- •Множества. Основные операции над множествами и их свойства. Диаграммы Венна. Декартово произведение множеств.
- •Отношения и бинарные отношения, область определения, область значения, обратные отношения. Произведение отношений.
- •Функции. Инъекции, сюръекции, биекции. Понятие последовательности.
- •Множество натуральных чисел. Два подхода к определению множества натуральных чисел. Аксиомы Дедекинда-Пеано. Принцип математической индукции.
- •Понятие мощности множества. Сравнение мощностей. Теорема Кантора-Берштейна. Операции над кардинальными числами.
- •Конечные, счетные, континуальные множества. Мощность булеана.
- •Матрицы бинарных отношений и их свойства. Специальные бинарные отношения.
- •Отношения эквивалентности и разбиения. Фактор-множества. Матрица отношения эквивалентности.
- •Отношения порядка. Максимальные и минимальные, наибольший и наименьший элементы частично упорядоченного множества. Диаграммы Хассе. Линейно и вполне упорядоченные множества.
- •Алгебраические системы: определение и примеры. Понятие полугруппы, моноида, группы; задание с помощью таблицы Кэли.
- •Морфизмы алгебраических систем.
- •Подсистемы. Термы сигнатуры ∑. Подсистема, порожденная множеством, ее структура.
- •Конгруэнции, фактор-алгебры, теорема о гомоморфизме.
- •17.Многообразия. Теорема Биркгофа.
- •Решетки. Дистрибутивные решетки. Критерий дистрибутивности.
- •Булевы алгебры. Теорема Стоуна. Принцип двойственности для булевых алгебр.
- •Булево кольцо.
- •18. Алгебры отношений. Реляционные алгебры.
- •27. Виды и способы задания графов.
- •28. Подграфы и части графа. Операции над графами. N-Мерные кубы.
- •Объединение: .
- •29. Маршруты, циклы, цепи. Достижимость и связность (матрицы достижимости, контрдостижимости, связности).
- •30. Расстояние в графах. Центральные и периферийные вершины.
- •31. Взвешенное расстояние. Алгоритм Форда-Беллмана.
- •32. Степени вершин. Эйлеровы графы, циклы, цепи. Алгоритм построения эйлерова цикла.
- •33. Гамильтоновы графы. Постановка задачи коммивояжера.
- •34. Деревья, леса. Остовы графов. Цикломатическое число, коранг. Алгоритм построения остова минимального веса. Обходы графов по глубине и ширине.
- •35. Упорядоченные и бинарные деревья. Соответствия между ними.
- •36. Фундаментальные циклы, разрезы. Матрицы фундаментальных циклов, разрезов.
- •37. Раскраска графов. Планарные графы.
- •38. Формулы алгебры логики, их таблицы истинности.
- •39. Булевы функции, способы их задания. Представления булевых функций формулами.
- •40. Эквивалентность формул.
- •41. Двухэлементная булева алгебра. Алгебра булевых функций. Фактор-алгебра алгебры формул.
- •42. Дизъюнктивные и конъюнктивные нормальные формы. Алгоритм приведения формулы к днф и кнф.
- •43. Теорема Шеннона. Теорема о функциональной полноте. Способы построения сднф и скнф.
- •44. Импликанты, простые импликанты. Сокращенные, тупиковые, минимальные нормальные формы. Алгоритм Квайна построения мднф.
- •45. Карты Карно. Построение мднф с помощью карт Карно.
- •46. Принцип двойственности. Самодвойственные функции.
- •47. Теорема Жегалкина. Способы построения полиномов Жегалкина. Линейные функции.
- •48. Классы Поста. Полные системы булевых функций. Теорема Поста. Базисы.
- •49. Логические сети. Реализация булевых функций контактными схемами и схемами из функциональных элементов.
30. Расстояние в графах. Центральные и периферийные вершины.
Пусть G=<M,R> - связный неорграф, a,b – две его несовпадающие вершины. Длина кратчайшего (a,b)-маршрута называется расстоянием между вершинами a и b и обозначается ρ(a,b). Положим ρ(a,a)=0.
Аксиомы метрики:
ρ(a,b)≥0;
ρ(a,b)=0 a=b
ρ(a,b)= ρ(b,a) (симметричность)
ρ(a,b)≤ ρ(a,с)+ ρ(с,b) (неравенство треугольника)
Если M={a1,…,an}, то матрица P=(pij), в которой pij=ρ(ai,aj), называется матрицей расстояний. Заметим, что PT=P.
Эксцентриситетом вершины a называется величина .
Максимальный среди всех эксцентриситетов вершин называется диаметром графа G и обозначается через d(G): . Вершина a называется периферийной, если e(a)=d(G). Минимальный из эксцентриситетов графа G называется его радиусом r(G): . Вершина a называется центральной, если e(a)=r(G). Множество всех центральных вершин графа называется его центром.
31. Взвешенное расстояние. Алгоритм Форда-Беллмана.
Пусть G=<M,R> - взвешенный граф, в котором вес каждой дуги (a,b) есть некоторое вещественное число μ(a,b). Весом маршрута a1,…,an+1 называется число . Взвешенным расстоянием (ω-расстоянием) ρω(a,b) между вершинами a и b называется минимальный из весов (a,b)-маршрутов). Маршрут с минимальным весом называется кратчайшим. Взвешенным эксцентриситетом вершины a называется величина . Взвешенной центральной вершиной называется вершина a, для которой . Взвешенный эксцентриситет центральной вершины называется взвешенным радиусом.
Пусть G=<M,R> - взвешенный граф, имеющий n вершин и матрицу весов W=(ωij). Предположим, что в G отсутствуют контуры с отрицательным весом, поскольку двигаясь по такому контуру достаточное число раз можно получить маршрут бесконечно малого веса.
Алгоритм Форда-Беллмана (для нахождения взвешенного расстояния от вершины ai (источника) до всех вершин графа G):
Зададим строку , полагая . Определим строку , полагая . Нетрудно заметить, что - минимальный из весов (ai,aj)-маршрутов, состоящих не более чем из двух дуг.
Продолжая процесс, на шаге s определим строку , полагая . Искомая строка ω-расстояний получается при s=n-1: . Алгоритм можно завершить на шаге k, если D(k)=D(k+1).
32. Степени вершин. Эйлеровы графы, циклы, цепи. Алгоритм построения эйлерова цикла.
Степенью или валентностью вершины a неорграфа G называется число ребер, инцидентных вершине a (петли считаются дважды). Вершина степени 0 называется изолированной, степени 1 – концевой или висячей.
Лемма о рукопожатиях: Сумма степеней всех вершин графа является четным числом и равна удвоенному числу ребер.
Критерий «эйлировости» графа: Связный неориентированный мультиграф тогда и только тогда является эйлеровым, когда степень каждой из его вершин – четное число.
Алгоритм построения эйлерова цикла:
Выбрать произвольно некоторую вершину a.
Выбрать произвольно некоторое ребро u, инцидентное a, и присвоить ему номер 1 (назовем это ребро пройденным).
Каждое пройденное ребро вычеркнуть и присвоить ему номер, на единицу больший предыдущего вычеркнутого ребра.
Находясь в вершине x, не выбирать ребро, соединяющее x с a, если есть возможность иного выбора.
Находясь в вершине x, не выбирать ребро, которое является перешейком (т.е. ребром, при вычеркивании которого граф распадается на две компоненты связности).
После того как в графе будут занумерованы все ребра, образуется эйлеров цикл.
Теорема: Если связный граф содержит k вершин нечетной степени, то минимальное число покрывающих его реберно непересекающихся цепей равно k/2.
Доказательство: Набор реберно непересекающихся цепей покрывает граф G, если каждое его ребро входит в одну из этих цепей.
Пусть связный граф G содержит k вершин нечетной степени. По лемме о рукопожатиях число k четно. Рассмотрим граф G’, полученной добавлением к G новой вершины a и ребер, соединяющих a со всеми вершинами нечетной степени графа G. Граф G’ будет содержать эйлеров цикл. Если удалить из этого цикла все ребра, инцидентные вершине a, то получится не более k/2 цепей, покрывающих G. С другой стороны, граф, являющийся объединением r реберно непересекающихся цепей имеет не более 2r верши нечетной степени. Поэтому граф G нельзя покрыть цепями, число которых меньше k/2.