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; в —ко-лес Г.