Материал: 00464
Рис. 1.12.
Дополнением
(дополнительным
графом)
к графу
называется
граф
,
у которого множество вершин то же, что
у
,
а множество ребер является дополнением
множества
до
множества всех неупорядоченных пар
вершин. Иначе говоря, две различные
вершины смежны в графе
тогда
и только тогда, когда они несмежны в
графе
.
Например,
.
Другой пример показан на рис.
1.13.
Очевидно, что всегда
.
Рис. 1.13.
Под
суммой
двух
абстрактных графов понимают объединение
графов с непересекающимися множествами
вершин. Точнее говоря, имеется в виду
следующее. Сначала вершинам графов-слагаемых
присваиваются имена (пометки, номера)
так, чтобы множества вершин не пересекались,
затем полученные графы объединяются.
Операция сложения ассоциативна, то есть
для
любых трех графов. Поэтому можно
образовывать сумму любого числа графов,
не указывая порядка действий с помощью
скобок. Если складываются
экземпляров
одного и того же графа
,
то полученный граф обозначается через
.
Например,
.
На рис.
1.14
изображен граф
.
Рис. 1.14.
Рис. 1.15.
Соединением
двух графов
и
называется
граф, получаемый из их суммы добавлением
всех ребер, соединяющих вершины первого
слагаемого с вершинами второго. Будем
записывать эту операцию как
.
На рис.
1.15
представлен граф
.
Легко видеть, что операции сложения и
соединения графов связаны друг с другом
следующими простыми соотношениями:
Введем
еще два типа специальных графов, которые
легко описываются с помощью операции
соединения. Первый - полный
двудольный граф
.
В этом графе множество вершин разбито
на два подмножества (доли), в одном из
которых
вершин,
в другом
,
и две вершины в нем смежны тогда и только
тогда, если они принадлежат разным
подмножествам. Второй - колесо
.
На рис.
1.16
показаны графы
и
.
Рис. 1.16.
Произведение
графов
и
определяется
следующим образом. Множеством вершин
графа
является
декартово произведение множеств
и
,
то есть вершины этого графа - упорядоченные
пары
,
где
-
вершина первого сомножителя,
-
вершина второго. Вершины
и
в
смежны
тогда и только тогда, если
и
смежна
с
в
графе
,
или
и
смежна
с
в
графе
.
С помощью операции произведения можно
выразить некоторые важные графы через
простейшие. Например, произведение двух
цепей дает прямоугольную
решетку
(см. рис.
1.17).
Если один из сомножителей превратить
в цикл, добавив одно ребро, то прямоугольная
решетка превратится в цилиндрическую,
а если и второй сомножитель превратить
в цикл, то получится тороидальная
решетка.
Рис. 1.17.
Другой
пример -
-
мерный куб
,
определяемый следующим образом. Вершинами
его являются всевозможные упорядоченные
двоичные наборы длины
.
Всего, таким образом, в этом графе
вершин.
Вершины
и
смежны
в нем тогда и только тогда, когда наборы
и
различаются
точно в одной координате. С помощью
операции произведения граф
можно
определить рекурсивно:
На
рис.
1.18
показано, как получается
из
.
Рис. 1.18.
Лекция 2. Поиск в глубину и ширину. Поиск в ширину
С этой лекции мы начинаем рассматривать алгоритмы для решения различных задач на графах. Сначала речь пойдет о задачах анализа графов с целью выявления их структуры и вычисления метрических характеристик. Многие задачи такого рода могут быть решены путем систематического обхода графа с посещением всех его вершин и исследованием всех его ребер. Такой обход можно выполнить многими способами, в действительности же широкое распространение благодаря своей простоте, а в большей степени своей полезности, получили две стратегии - поиск в глубину и поиск в ширину. Рассмотрение этих алгоритмов и примеров их применения к задачам анализа графов составляет содержание этой и двух следующих лекций.
Процедура поиска в ширину
Работа всякого алгоритма обхода состоит в последовательном посещении вершин и исследовании ребер. Какие именно действия выполняются при посещении вершины и исследовании ребра - зависит от конкретной задачи, для решения которой производится обход. В любом случае, однако, факт посещения вершины запоминается, так что с момента посещения и до конца работы алгоритма она считается посещенной. Вершину, которая еще не посещена, будем называть новой. В результате посещения вершина становится открытой и остается такой, пока не будут исследованы все инцидентные ей ребра. После этого она превращается в закрытую.
Идея
поиска в ширину состоит в том, чтобы
посещать вершины в порядке их удаленности
от некоторой заранее выбранной или
указанной стартовой вершины
.
Иначе говоря, сначала посещается сама
вершина
,
затем все вершины, смежные с
,
то есть находящиеся от нее на расстоянии
,
затем вершины, находящиеся от
на
расстоянии
,
и т.д.
Рассмотрим алгоритм поиска в ширину с заданной стартовой вершиной . Вначале все вершины помечаются как новые. Первой посещается вершина , она становится единственной открытой вершиной. В дальнейшем каждый очередной шаг начинается с выбора некоторой открытой вершины . Эта вершина становится активной. Далее исследуются ребра, инцидентные активной вершине. Если такое ребро соединяет вершину с новой вершиной , то вершина посещается и превращается в открытую. Когда все ребра, инцидентные активной вершине, исследованы, она перестает быть активной и становится закрытой. После этого выбирается новая активная вершина, и описанные действия повторяются. Процесс заканчивается, когда множество открытых вершин становится пустым.
Основная особенность поиска в ширину, отличающая его от других способов обхода графов, состоит в том, что в качестве активной вершины выбирается та из открытых, которая была посещена раньше других. Именно этим обеспечивается главное свойство поиска в ширину: чем ближе вершина к старту, тем раньше она будет посещена. Для реализации такого правила выбора активной вершины удобно использовать для хранения множества открытых вершин очередь - когда новая вершина становится открытой, она добавляется в конец очереди, а активная выбирается в ее начале. Схематически процесс изменения статуса вершин изображен на рис. 2.1. Черным кружком обозначена активная вершина.
Рис. 2.1.
Опишем
процедуру поиска в ширину (BFS - от
английского названия этого алгоритма
- Breadth First Search) из заданной стартовой
вершины
.
В этом описании
обозначает
множество всех вершин, смежных с вершиной
,
-
очередь открытых вершин. Предполагается,
что при посещении вершины она помечается
как посещенная и эта пометка означает,
что вершина уже не является новой.
Procedure BFS(a)
посетить вершину
while
do
for
do
исследовать ребро
if вершина новая
then посетить вершину
Отметим некоторые свойства процедуры BFS.
Процедура BFS заканчивает работу после конечного числа шагов.
Действительно, при каждом повторении цикла while из очереди удаляется одна вершина. Вершина добавляется к очереди только тогда, когда она посещается. Каждая вершина может быть посещена не более одного раза, так как посещаются только новые вершины, а в результате посещения вершина перестает быть новой. Таким образом, число повторений цикла while не превосходит числа вершин.
В результате выполнения процедуры BFS будут посещены все вершины из компоненты связности, содержащей вершину a, и только они.
Очевидно, что вершина может быть посещена только в том случае, когда существует путь, соединяющий ее с вершиной (так как посещается всегда вершина, смежная с уже посещенной). То, что каждая такая вершина будет посещена, легко доказывается индукцией по расстоянию от данной вершины до вершины .
Время работы процедуры BFS есть
,
где
-
число ребер в компоненте связности,
содержащей вершину
.
Из
предыдущих рассуждений видно, что каждая
вершина из этой компоненты становится
активной точно один раз. Внутренний
цикл for
для активной вершины
выполняется
раз.
Следовательно, общее число повторений
внутреннего цикла будет равно
.
Итак, процедура BFS( ) производит обход компоненты связности, содержащей вершину . Чтобы перейти к другой компоненте, достаточно выбрать какую-нибудь новую вершину (если такие вершины еще имеются), в качестве стартовой. Пусть - множество вершин графа. Следующий алгоритм осуществляет полный обход графа методом поиска в ширину.
Алгоритм 1. Поиск в ширину.
пометить все вершины как новые
создать пустую очередь
for
do
if
новая
then
BFS(
)