Связующее дерево и минимальное связующее дерево

В этом руководстве вы узнаете о связующем дереве и минимальном связующем дереве с помощью примеров и рисунков.

Прежде чем мы узнаем о покрывающих деревьях, нам нужно понять два графа: неориентированные графы и связанные графы.

Неориентированный граф представляет собой график , в котором ребро не указует в любом направлении (то есть. Края являются двунаправленными).

Ненаправленный граф

Связный граф представляет собой график , в котором всегда есть путь от вершины до любой другой вершины.

Связанный график

Остовное дерево

Остовное дерево - это подграф неориентированного связного графа, который включает в себя все вершины графа с минимально возможным количеством ребер. Если вершина пропущена, то это не остовное дерево.

Края могут иметь или не иметь веса.

Общее количество остовных деревьев с nвершинами, которые могут быть созданы из полного графа, равно .n(n-2)

Если есть n = 4, максимальное количество возможных остовных деревьев равно . Таким образом, из полного графа с 4 вершинами можно сформировать 16 остовных деревьев.44-2 = 16

Пример связующего дерева

Давайте разберемся с остовным деревом на примерах ниже:

Пусть исходный граф будет:

Нормальный график

Некоторые из возможных покрывающих деревьев, которые могут быть созданы из приведенного выше графика:

Остовное дерево Остовное дерево Остовное дерево Остовное дерево Остовное дерево Остовное дерево

Минимальное связующее дерево

Минимальное остовное дерево - это остовное дерево, в котором сумма веса ребер минимальна.

Пример связующего дерева

Давайте разберемся с приведенным выше определением с помощью примера ниже.

Исходный график:

Взвешенный график

Возможные остовные деревья из приведенного выше графика:

Минимальное остовное дерево - 1 Минимальное остовное дерево - 2 Минимальное остовное дерево - 3 Минимальное остовное дерево - 4

Минимальное остовное дерево из вышеперечисленных остовных деревьев:

Минимальное остовное дерево

Минимальное остовное дерево из графа находится с использованием следующих алгоритмов:

  1. Алгоритм Прима
  2. Алгоритм Крускала

Приложения связующего дерева

  • Протокол маршрутизации компьютерной сети
  • Кластерный анализ
  • Планирование гражданской сети

Минимальные приложения связующего дерева

  • Чтобы найти пути на карте
  • Для проектирования таких сетей, как телекоммуникационные сети, сети водоснабжения и электрические сети.

Интересные статьи...