- •Оглавление
- •Предисловие
- •1. Теоретико‑множественные основания дисциплины
- •1.1. Понятия и аксиомы теории множеств
- •1.2. Декартовы произведения, отношения и отношение эквивалентности
- •1.3. Понятия образа, прообраза, функции и отображения на конечном множестве. Аксиома выделения.
- •1.4. Аксиомы степени и бесконечности. Мощности и кардинальные числа множеств
- •1.5. Счетные и континуальные множества
- •1.6. Ординалы и трансфиниты. Аксиома выбора и континуум‑гипотеза
- •2. Основы математической логики
- •2.1. Высказывания и функции на высказываниях
- •2.2. Операции математической логики
- •2.3. Понятие формулы и свойства операций
- •2.4. Разложения булевых функций. Принцип двойственности. Совершенные нормальные формы.
- •2.5. Понятие полноты системы булевых функций
- •2.5. Исчисление предикатов
- •2.6. Введение в методы теории доказательств
- •1 Если X a,
- •0 Если X a.
- •1 Если X a,
- •0 Если X a.
- •3. Комбинаторика
- •3.1. Размещения
- •3.2. Размещения без повторений
- •3.3. Перестановки, подстановки и их свойства
- •3.4. Сочетания, структура соединений
- •3.5. Свойства биномиальных коэффициентов
- •Структура соединений
- •3.6. Понятие производящей функции
- •3.7. Соединения с повторениями
- •3.8. Разбиения множеств
- •3.9. Разбиения чисел
- •3.10. Композиции чисел
- •4. Основы теории графов
- •4.1. Основные понятия и определения
- •4.2. Графы и бинарные отношения
- •4.3. Понятие изоморфизма и изоморфизм плоских графов
- •4.4. Степени вершин графа
- •4.5. Представление графов матрицами
- •4.6. Представление графов списками инцидентности. Оценка пространственной сложности алгоритмов.
- •4.7. Маршруты, цепи, циклы и связность
- •4.7. Эйлеровы циклы и цепи
- •4.9. Гамильтоновы циклы. Оценка временной сложности алгоритмов
- •4.10. Деревья
- •4.11. Раскраска вершин и теорема Шеннона об информационной емкости графа
- •4.12. Раскраска ребер графа и теоремы о хроматическом классе
- •Ответы и решения
- •Список литературы
4. Основы теории графов
4.1. Основные понятия и определения
Пусть дано множество V = {v1, v2, …, vn} и в V определено семейство U = {u1, u2, …, um} пар элементов uk = {vi, vj}, (k = 1, m) произвольной кратности и упорядочения. Пара {V, U} именуется: граф. Графы, как правило, обозначают прописными латинскими буквами, например, G, H. Принято также писать G(V, U) для того, чтобы определить некоторый конкретный граф G.
Элементы v1, v2, …,vn называются вершинами графа, а пары uk = {vi, vj}, (k = 1, m) — ребрами.
Определению графа можно дать следующую интерпретацию. Пусть имеем описание графа:
G(V,Е) = {{ v1, v2, …, v6}, { { v1, v3 }, v5, v1, {v3, v4},
v2, v3, {v3, v3 }}}.
Это описание можно отобразить графически, как показано на рисунке 4.1. На этом рисунке некоторые ребра отмечены стрелкой, а соответствующие им пары вершин в описании графа выделены угловыми скобками. Это связано с тем, что для некоторого произвольного ребра можно принимать или не принимать во внимание порядок расположения его концов.
V6
v3 v5
Рисунок 4.1
Если этот порядок не существенен, то ребро называется неориентированным, в противном случае ребро называется ориентированным. Ориентированные ребра называются также дугами.
Для ориентированного ребра определены понятия начальной и конечной вершины. Начальная вершина записывается в начале пары вершин, определяющих дугу,а конечная — в конце. Так на рисунке 4.1 ребра v5, v1 и v2, v3 являются дугами. Они представлены упорядоченными парами вершин и, в связи с этим, обозначены так же, как обозначаются упорядоченные множества.
Ребра {v1, v3}, {v3, v4} неориентированы. Для любого неориентированного ребра полагают, что {vi, vj} = {vj, vi} так же, как и в случае неупорядоченных множеств. Ребро {vi, vi} называется петлей. На рисунке 4.1 имеем петлю {v3, v3}. Петли обычно не ориентированы.
Граф, у которого все ребра неориентированы, называется неориентированным. Неориентированное ребро может быть эквивалентно паре ориентированных ребер, если это возможно по условию задачи.
Граф, у которого все ребра ориентированы, называется ориентированным или орграфом.
На рисунке 4.1 приведен смешанный граф, т.е. содержащий как ориентированные, так и неориентированные ребра и петлю.
Многие теоремы и определения в теории графов могут быть отнесены как к ориентированным, так и к неориентированным графам. В таких случаях для обозначения ребер применяют круглые скобки, например, ребро {v3, v4} в графе рисунок 4.1 можно обозначать (v3, v4) либо (v4, v3), а ребро v5, v1 — соответственно как (v5, v1), указав при этом, что данное ребро представляет дугу. Принято также обозначение всех ребер круглыми скобками как в случае ориентированных графов, так неориентированных, если совершенно ясно о каком из типов этих графов идет речь в тексте.
Некоторые вершины графа G могут не войти в список пар. Такие вершины именуются изолированными. В рассмотренном примере это вершина v6. Граф, у которого все вершины изолированы, именуется нуль‑графом. Множество ребер такого графа пусто.
Антиподом нуль‑графа является полный граф. Ребрами полного графа являются всевозможные пары его вершин.
Как в случае ориентированного графа, так и в случае неориентированного — говорят, что ребро инцидентно паре определяющих его вершин.
Одной и той же паре вершин можно поставить в соответствие множество инцидентных ребер. Такие ребра называются кратными. Так на рисунке 4.2 представлена пара вершин (vi, vj), инцидентных трем различным ребрам u1, u2, u3. Одно из них направлено, а два — нет.
u1
vi u2 vj
u3
Рисунок 4.2
Граф называется плоским, если он может быть изображен на плоскости так, что все пересечения ребер есть его вершины. Так графы, представленные на рисунках 4.1 и 4.2 плоские. Примеры не плоских графов будут рассмотрены ниже в разделе 4.3.
Если граф G представлен конечным множеством ребер, то он называется конечным, независимо от числа вершин. В противном случае, граф называется бесконечным.
Граф H называется частью графа G или частичным графом H G, если множество его вершин V(H) содержится в множестве вершин V(G) графа G и все ребра H являются ребрами G. Частным, но важным типом частичных графов являются подграфы.
Пусть A — подмножество множества вершин V графа G. Подграф G(A) графа G есть такая часть графа, множеством вершин которого является A, а ребрами — все ребра из G, оба конца, которых лежат в A.
Для любой частиH графа определена дополнительная часть H (дополнение), состоящая из всех тех ребер, которые не принадлежат H и всех инцидентных им вершин.