16. Свойства графов

Подграфом G_А графа G=<М,Т> называется граф, в который входит лишь часть вершин графа G, образующих множество А, вместе с ребрами (дугами), их соединяющими.

Так, карта шоссейных дорог Пермской области является подграфом графа «Карта шоссейных дорог Российской Федерации» [18].

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

Так, карта главных дорог России – подграф карты шоссейных дорог России [18].

Если две вершины соединены ребром, то говорят, что каждая вершина инцидентна этому ребру, а соответствующие вершины – смежны (две вершины, инцидентные одному ребру – смежны). Два ребра, инцидентные одной вершине, также смежны.

Маршрут – чередующаяся последовательность вершин и ребер, в которой два соседних элемента инцидентны [26].

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

Если все ребра различны, то маршрут называется цепью.

Если все вершины (а, значит и ребра) различны, то маршрут называется простой цепью.

Замкнутая цепь – цикл.

Граф без циклов называется ациклическим.

В ориентированном графе цепь называется путем, а цикл – контуром.

Степенью вершины х, обозначаемой deg(х), называют число ребер, инцидентных ей. Если degх=1, то вершина х тупиковая, если degх=0, то вершина изолированная.

Если G – неориентированный граф с n вершинами и m ребрами, а degj – степени j-й вершины, то сумма степеней вершин равна удвоенному количеству ребер:

.

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

Деревья. Лес.

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

Связный граф, не имеющий циклов (ациклический), называется деревом (рис. 17).

Рис. 17. Граф-дерево

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

Простейшее дерево состоит из двух вершин, соединенных ребром. Каждый раз, когда добавляется еще одно ребро, в конце его прибавляется также и вершина. Следовательно, дерево с n вершинами имеет n-1 ребро.

В теории графов доказывается, что число различных деревьев, которые можно построить на m вершинах, равно m^m-2. Много деревьев – это лес.

Цикломатическое число.

Пусть G – неориентированный связный граф, имеющий n вершин и m ребер.

Цикломатическим числом связного графа G с n вершинами и m ребрами называется число

(G)=m-n+1.

Это число имеет интересный физический смысл: оно равно наибольшему числу независимых циклов в графе [18]. При расчете электрических цепей цикломатическое число используется для определения числа независимых контуров.

Рассмотрим примеры подсчета числа независимых циклов.

В графе, состоящем из одной вершины и одного ребра, один цикл (рис. 18а).

В графе, состоящем из одной вершины и трех ребер, три цикла (рис. 18б).

В графе, состоящем из двух вершин и двух ребер, один цикл (рис. 18в).

В графе, состоящем из двух вершин и пяти ребер, четыре цикла (рис. 18г).

В графе, состоящем из трех вершин и трех ребер, один цикл (рис. 18д).

В графе, состоящем из трех вершин и четырех ребер, два цикла (рис. 18е).

В графе, состоящем из четырех вершин и четырех ребер, один цикл (рис. 18ж).

В графе, состоящем из четырех вершин и пяти ребер, два цикла (рис. 18з).

В графе, состоящем из четырех вершин и шести ребер, три цикла (рис. 18и).

Цикломатическое число дерева равно нулю.

Рис. 18. Примеры циклов в графах

Плоские (планарные) графы.

Граф называется плоским (планарным), если он может быть изображен на плоскости так, что все пересечения ребер являются вершинами (без пересечения рёбер).

Аналогично можно ввести понятие объемного, т.е. трехмерного графа и т.д.

Хроматическое число графа.

Граф G называют р-хроматическим, где р – натуральное число, если его вершины можно раскрасить р различными цветами так, чтобы никакие две смежные вершины не были раскрашены одинаково. Наименьшее число р, при котором граф является р-хроматическим, называют хроматическим числом графа и обозначают (G). Если (G)=2, то граф называют бихроматическим. Необходимым и достаточным условием бихроматичности является отсутствие в графе циклов нечетной длины.

Граф на рис. 19а – бихроматический, его вершины «раскрашены» двумя «цветами», обозначенными 0,1.

Рис. 19. Примеры раскраски графов

Граф на рис. 19б можно «раскрасить» тремя цветами, например, черным (ч), красным (к) и белым (б).

Изоморфизм графов.

Как мы убедились, граф может быть задан различными способами. Он может быть изображен на чертеже, задан матрицей инцидентности, списком ребер или матрицей смежности, фактор-множеством и т.д. Вид чертежа зависит от формы линий и взаимного расположения вершин [24]. Иногда не так легко понять, одинаково ли графы, изображенные разными чертежами. Вид матриц и списка ребер зависит от нумерации вершин и ребер графа. Строго говоря, граф считается полностью заданным, если нумерация его вершин зафиксирована; графы, отличающиеся только нумерацией вершин, называются изоморфными.

Например, графы, изображенные на рис. 20, изоморфны [24].

Рис. 20. Изоморфные графы а) и б), отличающиеся

только перенумерацией вершин 51, 15

Если граф ориентированный, то направление дуг в изоморфных графах должно совпадать.

Чтобы узнать, представляют ли две матрицы смежности изоморфные графы, можно произвести всевозможные одинаковые перестановки строк и столбцов.

Если после одной из этих перестановок возникнет матрица, совпадающая с заданной, то сравниваемые графы изоморфны. Для этого требуется максимум n! перестановок, где n – число вершин графа.

Иногда для определения изоморфности определяют параметры обоих графов: число вершин, число ребер, число компонент связности, последовательность степеней вершин в убывающем порядке.

Если какие-то из этих параметров различны, то эти графы различны. Однако если все параметры у двух графов совпали, это не гарантирует изоморфности, то есть это необходимое, но не достаточное условие [24].

Так, на рис. 21 приведены два графа, у которых эти параметры совпадают, и, тем не менее, они различны [24].

Рис. 21. Пример неизоморфных графов а) и б)

На рис. 22 приведен граф, изоморфный графу «пятиконечная звезда» (см. рис. 12).

Рис. 22. Граф, изоморфный графу «пятиконечная звезда»

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

Псевдограф содержит и ребра, и дуги.

Тривиальный граф содержит только одну вершину.

Иногда граф задают в виде множества образов Г или прообразов Г^-1.

Множеством внутренней устойчивости графа называется подмножество таких его вершин, которые несмежны между собой.

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

Множество внешней устойчивости, содержащее наименьшее число вершин, называют наименьшим внешне устойчивым множеством, а число элементов этого множества – число внешней устойчивости графа.

Операции над графами.

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

Вводятся также операции объединения графов, когда объединяются множества вершин и заданных на них отношений; соединение графов, когда находится пересечение указанных множеств.

Используются и такие операции, как удаление вершины, удаление ребра, добавление вершины, добавление ребра.

В настоящее время в ЭВМ графы чаще всего задаются списками смежности и массивом указателей на эти списки [26].

Задачи на графах могут быть решены, например, системой компьютерной математики Matematica (3,4) фирмы Wolfram Research,Inc. – пакет расширения «Дискретная математика» (DiscreteMath) – представление графов, создание графов, свойства графов, алгоритмическая теория графов.