Деревья Штейнера: различия между версиями

Если множество <math>\mathcal{F} \;</math> состоит из всех полных компонентов размером не более 3, этот жадный алгоритм дает на выходе 3-ограниченное дерево Штейнера, введенное Зеликовским [14]. Если <math>\mathcal{F} \;</math> состоит из всех трехлучевых звезд и всех ребер (где трехлучевая звезда представляет собой дерево с 3 листьями и центральной вершиной), то этот жадный алгоритм дает на выходе итеративное 1-дерево Штейнера. Интересный факт, на которой обратили внимание Ду и коллеги [9], заключается в том, что функция gain(<math>\cdot</math>) является субмодулярной над всеми полными компонентами размера не более 3, но не является субмодулярной над всеми трехлучевыми звездами и ребрами.