Теория графов. Дерево
Дерево – это граф без циклов (рис. 2.16).
«Лес» - это компоненты дерева. Деревья образуют лес.
Рисунок 2.16 – Пример дерева.
Высотой дерева называется длина его самого длинного пути.
Свойство 1. Если у дерева е ребер и v вершин, то
Свойство 2. У каждого дерева существует основное дерево, которое составляет основу (рис.2.17).
Рисунок 2.17 – Основное дерево дерева (рис 2.16).
Пример. Дилерская сеть в разные города (рис 2.18).
Рисунок 2.18 – Граф дилерской сети.
Чтобы получить из этого графа дерево, необходимо «подвешивать» его за одну высоту. Как правило, наиболее логично подвешивать «дерево» за высоту с наименьшей длиной.
Разрезающее множество графа – это множество ребер, удаление которых нарушает его связность.
Вершина графа является разрезающей, если удаление ее и связанных с ней ребер нарушает связность графа.
Литература:
- Шевченко В.В. Конспект лекций по курсу "Логистика". Донецк, ДонНТУ - 2009 г.
- Ткачук А.Н. Конспект лекций по курсу "Логистика". Донецк, ДонНТУ - 2008 г.
