С неор я бы делал через поиск в глубину. А с ор - вроде бы через матрицы быстрее получится. Как для орграфа?

для орграфа, наверное, достаточно проверить i-й столбец и i-ю строку (i - неважно какое)

Если у Вас ориентированный граф без «петель» (рёбер исходящих и входящих в одну и ту же вершину) и матрица смежности задаётся, например, так: 

, где, 
если m[i, j] ==  0, то ребро, соединяющее вершины i и j, отсутствует, 
если m[i, j] ==  1, то ребро выходит из вершины i в вершину j, 
если m[i, j] == -1, то ребро входит в вершину i из вершины j, 
то можно составить матрицу `a' как произведение `m' и транспонированной `m': 

и проверить, что все элементы на гланой диагонали `a' положительны: 



Это сообщение отредактировал(а) V_A_KeRneL - 16.12.2006, 22:23

а если есть оба ребра?

По-видимому ты слабо себе представляеш всякие волновые алгоритмы...

Спасибо за замечание.
Я забыл явно описать, что подобные случаи тоже не рассматриваются.
Мне показалось, что из примера видно, что ячейка таблицы (матрицы) может принимать только 3 значения: -1, 0 и 1.
Поймите меня правильно, я не претендую на универсальность решения. Просто привёл эффективное решение частного случая.

Хотя мне кажется, что ничто не мешает для такого случая ввести дополнительное обозначение, например, 2.


Составим матрицу `a': 


А теперь опять-таки проверим, что все элементы на главной диагонали матрицы `a' положительны: 


Главный недостаток такого расширения следующий. Теряется главный смысл описанной операции. А он был таков: после умножения матрицы на транспонированную значения на главной диагонали (m[i, i]) показывают общую степень i-ой вершины графа по входу и по выходу.

З.Ы. Я поправил адресацию к элементу матрицы в своём коде. В Ruby (именно на этом языке у меня приведены фрагменты программы) обращение m[i][j] осуществляется, если `m' -- массив (Array), а для матрицы (Matrix) правильно будет так: m[i, j].


Это сообщение отредактировал(а) V_A_KeRneL - 16.12.2006, 22:29

даже если предположить, что не бывает таких рёбер (в принципе, по середине каждого одного ребра из такой пары можно поставить фиктивную вершину, что не изменит связности графа), то всё равно остаются непонятности:

A=m*tr(m)
a[i,i]=sum[n=1..N] m[i,n]*( tr(m) )[n,i]=sum[n=1..N] m[i,n]*m[i,n] >=0
так что не представляю себе такой матрицы, которая дала бы отрицательные числа на диагонали такого произведения (да и нули даст разве что нулевая)

второе соображение:
если граф будет состоять из двух связных компонент, то вершины можно перенумеровать так, что матрица будет блочной, операции транспонирования и умножения не меняют блочности и действуют независимо на каждый блок, так что из связности каждой компоненты будет следовать положительность диагональных элементов внутри блока, а значит, и для всей матрицы, а отсюда уже будет следовать связность всего графа, что не выполняется

А вот такая проверка: 

  

Это сообщение отредактировал(а) Elfet - 16.12.2006, 20:09

Вот что получилось: Graph Simple 

Отрицательных элементов действительно не получится. А нулевые получатся в том случае, если i-ая строка, а, соответственно, и i-ый столбец тоже, исходной матрицы `m' нулевые.









А вот тут Вы, похоже, правы.
Для графа с двумя связными компонентами мы получим блочную матрицу, оба побочных компонента (блока) которой будут нулевыми.
И тут мой алгоритм, действительно, даст неправильный ответ.

...

Что неверно.

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

maxim1000, спаибо за ещё одно ценное замечание.

З.Ы. Elfet, спасибо за готовую прогу!


Это сообщение отредактировал(а) V_A_KeRneL - 16.12.2006, 23:22