- •Содержание
- •Введение
- •Часть 1. Элементы теории множеств и отношений § 1. Понятие множества. Операции над множествами
- •Примеры
- •Операции над множествами
- •Основные тождества алгебры множеств
- •Упражнения
- •§ 2. Декартово произведение двух или нескольких множеств. Понятие отношения. Бинарные отношения
- •Упражнения
- •§ 3. Специальные бинарные отношения. Отношения эквивалентности
- •Упражнения
- •§ 4. Отношения порядка
- •Упражнения
- •§ 5. Функциональные отношения (отображения). Виды отображений
- •Виды отображений:
- •Упражнения
- •Часть 2. Теория графов
- •§ 1. Основные понятия теории графов
- •Способы задания графов. Матричное задание графов.
- •Свойства матриц смежности и инцидентности
- •Упражнения
- •§ Б 2. Булевы матрицы
- •Дизъюнкция (конъюкция)
- •§ 3. Связность графа. Компоненты связности. Матрица связности
- •Выделение компонент связности
- •Алгоритм выделения компонент сильной связности
- •Упражнения
- •§ 4. Полные графы. Двудольные графы. Однородные и реберные графы
- •Упражнения
- •§ 5. Поиск путей (маршрутов) с минимальным числом дуг (ребер)
- •Упражнения
- •§ 6. Расстояние в графах
- •Упражнения
- •§ 7. Нагруженные графы. Расстояния в нагруженном графе
- •Нахождение минимального пути в нагруженном орграфе
- •Алгоритм Форда-Беллмана нахождения минимального пути в нагруженном орграфе из v1 в vi1 (i1≠1)
- •Упражнения
- •§ 8. Эйлеровы цепи и циклы в графах. Эйлеровы графы. Гамильтоновы цепи и циклы в графах. Гамильтоновы графы
- •Упражнения
- •§ 9. Деревья. Остов графа. Цикловой базис графа
- •Алгоритм нахождения кратчайшего остова в нагруженном графе
- •Упражнения
- •§ 10. Раскраска графов. Планарные графы Раскраска вершин графа
- •Одноцветные классы образуют независимые множества вершин.
- •Существуют и приближенные алгоритмы раскрашивания:
- •Упражнения
- •Варианты контрольных работ Часть 1. Элементы теории множеств и отношений Вариант № 1.
- •Вариант № 2.
- •Вариант № 3.
- •Вариант № 4.
- •Вариант № 5.
- •Вариант № 6.
- •Часть 2. Теория графов Вариант № 1.
- •Вариант № 2.
- •Вариант № 3.
- •Вариант № 4.
- •Вариант № 5.
- •Вариант № 6.
- •Ответы Часть 1
- •Часть 2
- •Тест по теории множеств и отношений
- •Тест по теории графов
- •Библиографический список
- •Любовь Васильевна Архипова Елена Сергеевна Дернович
- •Дискретная математика
Упражнения
4.1. Найти число ребер и степени вершин в полных графах К6, К7, К8.
4.2. Найти количество ребер в полных двудольных графах К4, 6, К3, 5, К2, 3. Составить матрицу связности графа К2, 3.
4.3. Найти количество ребер в графах Е2, Е3, Е4. Построить реализации графов Е2, Е3 (Е2, Е3, Е4 – двух-, трех-, четырехмерные кубы).
4.4. Найти число полных трехвершинных подграфов в полных двудольных графах К3, 5, К4, 3.
4.5. Количество ребер в однородном графе G равно 15. Степень каждой вершины графа равна 3. Найти количество вершин графа G.
4.6. Существует ли полный граф с семью ребрами? С 50 ребрами?
4.7. Дан полный граф G и i: δ (v i) 20. Найти количество вершин и ребер графа.
4.8. Доказать, что графы Е³, Е4 являются двудольными.
4.9. Найти дополнение графа G до полного графа. Составить матрицы смежности графа G и его дополнения (по формуле).
G:
4.10. Для заданного графа G:
а) Построить соответствующий реберный граф;
б) Найти матрицу смежности реберного графа через матрицу инцидентности исходного графа (по формуле);
в) Определить степени вершин реберного графа через степени вершин исходного графа;
г) Определить число ребер в реберном графе, используя исходный граф G:
4.11. Построить однородный 5-вершинный граф. Составить его матрицу инцидентности. По матрице инцидентности найти матрицу смежности однородного графа. Построить соответствующий реберный граф. Найти его матрицу смежности, степени вершин, число ребер, используя исходный однородный граф.
§ 5. Поиск путей (маршрутов) с минимальным числом дуг (ребер)
Определение: Путь (маршрут) в орграфе Д (графе G) из вершины vi в вершину vj (i j) называется минимальным, если он имеет минимальную длину среди всех путей (маршрутов) орграфа Д (графа G).
Алгоритм поиска минимального пути из v в w орграфе Д (графе G).
Введем обозначения: Пусть Д = (V, X) – орграф, v V, V1 V
Обозначим
Д(v) = {w V | (v,w) X} – образ вершины v
Д-1(v) = {w V | (w, v) X} – прообраз вершины v
Д(V1) = Д(v), где v V1 – образ множества вершин V1.
Д-1(V1) = Д-1(v), где v V1 – прообраз множества вершин V1.
Пусть G = (V, X) – граф, v V, V1 V
Обозначим
G(v) = {w V | (v,w) X} – образ вершины v
G(V1) = G(v), где v V1 – образ множества вершин V1
Пусть Д = (V, X) – орграф с n вершинами (n 2).
v, w – заданные вершины из V, v w.
Опишем алгоритм поиска минимального пути из v в w в орграфе Д (алгоритм фронта волны).
-
Помечаем вершину v индексом 0, т. е. F W0 (v) = { v }. Затем помечаем образы вершины v, индексом 1. Множество вершин с индексом 1 обозначим FW1(v). Полагаем k = 1.
-
Если FWk(v) = Ø или k = n – 1, wFWk(v), то вершина w не достижима из вершины v, и работа алгоритма на этом заканчивается. В противном случае переходим к шагу 3.
-
Если wFWk(v), то переходим к шагу 4. В противном случае существует путь из v в w длины k и этот путь минимальный.
Последовательность вершин:
v w1 w2 … wk-1w, где
wk-1 F Wk-1 (v) ∩ Д-1 (w) (1)
wk-2 F Wk-2 (v) ∩ Д-1 (wk-1)
…
w1 F W1 (v) ∩ Д-1 (w2)
и есть искомый путь длины k из v в w. На этом работа алгоритма заканчивается.
-
Помечаем индексом k+1 все непомеченные вершины, которые принадлежат образу множества вершин с индексом k. Множество вершин с индексом k+1 обозначаем F Wk+1 (v). Присваиваем k := k+1 и переходим к шагу 2.
Множество F W(v) в алгоритме обычно называют фронтом волны k-го уровня.
Вершины w1, …, wk-1 из последовательности (1), вообще говоря, могут быть выделены неоднозначно. Эта неоднозначность соответствует случаям, когда существует несколько различных минимальных путей из v в w.