Задача по Теории графов

forester_200

Пусть дан ориентированный граф с конечным числом вершин N
Пронумеруем его вершины номерами 1, 2, 3, …, N
Пусть a_ij – количество ориентированных рёбер идущих из вершины № i в вершину № j, 1<= i, j <= N
Как называется матрица A=(a_ij)?
Как называется матрица B=(a_ji)?
Просьба гипотез и догадок не высказывать.
Нужен надёжный ответ.
Спасибо.

Lokomotiv59

Матрица смежности
2. Матрица смежности транспонированного графа или транспонированная матрица смежности

forester_200

deleted by

Waleri58

блин, как-то сразу я не врубился, что это матрица смежности, мне показалось, что тут разговор о полустепенях исхода и тп, а не про гиперграф.
вершины бывают смежными - когда одна достижима из другой... честно говоря, не помню, насколько корректно говорить о матрице смежности для ориентированного графа.
википедия, кстати другое определение матрицы смежности даёт, которое не эквивалентно данному:
Матрица смежности графа - это матрица, значения элементов которой характеризуются смежностью вершин графа. При этом значению элемента матрицы присваивается количество рёбер, которые соединяют соответствующие вершины (т.е. которые инцидентны обоим вершинам). Петля считается сразу двумя соединениями для вершины, т.е. к значению элемента матрицы в таком случае следует прибавлять 2.
Лучше, чем википедия не скажу :
Матрица инцидентности графа - это матрица, значения элементов которой характеризуется инцидентностью соответствующих вершин графа (по вертикали) и его рёбер (по горизонтали). Для неориентированного графа элемент принимает значение 1, если соответсвующие ему вершина и ребро инцидентны. Для ориентированного графа элемент принимает значение 1, если инцидентная вершина является началом ребра, значение -1, если инцидентная вершина является концом ребра. В остальных случаях (в том числе и для петель) значению элемента присваивается 0.
http://ru.wikipedia.org/wiki/%D0%A1%D0%BB%D0%BE%D0%B2%D0%B0%...

Lokomotiv59

точно такое же определение матрицы смежности, в чем разница-то ?

Waleri58

в первом определении учитываются только исходящие дуги для i, а во втором, как я понял, и те и другие, особенно если учесть тут, что сказано про петли.
Оставить комментарий
Имя или ник:
Комментарий: