Изменения

Перейти к: навигация, поиск

Алгоритм Борувки

66 байт добавлено, 18:14, 15 декабря 2012
Доказательство корректности
|id=lemma1
|statement=Рассмотрим связный неориентированный взвешенный граф <tex> G = (V, E) </tex> с весовой функцией <tex>w : E \to \mathbb{R}</tex>.
Для каждой вершины введем ребро <tex>me(u) = \min \limits_{tu uv \in E}w(tuuv)</tex>. Тогда <tex>T = \bigcup\limits_{u \in \mathbb{V}} e(u)</tex>
|proof=доказательство (необязательно)
Анонимный участник

Навигация