У меня есть матрица смежности орграфа. Как определить связанный или нет?   

1.обходиш граф.
2.смотриш, все ли вершины помеченны.

 Я помню был какой то способ с перемножением матриц смежности. Меня он более всего интересует 

ну тогда можно рассмотреть такую операцию:
берём вектор, в котором будем хранить, до каких вершин уже добрались
под умножением матрицы будем понимать вектор, показывающий до каких вершин можно добраться если иметь возможность делать один шаг по рёбрам (будем считать, что по главной диагонали матрицы стоят 1)
тогда получается, что каждый элемент нового вектора:
Y[n]=OR[i=1..N] ( X[i] and M[n,i] )
эта операция задаёт "умножение" матрицы на вектор - Y=M*X
большинство нужных свойств выводятся из ассоциативности, дистрибутивности и коммутативности операций or/and аналогично операциям +/*

так что берём вектор с одной 1-цей, действуем на него N раз матрицей M и проверяем в нём наличие нулей, если есть - значит, это изолированные вершины (от первой), если нет - весь граф связный

P.S.
подозреваю, можно перевести это всё просто на умножение матриц
потом посмотреть, что это просто возведение в N-ю степень
в том виде, в котором оно представлено выше - количество умножений N
но само по себе возведение в степень можно сделать за log N шагов:
(в качестве иллюстрации)

Ок!  Спасибо!    

Граждане! А вам знакомы такие алгоритмы как обход в ширину и глубину?!! Выкладываю вам текст из Окулова:

3.2.2. Поиск в ширину
Идея метода. Суть (в сжатой формулировке) заключается в том, чтобы рассмотреть все вершины, связанные с текущей. Принцип выбора следующей вершины - выбирается та, которая была раньше рассмотрена. Для реализации данного принципа необходима структура данных “очередь”. 
 
    Пример. Исходный граф на левом рисунке. На правом рисунке рядом с вершинами в скобках указана очередность просмотра вершин графа.

    Приведем процедуру реализации данного метода обхода вершин графа.
    Логика просмотра вершин.
    


А вот сам алгоритм, который определяет связан граф или нет обходом в ширину:


Это сообщение отредактировал(а) maxim1000 - 12.12.2006, 01:12

Построение ПВГ для каждой вершины?  Вроде с момощью перемножения проще 

Не проще это точно. dfs легче для понимания имхо. рекурсия в пару строчек выходит. Единственное, может умножением быстрее...

ДФС, не катит в данном случае.


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

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

Странно, а у меня в ширь сложнее получился чем в глубь 

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

Ну да? В шируну тоже есть возврат из рекурсии    Но это уже оффтоп  

А можно ещё про перемножение матриц? N раз перемножить раз. А дальше что?

если не ошибаюсь, то вполне достаточно проверить, что в каком-нибудь столбце все элементы- единицы (если граф неориентированный)

И все же самый простой алг, это случайный обход

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

для орграфа, наверное, достаточно проверить 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