Начальные понятия теории графов (стр. 4 )

Рис. 1.13.

Под суммой двух абстрактных графов понимают объединение графов с непересекающимися множествами вершин. Точнее говоря, имеется в виду следующее. Сначала вершинам графов-слагаемых присваиваются имена (пометки, номера) так, чтобы множества вершин не пересекались, затем полученные графы объединяются. Операция сложения ассоциативна, то есть для любых трех графов. Поэтому можно образовывать сумму любого числа графов, не указывая порядка действий с помощью скобок. Если складываются экземпляров одного и того же графа , то полученный граф обозначается через . Например, . На рис. 1.14 изображен граф .

Рис. 1.14.

Рис. 1.15.

Соединением двух графов и называется граф, получаемый из их суммы добавлением всех ребер, соединяющих вершины первого слагаемого с вершинами второго. Будем записывать эту операцию как . На рис. 1.15 представлен граф . Легко видеть, что операции сложения и соединения графов связаны друг с другом следующими простыми соотношениями:

Введем еще два типа специальных графов, которые легко описываются с помощью операции соединения.

Первый - полный двудольный граф . В этом графе множество вершин разбито на два подмножества (доли), в одном из которых вершин, в другом , и две вершины в нем смежны тогда и только тогда, если они принадлежат разным подмножествам.

Второй - колесо . На рис. 1.16 показаны графы и .

Рис. 1.16.

Произведение графов и определяется следующим образом. Множеством вершин графа является декартово произведение множеств и , то есть вершины этого графа - упорядоченные пары , где - вершина первого сомножителя, - вершина второго. Вершины и в смежны тогда и только тогда, если и смежна с в графе , или и смежна с в графе . С помощью операции произведения можно выразить некоторые важные графы через простейшие. Например, произведение двух цепей дает прямоугольную решетку (см. рис. 1.17). Если один из сомножителей превратить в цикл, добавив одно ребро, то прямоугольная решетка превратится в цилиндрическую, а если и второй сомножитель превратить в цикл, то получится тороидальная решетка.

Рис. 1.17.

Другой пример - - мерный куб , определяемый следующим образом. Вершинами его являются всевозможные упорядоченные двоичные наборы длины . Всего, таким образом, в этом графе вершин. Вершины и смежны в нем тогда и только тогда, когда наборы и различаются точно в одной координате. С помощью операции произведения граф можно определить рекурсивно:

На рис. 1.18 показано, как получается из .

Рис. 1.18.

Маршруты, пути, циклы

Маршрут в графе - это последовательность вершин , такая, что для каждого вершины и соединены ребром. Эти ребер называются ребрами маршрута. Говорят, что маршрут проходит через них, а число называют длиной маршрута. Говорят, что маршрут соединяет вершины и , они называются соответственно началом и концом маршрута, вершины называются промежуточными. Маршрут называется замкнутым, если .

Путь - это маршрут, в котором все ребра различны. Путь называется простым, если и все вершины в нем различны.

Цикл - это замкнутый путь. Цикл называется простым, если все вершины попарно различны.

В графе на рисунке 2.1 последовательность вершин

- не маршрут; - маршрут, но не путь; - путь, но не простой; - замкнутый маршрут, но не цикл; - цикл, но не простой; - простой цикл.

Рис. 2.1.