Остов и кодерево

Остовом Tграфа G называется называется подграф графа в виде дерева, содержащий все его вершины. Остов определяет каркас графа. Кодеревом T^* остова Т называется подграф графа G, содержащий все вершины и только те ребра, которые не входят в остов Т. Ребра остова называют ветвями, а ребра кодерева - хордами.

Из определений остова и кодерева следует:

1. Объединение остова T и кодерева T^* есть граф G:

Т ÈT^* = G.

2. Кодерево есть дополнение остова T до графа G:

T^* = G \ Т =`Т.

Рассмотрим пример графа, изображенного на рис. 3.30.

Рис. 3.30. Граф

Выберем остов графа в виде связного дерева (рис. 3.31).

 

Рис. 3.31. Остов графа

Кодерево для данного остова имеет вид несвязного графа (рис. 3.32), но он может быть и связным.

 

Рис. 3.32. Кодерево графа