LINUX.ORG.RU
Форум — Development  

Проблема с графом

 


0

2

Есть связанный взвешенный граф с положительными весами.

Нужно найти подграф минимального размера такой, что все вершины, не вошедшие в новый граф доступны за один переход из вершины нового графа.

Минимальный или близкий к минимальному - не так важно.

Есть какой-нибудь стандартный алгоритм для этой задачи?

★★★★
← размер бинарников avr-gcc
Golang в Atom'е (настройка) →

Первое что приходит в голову - взять все вершины, имеющие более одного соседа. Только не факт, что он минимальный. Можно его итеративно уменьшать... до тех пор пока будет соблюдаться условие.

BattleCoder ★★★★★
()
Последнее исправление: BattleCoder (всего исправлений: 3)

положительными _весами_
подграф минимального _размера_

Уж, определитесь. А по сабжу - не знаю, ну можно попробовать ребрам веса пририсовать (сумма вершин) -> минимальное остовное дерево -> выкинуть листья (для каждого сохравнив множество V оставшихся верших из которого лист достижим) -> продолжать выкидывать (в общем случае дерево распадается), пока удаление любой вершины не сделает пустым какое-либо V (Но это вилами по воде.)

anonymous
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.
← размер бинарников avr-gcc
Development
Golang в Atom'е (настройка) →