Графы. Удаление вершин в графе.

[morozixa939]

Помогите, плиз....с написание программы С ++(Желательно).....Суть программы: в каком порядке нужно удалять вершины графа, чтобы не нарушать связность графа.

[Abstraction]

Если в графе удалить вершину степени 1 (или 0), связность не нарушится.
Если таких вершин нет, это хуже. Но, к примеру, если каждой вершине сопоставить максимум длин кратчайших путей до других вершин, то вершину с максимальным таким числом можно удалить.
Также если от любой вершины, инцидентной с А, можно дойти до любой другой инцидентной с А, не проходя через А, то А можно удалить (это условие относительно легко проверить для вершин степени 2).