4551
правка
Лес Штейнера: различия между версиями
Перейти к навигации
Перейти к поиску
м
нет описания правки
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) мНет описания правки |
||
| Строка 8: | Строка 8: | ||
== Формальное определение и нотация == | == Формальное определение и нотация == | ||
Экземпляр задачи построения леса Штейнера I = (G, c, R) составляют неориентированный граф G = (V, E) с множеством вершин V и множеством ребер E, неотрицательная стоимостная функция <math>c: E \to Q^+ \;</math> и множество пар вершин <math>R = \{ (s_1, t_1 ), ..., (s_k, t_k) \} \subseteq V \times V \;</math>. Пары в множестве R называются ''парами полюсов''. Допустимое решение задачи представляет собой подмножество <math>F \subseteq E \;</math> ребер графа G, такое, что для каждой пары полюсов <math>(s_i, t_i) \in R \;</math> существует путь между <math>s_i \;</math> и <math>t_i \;</math> в подграфе G[F], порожденном F. Пусть [[стоимость]] c(F) определяется как суммарная стоимость всех ребер в F, т.е. <math>c(F) = \sum_{e \in F} c(e) \;</math>. Задача заключается в нахождении допустимого решения F с минимальной стоимостью c(F). Легко заметить, что существует оптимальное решение, являющееся лесом. | Экземпляр задачи построения леса Штейнера I = (G, c, R) составляют неориентированный граф G = (V, E) с множеством вершин V и множеством ребер E, неотрицательная стоимостная функция <math>c: E \to \mathbb{Q}^+ \;</math> и множество пар вершин <math>R = \{ (s_1, t_1 ), ..., (s_k, t_k) \} \subseteq V \times V \;</math>. Пары в множестве R называются ''парами полюсов''. Допустимое решение задачи представляет собой подмножество <math>F \subseteq E \;</math> ребер графа G, такое, что для каждой пары полюсов <math>(s_i, t_i) \in R \;</math> существует путь между <math>s_i \;</math> и <math>t_i \;</math> в подграфе G[F], порожденном F. Пусть [[стоимость]] c(F) определяется как суммарная стоимость всех ребер в F, т.е. <math>c(F) = \sum_{e \in F} c(e) \;</math>. Задача заключается в нахождении допустимого решения F с минимальной стоимостью c(F). Легко заметить, что существует оптимальное решение, являющееся лесом. | ||
Задачу построения леса Штейнера можно определить альтернативным образом при помощи не пар, а групп полюсов <math>R = \{ g_1, ..., g_k \} \;</math>, где <math>g_i \subseteq V \;</math>. Задача заключается в вычислении подграфа с минимальной стоимостью, такого, что все полюса, принадлежащие к одной и той же группе, связаны друг с другом. Определение эквивалентно предыдущему. | Задачу построения леса Штейнера можно определить альтернативным образом при помощи не пар, а групп полюсов <math>R = \{ g_1, ..., g_k \} \;</math>, где <math>g_i \subseteq V \;</math>. Задача заключается в вычислении подграфа с минимальной стоимостью, такого, что все полюса, принадлежащие к одной и той же группе, связаны друг с другом. Определение эквивалентно предыдущему. | ||
== Родственные задачи == | == Родственные задачи == | ||