- •Оглавление
- •Предисловие
- •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.3. Понятие изоморфизма и изоморфизм плоских графов
Один и тот же граф можно изображать по разному.
Во‑первых, в соответствии с описанием графа, вершины допускается представлять точками, которые в пространственном отношении могут располагаться произвольно друг по отношению к другу, но так чтобы разным вершинам отвечали бы и разные точки. Очевидно, что, в этом случае, несмотря на то, что визуальное изображение графа может существенно измениться, оба изображения — исходное и измененное — должны соответствовать одному и тому же описанию графа.
Во‑вторых можно перенумеровать вершины уже изображенного графа и при этом потребовать не различать описаний, поскольку граф при этом фактически остался тем же.
В таких ситуациях необходимо четко определиться какие графы различаются, а какие — нет. С этой целью вводится понятие изоморфизма графов. Слово «изоморфизм» в переводе с греческого означает — одинаковой формы.
Графы G(V,U) и G (V, U) называются изоморфными, если существует биекция между множествами вершин V и V, а также между множествами ребер U и U, сохраняющая отношение инцидентности: если v V, v V, u U и u U, то вершина v инцидентна ребру U тогда и только тогда, когда вершина v инцидентна ребру U.
Графы, содержащие различное число вершин или ребер, не могут быть изоморфными.
Понятие изоморфизма позволяет упростить решение ряда задач. Поясним это на примере решения задачи укладки графов. Под укладкой графа понимают такое его изоморфное преобразование, при котором граф становится плоским.
Задача укладки имеет применение, например, при разработках информационных, транспортных, энергетических сетей, и т.д.
Одной из первых задач укладки графов была следующая старинная шуточная задача. Три поссорившихся соседа имеют три общих колодца. Можно ли провести непересекающиеся дорожки от каждого дома к каждому из колодцев?
Строгое доказательство невозможности получения положительного решения этой задачи принадлежит Жордану. Им была доказана следующая теорема, которая на первый взгляд кажется очевидной.
Теорема 4.1 (Жордан) Если L — непрерывная замкнутая кривая без самопересечений на плоскости (рисунок 4.5), то L делит плоскость на внешнюю и внутреннюю области так, что любая непрерывная линия, соединяющая две точки x и у с внутренней и внешней области, пересекает L.
L y
x
Рисунок 4.5
Построим для задачи о трех соседях и трех колодцах граф, соответствующий взаимному расположению домов и колодцев. Этот граф изображен на рисунке 4.6 слева
На рисунке 4.6 справа изображен граф, изоморфный исходному. Из теоремы Жордана следует, что соединение вершин vd3 и vk2 ребром без пересечения с замкнутой кривой L не представляется возможным.
vd1 vd2 vd3
.. . vk1 L
.. .vd1 vd3 vd2
vk3
vk1 vk2 vk3 vk2
Рисунок 4.6
Конечно, пытаясь получить любое другое решение задачи, можно перенумеровать вершины нашего графа, однако, поскольку перенумерация вершин любого графа с сохранением инцидентности этих вершин ребрам приводит к изоморфизму этих же графов, то и в общем случае имеем отрицательное решение задачи о трех колодцах и трех поссорившихся соседях.
Граф, изображенный на рисунке 4.6 слева, получил специальное обозначение A33.
Другой, замечательный в отношении планарности граф, представлен на рисунке 4.7.
Этот граф имеет обозначение U55. Обозначение U обычно принимается для полных графов.
То, что граф U55 не плоский, доказывается точно также, как и для графа A33.
В теории плоских графов один из фундаментальных результатов принадлежит Понтрягину и Куратовскому. Ими доказана следующая теорема.
v2 v3
v1
v4 v5
Рисунок 4.7
Теорема 4.2 (Понтрягин и Куратовский) Для того, чтобы граф G был плоским, необходимо и достаточно, чтобы он не содержал частичного графа, изоморфного A33 или U5.
Доказательство этой теоремы ввиду его громоздкости мы опускаем.