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

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

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

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

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

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

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

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

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

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

n(G)=m-n+1.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Граф G называют р-хроматическим, где р – натуральное число, если его вершины можно раскрасить р различными цветами так, чтобы никакие две смежные вершины не были раскрашены одинаково. Наименьшее число р, при котором граф является р-хроматическим, называют хроматическим числом графа и обозначают l(G). Если l(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.

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

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

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