Минимальное остовное дерево: различия между версиями

Минимальное остовное дерево (посмотреть исходный код)

4 байта добавлено , 22 декабря 2015

м

4511

правок

Версия от 19:31, 22 декабря 2015 (просмотреть исходный код) Irina (обсуждение \| вклад) м (→‎Основные результаты) ← Предыдущая правка		Версия от 19:32, 22 декабря 2015 (просмотреть исходный код) Irina (обсуждение \| вклад) м (→‎Основные результаты) Следующая правка →
Строка 47:		Строка 47:


	'''Приближенная сжимаемость'''. Рассмотрим граф G', полученный из G при помощи увеличения веса некоторых ребер. Если C является сжимаемым относительно G', то <math>MST(G) = MST(MST(C) \cup MST(G \backslash C) \cup E^) \;</math>, где E – множество ребер с увеличенными весами.		'''Приближенная сжимаемость'''. Рассмотрим граф G', полученный из G при помощи ''увеличения'' веса некоторых ребер. Если C является сжимаемым относительно G', то <math>MST(G) = MST(MST(C) \cup MST(G \backslash C) \cup E^) \;</math>, где E – множество ребер с увеличенными весами.