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

Матрица смежности — один из способов представления графа в виде матрицы.

Матрица смежности графа G с конечным числом вершин n (пронумерованных числами от 1 до n) — это квадратная матрица A размера n, в которой значение элемента a_ij равно числу рёбер из i -й вершины графа в j -ю вершину.

Иногда, особенно в случае неориентированного графа, петля (ребро из i -й вершины в саму себя) считается за два ребра, то есть значение диагонального элемента a_ii в этом случае равно удвоенному числу петель вокруг i -й вершины.

Матрица смежности простого графа (не содержащего петель и кратных ребер) является бинарной матрицей и содержит нули на главной диагонали.

· a_ij — число рёбер, связывающих вершины и , причем в некоторых приложениях при каждая петля (ребро при некотором ) учитывается дважды.

· Матрица смежности пустого графа, не содержащего ни одного ребра, состоит из одних нулей.

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

В случае ориентированного графа каждому ребру <x,y> ставится в соответствие "-1" на позиции (x,y) и "1" на позиции (y,x); если связи между вершинами нет, то ставится в соответствие "0".

Особенности:

· Не используется для графов с петлями, так как у петель одна вершина является и началом, и концом.

· В каждом столбце должны стоять две единицы, а все остальные символы - нули.

Вопрос