Алгоритм построения всех остовных деревьев графа на основе полного перебора последовательности ребер или дуг

· Все ребра(дуги) перенумеровываются.

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

· Строится дерево. Если очередное ребро (дуга) увеличивает дерево, оно включается в дерево, если ребро приводит к образованию цикла, то оно вычеркивается. Если дуга образует два пути в одну вершину, то она вычеркивается. Если ребро(дуга) не увеличивает дерево, то оно вносится в список «пропущенное ребро».

· После каждого включения ребра(дуги) дерева просматривается список «пропущенное ребро». После использования пропущенного ребра оно вычеркивается из списка. Ребро вычеркивается из списка «пропущенное ребро» также и в том случае, если пропущено ребро(дуга) приводит к образованию цикла (для неориентированного графа) или к двум путям (ориентированный граф).

· Пункт 3-4 повторяется, для того, чтобы убедиться в том, что полученное дерево – остовное дерево для ориентированного графа.

· Новое дерево заносится в память.

· Если число остовных деревьев меньше максимального, то перейти к пункту 3.

1. Все ребра пронумеруем.

2. а)а₁ а₂ а₃ а₄ а₅ а₆ а₇ а₈ а₉ а₁₀

б)а₆ а₇ а₈ а₉ а₁₀ а₁ а₂ а₃ а₄ а₅

а) х2 а₂ б) х2 а₂

а₁ х3 а₁ х3

х1 а₃ х1

а₅ х4

х4 х5

а₉ а₇ а₉ а₇ а₆

х6 х5

х6

х7

х7

Для получения кратчайшего остовного дерева необходима длительность ребер(дуг) выставить по возрастанию и построить остовное дерево.

Дата добавления: 2015-08-21