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