Основные термины для ориентированных и неориентированных графов

Смешанный граф – это граф, в котором некоторые рёбра могут быть ориентированными, а некоторые – неориентированными. Записывается упорядоченной тройкой , где определены так же, как выше. Ориентированный и неориентированный графы являются частными случаями смешанного.

Рисунок 6.3 – Смешанный граф

На рисунке 6.3 – ребра и – неориентированные, дуги и – ориентированные.

Подграфом графа называется граф , все вершины и дуги которого содержатся среди вершин и дуг графа , т.е. . Сам граф является своим подграфом.

Сам граф по отношению к своим подграфам называется надграфом (или суперграфом).

Подграф называется собственным, если он отличен от самого графа.

Для любого подмножества вершин графа порождённым подграфом называется максимальный подграф графа , множеством вершин которого является .

Часть графа, которая наряду с некоторым подмножеством ребер (дуг) графа содержит и все вершины исходного графа называется суграфом.

Подграф неориентированного графа называется каркасом, или остовным деревом (остовом) графа , если – дерево и .

Пример. На рисунке 6.4 изображен граф и его подграфы. Подграф – остовный, подграф – порожденный.

Рисунок 6.4 – Подграфы

Изоморфные графы. Граф называется изоморфным графу , если существует биекция f из множества вершин графа в множество вершин графа , обладающая следующим свойством: если в графе есть ребро из вершины A в вершину B, то в графе должно быть ребро из вершины в вершину и наоборот – если в графе есть ребро из вершины A в вершину B, то в графе должно быть ребро из вершины в вершину . В случае ориентированного графа эта биекция также должна сохранять ориентацию ребра. В случае взвешенного графа биекция также должна сохранять вес ребра.

Рисунок 6.5 – Изоморфные графы

Путём (или цепью) в графе называют конечную последовательность вершин, в которой каждая вершина (кроме последней) соединена со следующей в последовательности вершин ребром.

Ориентированным путём в орграфе называют конечную последовательность вершин , для которой все пары являются (ориентированными) рёбрами.

Циклом называют путь, в котором первая и последняя вершины совпадают. При этом длиной пути (или цикла) называют число составляющих его рёбер. Заметим, что если вершины и являются концами некоторого ребра, то согласно данному определению, последовательность является циклом. Чтобы избежать таких «вырожденных» случаев, вводят следующие понятия.

Путь (или цикл) называют простым, если ребра в нём не повторяются; элементарным (или контуром), если он простой и вершины в нём не повторяются. Несложно видеть, что:

• всякий путь, соединяющий две вершины, содержит элементарный путь, соединяющий те же две вершины;

• всякий простой неэлементарный путь содержит элементарный цикл;

• всякий простой цикл, проходящий через некоторую вершину (или ребро), содержит элементарный (под-) цикл, проходящий через ту же вершину (или ребро);

• петля – элементарный цикл.

Пример. Рассмотрим граф на рисунке 6.6. Он содержит пути: (5, 1, 2), (5, 6, 3, 2), (4, 5, 1, 4, 2) и т.д. Все эти пути простые, элементарным же является только последний. Цикл в графе только один – (1, 4, 5).

Рисунок 6.6 – Пути на графе

Бинарное отношение на множестве вершин графа, заданное как «существует путь из в », является отношением эквивалентности, и, следовательно, разбивает это множество на классы эквивалентности, называемые компонентами связности графа. Если у графа ровно одна компонента связности, то граф связный. На компоненте связности можно ввести понятие расстояния между вершинами как минимальную длину пути, соединяющего эти вершины.

Всякий максимальный связный подграф графа называется связной компонентой (или просто компонентой) графа . Слово «максимальный» означает максимальный относительно включения, то есть не содержащийся в связном подграфе с большим числом элементов

Ребро графа называется мостом, если его удаление увеличивает число компонент.

Вершина, удаление которой приводит к увеличению компонент связности, называется точкой сочленения. Множество вершин, удаление которых (всех вместе), приводит к увеличению компонент связности, называется разделяющим множеством.

Пример. На рис. 6.7: в графе – ребро – мост; в графе – вершина – точка сочленения; в графе – множество вершин – разделяющее множество.

Рисунок 6.7

Граф называется:

• связным, если для любых вершин u, v есть путь из u в v.

• сильно связным или ориентировано связным, если он ориентированный, и из любой вершины в любую другую имеется ориентированный путь.

• деревом, если он связный и не содержит простых циклов (рис 6.8).

• полным, если любые его две (различные, если не допускаются петли) вершины соединены ребром. Полный граф с n вершинами обозначается . На рис. 6.9 изображены полные графы .

• двудольным, если его вершины можно разбить на два непересекающихся подмножества и так, что всякое ребро соединяет вершину из с вершиной из . Двудольный граф называется полным двудольным графом , если содержит вершин, содержит вершин и для каждого , имеем . Таким образом, для каждого и имеется связывающее их ребро. На рис. 6.10 изображены полные двудольные графы .

• k-дольным, если его вершины можно разбить на непересекающихся подмножества так, что не будет рёбер, соединяющих вершины одного и того же подмножества.

• планарным, если граф можно изобразить диаграммой на плоскости без пересечений рёбер (рис. 6.11).

• взвешенным или нагруженным, если каждому ребру графа поставлено в соответствие некоторое число, называемое весом ребра (рис. 6.12).

• однородным (регулярным) графом степени , если степени всех вершин которого одинаковы и равны . Граф третьей степени называют кубическим; этот граф обладает рядом интересных свойств и, в частности, он всегда имеет четное число вершин (рис. 6.13).

Примеры:

Рисунок 6.8 – Граф – дерево

Рисунок 6.9 – Полные графы

Рисунок 6.10 – Полные двудольные графы

Рисунок 6.11 – Планарный граф и его плоское изображение

Рисунок 6.12 – Нагруженный граф

Вставить рисунки (6.13)