- •Оглавление
- •Предисловие
- •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.7. Маршруты, цепи, циклы и связность
Пусть G — конечный граф. Маршрутом S в G называется последовательность ребер,
S = (u1, u2, …, un), (4.6)
в которой любые соседние два ребра ui-1, ui, (i = 2, n) имеют общую вершину.
На графах допускаются маршруты, в которых не принимаются во внимание направления ребер. Такие маршруты называются неориентированными.
Пусть на графе определен маршрут (4.6). Та вершина ребра u1, которая не является общей с вершиной ребра u2, называется начальной вершиной маршрута S.
Аналогично вводится понятие конечной вершины маршрута: та вершина ребра un, которая не является общей с вершиной un-1, называется конечной вершиной маршрута S.
Остальные вершины маршрута S называются внутренними.
Нуль‑маршрутом называется маршрут, не содержащий ребер.
Вершина uj называется достижимой из вершины ui, если существует маршрут из ui в uj. Для определенности считают, что любая вершина ui достижима из себя нуль-маршрутом независимо от наличия петель.
Неориентированный граф называется связным, если все его вершины попарно достижимы.
Неориентированный граф называется соотнесенным, если он получен из ориентированного либо смешанного графа заменой всех дуг на неориентированные ребра.
Ориентированный либо смешанный граф называется связным, если связен соответствующий ему соотнесенный граф.
Ясно, что отношение достижимости, построенное на ребрах графа, является отношением эквивалентности и разбивает любой граф на классы связных подграфов.
Маршрут называется цепью, если все его ребра различны и — простой цепью, если все его вершины различны
Цепь называется циклом, если начальная и конечная вершины цепи равны. Другое определение цикла — замкнутая цепь, которое понимается в первоначальном определении. Цикл называется простым, если все его вершины различны.
Началом (концом) цикла можно считать любую из его вершин.
На ориентированном графе аналогично понятию цепи вводится понятие пути, а аналогично понятию цикла — понятие контура.
Путь — это ориентированная цепь. Контур — это замкнутый путь. Рассмотрим примеры различных маршрутов на графе G, представленном на рисунке 4.11.
v1
u5
v4 u4 v3 u1 u2
u3 v2
u 6
u7 v5
Рисунок 4.11
Маршрут (u4, u1, u2) является простой цепью.
Маршрут (u4, u1, u2, u3, u1 ) цепью не является, поскольку ребро u1 встречается в нем дважды. Маршрут (u4, u3, u2, u1) представляет цепь, но не простую, поскольку вершина v3 встречается на ней дважды: как начало ребра u1 и как конец ребра u3. Такая цепь содержит в себе цикл. В данном случае в цепи (u4, u3, u2, u1) имеем цикл (u3, u2, u1 ). Этот цикл простой. Примером не простого цикла может служить маршрут (u1, u2, u3, u7, u6, u5 ).
Существенный интерес в теории графов, а также для приложений представляют маршруты, которые образуют эйлеровы и гамильтоновы циклы и цепи. Такие маршруты рассматриваются нами ниже.