Деревья и ордеревья

Определение: Связный граф без циклов называется деревом.

Теорема. Для графа Х с n – вершинами следующие условия эквивалентны:

1) Х является деревом

2) любые две вершины соединенные единственной простой цепью.

3) граф связен и имеет n – 1 ребро дерева.

4) граф не содержит циклов и имеет n –1 ребро.

5) граф не содержит циклов, но добавление любого нового ребра приводит к появлению цикла.

6) граф связен, но утрачивает связность при удалении любого ребра.

Определение: Орграф называется ордеревом с корнем Х ₀, если:

1) в Х₀ не заходит ни одна дуга;

2) в остальные вершины заходит единственная дуга

3) орграф не содержит контуров.

Х₀

Ордерево

Предложение. Если в ордереве «стереть стрелки» то получится дерево.

Замечание. Понятие корня у дерева отсутствует.

В теории графов рассматриваются не жесткие объекты (топологические объекты) можно растягивать ребра и дуги, изгибать их, поворачивать. нельзя лишь менять количество вершин и их соединение.

Дата добавления: 2014-01-06