Свойства

• Дерево не имеет кратных рёбер и петель.

• Любое дерево с вершинами содержитребро. Более того, конечный связный граф является деревом тогда и только тогда, когда, где— число вершин,— число рёбер графа.

• Граф является деревом тогда и только тогда, когда любые две различные его вершины можно соединить единственной простой цепью.

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

• Любое дерево является двудольным графом. Любое дерево, множество вершин которого не более чем счётное, является планарным графом.

• Для любых трёх вершин дерева, пути между парами этих вершин имеют ровно одну общую вершину.

17. Задача Штейнера. Остовное дерево

Задача Штейнера состоит в поиске минимального дерева Штейнера — кратчайшей сети, соединяющей заданный конечный набор точек плоскости. Свое название получила в честь Якоба Штейнера (1796—1863).

Опр. Остовным деревом связного графа G называется любой его подграф, содержащий все вершины графа G и являющийся деревом.

Пусть G – связный граф. Тогда остовное дерево графа G должно содержать n(G)-1 ребер. Значит, для получения остовного дерева из графа G нужно удалить ребер. Числоназывается цикломатическим числом графаG.

Алгоритм выделения остовного дерева

1) Выберем в G произвольную вершину , которая образует подграф, являющийся деревом. Положимi=1.

2) Если i=n(G), то задача решена и G_i – искомое остовное дерево графа G. Иначе переходим к п. 3.

3) Пусть уже построено дерево являющееся подграфом графаG, в которое входят вершины , где. Строим граф, добавляя к графуG_i новую вершину , смежную с некоторой вершинойграфаи новое ребро. Во-первых, это можно всегда сделать, поскольку граф связен. Во-вторых,- дерево, т.к. если вне было циклов, то и вих не могло появиться.

Присваиваем i:=i+1 и переходим к шагу 2).

Замечание. Остовное дерево может быть выделено, вообще говоря, не единственным способом.

Если граф – нагруженный, то можно выделить остовное дерево с минимальной суммой длин содержащихся в нем ребер.

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

1) Выберем в графе G ребро минимальной длины. Вместе с инцидентными ему двумя вершинами оно образует подграф G₂ графа G. Положим i=2.

2) Если i=n(G), то задача решена и G_i – искомое минимальное ост. дерево графа G. Иначе переходим к шагу 3).

3) Строим граф G_i+1, добавляя к графу G_i новое ребро минимальной длины из оставшихся, которое инцидентно какой-нибудь верш. графа G_i и одновременно вершине, не содержащейся в G_i. Вместе с этим ребром включаем в G_i+1 и эту инцидентную ему верш. Присваиваем i:=i+1 и переходим к шагу 2).

39. Алгоритм Краскала

Алгоритм построения минимального остовного дерева взвешенного связного неориентированного графа. Вначале текущее множество рёбер устанавливается пустым. Затем, пока это возможно, проводится следующая операция: из всех рёбер, добавление которых к уже имеющемуся множеству не вызовет появление в нём цикла, выбирается ребро минимального веса и добавляется к уже имеющемуся множеству. Когда таких рёбер больше нет, алгоритм завершён. Подграф данного графа, содержащий все его вершины и найденное множество рёбер, является его остовным деревом минимального веса.