11.5. деревья

11.5. деревья

Связный граф, не содержащий циклов, называется деревом.

Деревом некоторого графа G называется его связный подграф без циклов. Дерево графа G, содержащее все его вершины, называется остовом графа G или его покрывающим деревом.

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

На рис. 11.6 представлены граф G, его дерево Gv остов Тх и ко-дерево Т[.

Теорема. Граф Gen вершинами является деревом тогда и только тогда, когда G — связный граф и число его ребер равно (и 1).

Ребра остова Т называются ветвями графа G, а ребра кодере-ва — Т*-связями.

311