Ориентированные деревья

Орграф называется ориентированным деревом (ордеревом), если

1. существует единственный узел, полустепень захода которого равна 0 (корень),

2. полустепень захода остальных узлов равна 1,

3. все узлы достижимы из корня.

Пример.

• • • •

• • • • • • •

• • •

•

•

Рис. 59. Ордеревья с 4 узлами

Остальные ордеревья с 4 узлами изоморфны графам на рис. 59.

Теорема. Свойства ордеревьев.

1.Если q – число дуг, а p – число узлов оррдерева, то q = p - 1.

2. Если в оррдереве отменить ориентацию ребер, то получится свободное дерево.

3. В оррдереве нет контуров.

4. Для каждого узла существует единственный путь из корня.

5. Если в свободном дереве любую вершину назначить корнем, то получится оррдерево.

Доказательство.

1. Т.к. в каждый узел, кроме корня, заходит единственная дуга (п. 1, 2 определения), то q = p - 1

2. Отмена ориентации в оррдереве приведет к созданию связного дерева (иначе нарушается п.3 определения). Из доказанного свойства 1 следует, что этот граф древовиден. Граф связен и древовиден, значит, он – дерево.

3. Если допустить в ордереве наличие контуров, то при отмене ориентации получится граф с циклами, т.е. не дерево, что противоречит свойству 2.

4. Если предположить наличие двух путей для некоторого узла, то при отмене ориентации получится граф с циклами, т.е. не дерево, что противоречит свойству 2.

5. Пусть вершина u назначена корнем. Инцидентные с ней ребра ориентируем в глубину. Т.к. для любой вершины v существует единственная цепь, соединяющая u и v, то полустепень захода d ⁺(v) = 1 v, и каждый узел достижим из корня.

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