Теория графов. Дерево


Дерево – это граф без циклов (рис. 2.16).

«Лес» - это компоненты дерева. Деревья образуют лес.

1-derevo-teoriia-grafov

Рисунок 2.16 – Пример дерева.

Высотой дерева называется длина его самого длинного пути.

Свойство 1. Если у дерева е ребер и v вершин, то

 4-derevo-teoriia-grafov

Свойство 2. У каждого дерева существует основное дерево, которое составляет основу (рис.2.17).

 2-derevo-teoriia-grafov

Рисунок 2.17 – Основное дерево дерева (рис 2.16).

Пример. Дилерская сеть в разные города (рис 2.18).

3-derevo-teoriia-grafov

Рисунок 2.18 – Граф дилерской сети.

Чтобы получить из этого графа дерево, необходимо «подвешивать» его за одну высоту. Как правило, наиболее логично подвешивать «дерево» за высоту с наименьшей длиной.

 

Разрезающее множество графа – это множество ребер, удаление которых нарушает его связность.

Вершина графа является разрезающей, если удаление ее и связанных с ней ребер нарушает связность графа.

Литература:

  1. Шевченко В.В. Конспект лекций по курсу "Логистика". Донецк, ДонНТУ - 2009 г.
  2. Ткачук А.Н. Конспект лекций по курсу "Логистика". Донецк, ДонНТУ - 2008 г.


Категории: Логистика  

Об этой статье

teoriia-grafov-derevo-avatar
2017-11-02 12:51:49
873
user
Логистика; Лекции; Теория графов;
В статье рассматривается дерево в теории графов