Матричные представления графов

Информация о структуре графа может быть задана матрицей смежности.Матрицей смежности графа G=(X,V), |X|=n называется квадратная матрица , элементы которой определяются следующим образом:

Замечание. Матрица смежности неориентированного графа симметрична. В случае кратных ребер a_ij есть количество ребер, соединяющих вершины x_i и x_j. Для орграфа а_ij определяется как количество дуг, направленных от вершины x_i к вершине x_j.

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

Согласно этой теореме по матрице смежности граф восстанавливается однозначно с точностью до изоморфизма.

Матрицей инцидентности графа G=(X,V), |Х|=п ,|V|=m называется матрица , элементы которой определяются следующим образом:

если G - неориентированный граф, то