Поиск разделяющих вершин в произвольном графе...

[Agnazar]

В общем, задача звучит следующим образом:
Найти все разделяющие вершины в произвольном графе...

В некоторой литературе в инете нашел их(разделяющие вершины то есть) как точки связности.
Примечание: Вершина - разделяющая, если при удалении ее граф становится насвязным.

Помогите пожалуйста хотя бы с общим описанием концепции =)
Писать буду под Delphi. Хотя если кто-то что-то на Basic/C++ покажет тоже пойму.
Спасибо!

[alexBlack]

Сообщение от Agnazar

В общем, задача звучит следующим образом:
Найти все разделяющие вершины в произвольном графе...

В некоторой литературе в инете нашел их(разделяющие вершины то есть) как точки связности.
Примечание: Вершина - разделяющая, если при удалении ее граф становится насвязным.

Помогите пожалуйста хотя бы с общим описанием концепции =)
...

Нужно реализовать функцию для проверки графа на связность.
Начинаем с любой вершины. Включаем в список вершины, которые с ней
связаны и которых еще нет в списке. Для этих вершин рекурсивно
делаем то-же самое. Если после выполнения в списке окажутся все
вершины графа, то граф связан.

Теперь для всех вершин делаем следующее:
удаляем ее из графа. Если граф стал несвязанным, то это наша вершина.
Восстанавливаем граф и переходим к следующей вершине.

[Agnazar]

1. Простите за дурацкие вопросы, но как их помечать? (добавлять в список)
2. Как сформировать подходящий для этой задачи граф? Чтобы таких точек было немного...

Просто с графами как-то не приходилось работать и литературы подходящей не узрел...

[alexBlack]

Сообщение от Agnazar

2. Как сформировать подходящий для этой задачи граф? Чтобы таких точек было немного...

Просто с графами как-то не приходилось работать и литературы подходящей не узрел...

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

type
    PNode = ^TNode;
    TNode = record 
        P : boolean;
        Link : array [1..10] of PLink;   // Связи с другими вершинами 
    end;
    
    //  Сами вершины можно хранить в массиве
var Graf : array [1..10] of PNode;

... как их помечать? (добавлять в список)

Можно обойтись без списка. Поле P в вершине графа будет меткой.
Дальше действуем примерно так:

//сначала очищаем все метки
for i:=1 to countNode do Graf[i]^.P := false;

// Маркируем вершины, связанные с первой:
_markSv(Graf[1]);
// Проверяем метки у всех вершин
// Если есть хотя-бы одна не помеченная, значит граф не связанный

//Функция для проверки связанности:
procedure _markSv(P:PNode);
begin
    P.P := true;   // помечаем саму вершину 
    // Рекурсивно проходим по всем связанным вершинам
    for i:=1 to 10 do begin
       P1 := P.Link[i];
       if not P1.P then _markSv(P1);
    end;
end;

[Agnazar]

спасибо большое