Матрицы смежности и инцидентности

Способы задания графов

Матрица инцидентности A. По вертикали указываются вершины, по горизонтали - ребра. aij=1 если вершина i инцидентна ребру j, в противном случае aij=0. Для орграфа aij=-1 если из вершины i исходит ребро j, aij=1 если в вершину i входит ребро j. Если ребро - петля, то aij=2.

Список ребер. В первом столбце ребра, во втором вершины им инцидентные.

Матрица смежности - квадратная симметричная матрица. По горизонтали и вертикали - все вершины. Dij= число ребер, соединяющее вершины i,j.

Матрица Кирхгофа: bij=-1, если вершины i и j смежны, bij=0 если вершины i и j не смежны, bii=deg(i). Сумма элементов в каждой строке и каждом столбце матрицы Кирхгофа равна 0.

Понятия смежности, инцидентности, степени

Если x ={ v, w } - ребро, то v и w − концы ребра x.

Если x =(v, w) - дуга ориентированного графа, то v − начало, w – конец дуги.

Вершина v и ребро x неориентированного графа (дуга x ориентированного графа) называются инцидентными, если v является концом ребра x (началом или концом дуги x).

Вершины v, w называются смежными, если { v, w }Î X.

Степенью вершины v графа G называется число d(v) ребер графа G, инцидентных вершине v.

Вершина графа, имеющая степень 0 называется изолированной, а степень 1 – висячей.

Полустепенью исхода (захода) вершины v ориентированного графа D называется число d⁺(v) (d^-(v)) дуг ориентированного графа D, исходящих из v (заходящих в v).

Следует заметить, что в случае ориентированного псевдографа вклад каждой петли инцидентной вершине v равен 1 как в d⁺(v), так и в d^-(v).

Матрицы смежности и инцидентности

Пусть D =(V, X) ориентированный граф, V ={ v ₁,..., v _n}, X ={ x ₁,..., x _m}.

Матрица смежности ориентированного графа D − квадратная матрица

A (D)=[ a_ij ] порядка n, где

Матрица инцидентности − матрица B (D)=[ b_ij ] порядка n ´ m, где

Матрицей смежности неориентированного графа G =(V, X) называется квадратная симметричная матрица A (G)=[ a_ij ] порядка n, где

.

Матрица инцидентности графа G называется матрица B (G)=[ b_ij ] порядка n ´ m, где

Дата добавления: 2015-10-13