2.2. k-деревья, остовные k-деревья, леса

k-Деревом называется ациклический граф, состоящий из k компонент. Очевидно, что каждая компонента k-дерева сама является деревом. Заметим, что k-дерево совпадает с деревом.

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

-Кодеревом Т остовного -дерева Т графа G является остовный подграф графа G, содержащий точно те ребра, которых нет в Т.

Например, граф на рис. 2.2, б является -деревом графа G, представленного на рис. 2.2, а. Остовное -дерево Т графа G и соответствующее 3-кодерево Т показаны на рис. 2.2, в, г.

Рис. 2.2. Иллюстрация определения -дерева, остовного -дерева и -кодерева. а — граф -дерево графа в — остовиое -дереао Т графа г — -кодерево Т.

Обозначим 6 компонент остовного -дерева графа G на вершинах через Если — число вершин в то Поскольку каждое является деревом, то по теореме 2.1 имеем где число ребер в Таким образом, общее число ребер остовного -дерева Т равно Если — число ребер в G, то -кодерево Т будет иметь ребер.

Лесом графа G называется остовное -дерево графа G, где — число компонент в G. Если граф G имеет компонент, тогда для любого остовного -дерева графа Так как лесом Т графа G является остовное -дерево графа необходимо, чтобы каждая компонента Т была остовом одной из компонент G. Таким образом, лес Т графа компонентами состоит из таких компонент что — есть остов

Ко-лес Т леса Т графа G — это остовный подграф графа G, содержащий точно те ребра G, которые не входят в Т.

Отметим, что понятия «лес» и «остов» являются синонимами по отношению к связному графу. Лес Т и соответствующий ко-лес Т графа представлены на рис. 2.3.

Рис. 2.3. Лес и ко-лес. а — граф G; б — лес Г графа G; в —ко-лес Г.

2.3. Ранг и дипломатическое число

Рассмотрим граф G на вершинах и ребрах, содержащий k компонент. Ранг графа G, обозначаемый через , определяется как . Цикломатическое число графа G, обозначаемое определяется как . Заметим, что . Из определения леса и колеса следует, что ранг графа равен числу ребер леса графа G, а цикломатическое число — числу ребер ко-леса графа G. Ранг и цикломатическое число являются одними из наиболее важных характеристик графа. Как мы увидим в гл. 4, они определяют размерность подпространств циклов и разрезов графа.