Метрические характеристики графов

Граф – это множество точек или вершин и множество линий или ребер, соединяющих между собой все или часть этих точек.

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

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

По матрице смежности можно однозначно восстановить граф.

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

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