Как быстрее оставить граф без ребер?

[ellipse]

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

[venco]

ellipse в сообщении #483627 писал(а):

Верно ли, что наилучший алгоритм на каждом шаге выбирает вершину с наибольшим числом ребер?

Неверно:

A-B-C-D-E
    |
  G-F

[Sonic86]

http://e-science.ru/forum/index.php?showtopic=33774
Это стандартная NP-задача о вершинном покрытии. Гуглите.