Остовом 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. Кодерево графа
