Тема: Построение остовного дерева минимальной длины

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

Если в маршруте не повторяются ребра, то он называется цепью.

Если в цепи не повторяются вершины, то он называется простой цепью.

Цепь, в которой первая и последняя вершины совпадают – называется циклом.

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

Связанный граф, не содержащий циклов, называется деревом.

Граф, не имеющий циклов, называется лесом.

Граф, который не имеет ни одного ребра, называется простым.

Граф H называется подграфом графа G, если вершины и ребра графа H принадлежат графу G.

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

Если каждому ребру (дуге) () поставлено в соответствие некоторое число ω(), то граф G называется графом со взвешенными ребрами (дугами). Число ω() называется весом ребра (дуги).

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

1) К пустому графу прибавим ребро минимальной длины и получим граф .

2) Пусть построен граф , тогда граф = + , где – ребро, не принадлежащее и не образующее цикла с ребрами графа .

3) - искомое дерево.

4) Построить остовное дерево.

Пример:

Решение:

Ответ:

G’={(x1,x4);(x3,x6);(x2,x3);(x2,x5);(x1,x2);(x5,x7)}

μ(G’)=100+100+150+170+200+210=930

Алгоритм Прима:

1) Выберите произвольную вершину и ребро, соединяющее её с ближайшим по весу соседом.

2) Найдите не присоединённую вершину ближе всего лежащую к одной из присоединённых и соедините с ней.

3) Повторяйте шаг 2 до тех пор, пока все вершины не будут присоединены.

Решение:

Задание 1: Задана матрица весов (из омег). Построить остовное дерево минимальной длины.

			v1	v2	v3	v4	v5	v6	v7
		v1	-		∞		∞	∞	∞
		v2		-				∞
		v3	∞		-	∞
Ω	=	v4			∞	-	∞		∞
		v5	∞			∞	-
		v6	∞	∞				-
		v7	∞			∞			-

Ответ:

G’={(v1,v2);(v2,v3);(v2,v5);(v4,v6),(v5,v6),(v6,v7)}

μ(G’)=2+1+4+3+4+4=18