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

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

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

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

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

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

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

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

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

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

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

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

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

Литература:

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