Матрицы графов и их свойства

G (ρ(1)=3, ρ(2)=2, ρ(3)=4, ρ(4)=2, ρ(5)=3.

Матрицей смежности (смежностей) А=||aij|| графа

G с p вершинами называется (рxр) матрица, в которой аij = 1, если вершина υi смежна с υj, и аij = 0 в противном случае.

Итак, существует взаимно однозначноесоответствие между графами с р вершинами и симметрическими бинарными (рxр) – матрицами с нулями на главной диагонали.

аij = 1, если дуга υiυj принадлежит Д, и аij

= 0 в противном случае. Итак, А(Д) не обязательно симметрична.

Матрицу смежности данного графа можно рассматривать как матрицу смежности симметрического орграфа.

Линейным подграфом орграфа Д называется подграф, в котором у каждой вершины полустепень исхода и полустепень захода равны 1. Таким образом, такой подграф содержит непересекающийся набор простых контуров.

Остовной подграф - подграф графа G, содержащий все его вершины.

изоморфизма.

Теорема с связи матрицы смежностей G и матрицы

инциденций G. Пусть ВТ – транспонируемая матрица к В.

B=||bij||, размерность nxm (n вершин, m дуг).
bij = 1, если xi является начальной вершиной дуги aj.
bij = -1, если xi является конечной вершиной дуги aj.
bij = 0, если xi не является концевой вершиной дуги aj или если aj является петлей.
 

инциденций В
А( (G)) = BTB-2Iq,

где Iq –

единичная матрица порядка q. Имеется в виду реберный граф (G) все вершины которого взаимно однозначно сопоставлены ребрам графа G, причем две вершины в (G) смежны тогда и только тогда, когда соответствующие им ребра смежны в G.
 

Поскольку каждая дуга инцидентна двум различным вершинам, за исключением того случая, когда дуга образует петлю, то каждый столбец либо содержит один элемент, равный 1, и один, равный -1, либо все элементы столбца равны 0.

Если G – неориентированный граф, то его матрица инциденций определяется также, за исключением того, что все элементы, равные -1, заменяются на +1.
Обобщение на случай мультиграфа:

вершин V=V1 V2, а

множество ребер Х=Х1 Х2.

Соединение графов: G1+G2 состоит из G1 G2 и всех ребер, соединяющих V1 и V2.

G1+G2:

Если G - связный граф, то nG с n компонентами, каждая из которых изоморфна G.

U=(U1,U2) и V=(V1,V2) из V=V1xV2 .

Композиция G=G1[G2] также имеет V=V1xV2 в качестве множества вершин и вершина U=(U1,U2) смежна с V=(V1,V2) тогда и только тогда, когда [U1 adj V1] или [U1=V1 и U2 adj V2]

цикл:
z1={x1,x2,x3} z4={x1,x3,x4,x5,x6}
z2={x2,x4,x5,x6}

z5={x2,x4,x5,x7,x8}
z3={x6,x7,x8} z6={x1,x3,x4,x5,x7,x8}

С, то
С*ВТ≡0(mod 2)
Доказательство: рассмотрим i-ю строку матрицы С и j–й

столбец матрицы ВТ, которая является j–й строкой матрицы В. Оба 2-х элемента этих двух строк ≠ 0 тогда и только тогда, когда ребро Х2 принадлежит i-му циклу Zi и инцидентно 3,вершин Vi. Если цикл Zi содержит Х2, то он содержит и вершину Vj.

с данным числом ребер р.   Задача: Даны графы: