Пример 3. Определение. Маршрутом длины на графе называется такая последовательность

3.2. Маршруты, цепи и циклы в графе

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

Такой маршрут кратко называют - маршрутом и кратко обозначают . Про - маршрут говорят, что он соединяет вершину с вершиной . Вершины и называют соответственно началом и концом маршрута.

Случай, когда длина маршрута равна нулю, не исключается; в этом случае маршрут сводится к одной вершине.

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

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

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

Определение. Цепь – это маршрут без повторяющихся ребер.

Цепь, соединяющую вершину с вершиной , кратко называют - цепью и обозначают .

Определение. Цепь называется простой, если в ней нет повторяющихся вершин за исключением, быть может, совпадающих концевых.

Определение. Замкнутая цепь называется циклом.

Определение. Замкнутая простая цепь называется простым циклом.

Пример 1. - - маршрут; его длина равна 4; данный маршрут является - цепью; эта цепь незамкнутая, не простая. Маршрут - цикл длины 5, этот цикл не является простым; - простой цикл.

3.3. Связность, компоненты связности графа

Определение. Обозначим через G_i подграф графа G, порожденный множеством вершин V_i. При этом

Графы называют компонентами связности графа G.

Определение. Число различных компонент связности графа называется числом связности и обозначается .

Определение. Если , то граф называется связным.

Пример 1. Рассмотрим граф , с множеством вершин , множеством ребер и отображением инцидентности: , , , . Имеем три компоненты связности:

1. , где , , , , ;

2. , где , ;

3. , где , , .

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

Пусть - произвольный граф; - число его вершин, - число ребер, - число связности.

Определение. Поставим графу в соответствие число , называемое цикломатическим числом графа.

3.5. Матрицы, ассоциированные с графом

Во многих задачах теории графов (особенно реализуемых на ЭВМ) графы удобно описывать матрицами. Пусть - произвольный неориентированный граф с m вершинами и n ребрами. Занумеруем вершины графа.

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

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

Помимо вершин занумеруем ребра графа.

Определение. Матрицей инцидентности неориентированного графа называется матрица размера , элементы которой определены следующим:

1. , если вершина с номером i инцидентна ребру с номером j и j-ое ребро не является петлей;

2. во всех остальных случаях.

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

Пример. ; .

3.6. Деревья и леса

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

Определение. Связный ациклический граф называется деревом.

Каждая компонента связности леса – дерево, следовательно, для -связного леса существует дизъюнктное разбиение на деревьев.

Пример 1. Граф не является деревом, не является лесом. Граф - дерево. Граф - лес.

Теорема. Связный граф является деревом тогда и только тогда, когда .

Следствие. Если граф --связный лес, то .

Дата добавления: 2014-01-03