11

Нахождение остова наименьшего веса

Остовы в графе

Пусть дан связный граф G = (V ; E) с n вершинами и m ребрами.

Нахождение остова наименьшего веса

Остовы в графе

Пусть дан связный граф G = (V ; E) с n вершинами и m ребрами. Тогда m n 1.

Нахождение остова наименьшего веса

Остовы в графе

Пусть дан связный граф G = (V ; E) с n вершинами и m ребрами. Тогда m n 1. Если m = n 1; то G является деревом.

Нахождение остова наименьшего веса

Остовы в графе

Пусть дан связный граф G = (V ; E) с n вершинами и m ребрами. Тогда m n 1. Если m = n 1; то G является деревом. Если m > n 1; то в G имеется ребро e 2 E, не являющееся мостом.

Нахождение остова наименьшего веса

Остовы в графе

Пусть дан связный граф G = (V ; E) с n вершинами и m ребрами. Тогда m n 1. Если m = n 1; то G является деревом. Если m > n 1; то в G имеется ребро e 2 E, не являющееся мостом. Тогда граф G0 = (V ; E0), где

E0 = E n feg:

снова является связным.

Нахождение остова наименьшего веса

Остовы в графе

Пусть дан связный граф G = (V ; E) с n вершинами и m ребрами. Тогда m n 1. Если m = n 1; то G является деревом. Если m > n 1; то в G имеется ребро e 2 E, не являющееся мостом. Тогда граф G0 = (V ; E0), где

E0 = E n feg:

снова является связным.

Повторив эту процедуру m (n 1) раз получим граф G0 = (V ; E0), E0 E, являющийся деревом.

Нахождение остова наименьшего веса

Остовы в графе

Пусть дан связный граф G = (V ; E) с n вершинами и m ребрами. Тогда m n 1. Если m = n 1; то G является деревом. Если m > n 1; то в G имеется ребро e 2 E, не являющееся мостом. Тогда граф G0 = (V ; E0), где

E0 = E n feg:

снова является связным.

Повторив эту процедуру m (n 1) раз получим граф G0 = (V ; E0), E0 E, являющийся деревом.

Определение. Дерево T = (V ; P) называется остовом связного графа G = (V ; E), если P E.

Нахождение остова наименьшего веса

Взвешенные графы и задача об остове наименьшего веса

Определение. Взвшенный граф граф G = (V ; E) с заданной функцией : E ! R. Величина (e) называется весом ребра e 2 E.

Нахождение остова наименьшего веса

Взвешенные графы и задача об остове наименьшего веса

Определение. Взвшенный граф граф G = (V ; E) с заданной функцией : E ! R. Величина (e) называется весом ребра e 2 E.

Задача. По данному связному взвешенному графу

G = (V ; E; ) найти остов T = (V ; P) такой, что вес остова

X

(T ) = (e)

e2P

наименьший.

Нахождение остова наименьшего веса

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

Пусть задан связный взвешенный граф G = (V ; E; ) с n вершинами.