- •Введение
- •1. Элементы теории множеств
- •1.1. Основные понятия и определения теории множеств
- •1.2. Операции над множествами и их свойства. Диаграммы Эйлера-Венна
- •1.3. Мощность множества
- •1.4. Взаимно однозначное соответствие между множествами
- •1.5. Счетные и несчетные множества
- •Задачи и упражнения
- •2. Элементы теории отношений
- •2.1. Бинарные отношения. Свойства отношений
- •2.2. Отношение эквивалентности и разбиения
- •2.3. Отношения порядка. Диаграмма Хассе
- •Задачи и упражнения
- •3.Функции, отображения и операции
- •4. Элементы теории графов
- •4.1. Основные понятия и определения теории графов
- •4.2. Типы графов
- •4.3. Матричные представления графов
- •4.5. Операции над графами
- •4.6. Метрические характеристики графа. Расстояние в графах
- •Затем, изымая степень, соответствующую вершине , получим
- •4.8. Достижимость и связность
- •4.8.1. Основные определения
- •4.8.2. Матрицы достижимостей
- •4.8.3. Нахождение сильных компонент
- •Алгоритм нахождения сильных компонент графа можно описать следующей последовательностью шагов
- •Таким образом, сильные компоненты графа можно находить по следующему алгоритму.
- •4.8.4. Базы и антибазы
- •4.9. Независимые и доминирующие множества
- •4.9.1. Нахождение всех максимальных независимых множеств
- •Опишем алгоритм нахождения всех максимальных независимых множеств вершин графа.
- •4.10. Покрытия и раскраски
- •4.11. Деревья, остовы и кодеревья
- •4.11.1. Основные определения
- •4.11.2. Алгоритм построения остова неорграфа
- •4.11.4. Обходы графа по глубине и ширине
- •Доказательство.
- •4.11.5. Упорядоченные и бинарные деревья
- •4.12. Эйлеровы циклы. Гамильтонов контур
- •4.12.1. Метод Флёри построения эйлерова цикла
- •Матрица м данного графа имеет вид
- •4.12.3. Алгебраический метод выделения гамильтоновых путей и контуров
- •4.13. Плоские и планарные графы
- •4.13.1. Формула Эйлера
- •4.13.2. Критерии анализа планарности
- •4.13.3. Алгоритм укладки графа на плоскости
- •Задачи и упражнения
- •5. Комбинаторика
- •5.1. Перестановки
- •5.2. Перестановки с неограниченными повторениями
- •5.3. Размещения
- •5.4. Сочетания
- •5.5. Сочетания с повторениями
- •5.6. Производящие функции для сочетаний
- •5.7. Производящие функции для перестановок
- •5.8. Циклы перестановок
- •Общее число дубликатов
- •5.9. Принцип включений и исключений
- •Почему появился ?
- •Задачи и упражнения
- •6. Алгебра высказываний
- •6.1. Операции над высказываниями
- •6.2. Правила записи сложных формул
- •6.3. Таблицы истинности
- •6.4. Равносильность формул
- •6.5. Дизъюнктивные и конъюнктивные нормальные формы
- •6.5.1. Алгоритм приведения пф к нормальным формам
- •6.5.2. Аналитический способ приведения к сднф
- •6.5.3. Табличный способ приведения к сднф
- •6.5.4. Табличный способ приведения к скнф
- •6.6. Логическое следствие
- •Задачи и упражнения
- •7. Разрешимые и неразрешимые проблемы
- •Заключение
- •Библиографический список
- •394026 Воронеж, Московский просп., 14
4.11.4. Обходы графа по глубине и ширине
Обход графа – это некоторое систематическое перечисление его вершин (и \ или ребер). Наибольший интерес представляют обходы, использующие локальную информацию. Среди всех обходов наиболее известны поиск в ширину и глубину. Эти обходы можно описать так.
При поиске в глубину, отправляясь в «путешествие» по графу из некоторой начальной вершины xо, мы действуем следующим образом. Пусть, «путешествуя», мы достигли некоторой вершины x (в начале «путешествия» x=x0). Отмечаем вершину x и просматриваем вершины из ее списка смежности L[x].
При условии, что в этом списке существует хотя бы одна неотмеченная вершина, продолжаем «путешествие» из первой такой вершины y, действуя как описано выше «ныряем» вглубь, т.е. просматриваем вершины списка смежности L[y] вершины y, откладывая анализ других элементов L[x] как возможных продолжений поиска «на потом».
Если же неотмеченных вершин в L[x] нет, то возвращаемся из x в ту вершину, из которой мы в нее попали, и продолжаем анализировать список смежности этой вершины.
Рассмотрим теперь поиск в ширину. При поиске в ширину «правила игры» такие: достигнув некоторой вершины, отмечаем ее. Затем просматриваем ее список смежности L[x] и отмечаем все ранее не отмеченные вершины списка (при старте поиска x=xo). После того как отмечены все вершины из L[x], вершину x считаем полностью обработанной и продолжаем обработку вершин из списка L[x] по очереди согласно описанным правилам.
Именно в обработке сразу всего списка смежности текущей вершины заключается принципиальное отличие поиска в ширину от поиска в глубину: там мы «ныряли» как можно «глубже», а здесь идем, «загребая» сразу все, что можно.
Поиск в ширину заканчивается, когда все вершины полностью обработаны или продолжение поиска невозможно.
Теорема 4.11.2. Если граф G=(X,V) связен, то поиск в ширину и глубину обойдут все вершины по одному разу.
Доказательство.
Единственность обхода вершин. Обходятся только вершины попавшие в Т. В Т попадают только неотмеченные вершины. При попадании в Т вершина отмечается. Следовательно, любая вершина будет обойдена не более одного раза.
Завершаем ость алгоритма. Всего в Т может попасть не более р вершин. На каждом шаге одна вершина удаляется из Т. Следовательно, алгоритм завершит работу не более чем через р шагов.
Обход всех вершин. От противного. Пусть алгоритм закончил работу, и вершина z не обойдена. Значит, не попала в Т. Следовательно, она не была отмечена. Отсюда следует, что все вершины, смежные с z, не были обойдены и отмечены. Аналогично, любые вершины, смежные с неотмеченными, сами не отмечены (после завершения алгоритма). Но G связан, значит, существует путь (x, z). Следовательно, вершина x не отмечена. Но она была отмечена на первом шаге.
Рассмотрим более подробно алгоритм поиска в ширину в графе.
Вход. Граф G=(X,V), заданный матрицей смежности начальная вершина (не обязательно первый элемент массива).
Выход. Массив Т меток вершин, где каждая метка равна длине пути от x 0 до x.
Шаг 1.В начале все вершины у нас не отмечены w[x]=0.
Шаг 2. Выбираем вершину с которой начнем обход и помещаем ее в структуру данных Т.
Шаг 3. Отмечаем эту вершину в качестве пройденной w[x]=1.
Шаг 4. Начинаем просматривать смежные с ней вершины, если данную вершину не просматривали (т.е. w[z]=0) то помещаем ее в структуру данных Т, и отмечаем ее как пройденную w[z]=1.
Шаг 5. Обход будем выполнять до тех пор, пока не отметим все вершины.
На рис. 4.37 представлен граф, вершины которого занумерованы согласно очередности, в которой они посещаются в процессе поиска в ширину.
Рис. 4.37