Матрицы

Граф полностью определяется или его смежностями, или его инциденциями. Указанную информацию о графе удобно представлять в матричной форме. Действительно, с данным графом, помеченным соответствующим образом, связаны несколько матриц, в том числе матрица смежностей, матрица инциденций, матрица циклов и матрица коциклов. Часто эти матрицы удается использовать при выявлении определенных свойств графа. Классическим результатом о графах и матрицах является матричная теорема о деревьях, в которой дается число остовов любого помеченного графа. В данной главе рассматриваются также матроиды, связанные с матрицами циклов и матрицами коциклов.

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

Матрицей смежностейА = ||аij||помеченного графаG c р вершинами называется (рр) - матрица, в которой аij=1, если вершина vi смежна с vj, и aij=0 в противном случае. Таким образом,

существует взаимно однозначное соответствие между помеченными графами с р вершинами и симметрическими бинарными (р х р)-матрицами с нулями на диагонали.

На рисунке показаны помеченный граф G и его матрица смежностей А. Легко заметить, что суммы элементов матрицы А по строкам равны степеням вершин графа G. Вообще в силу соответствия, существующего между графами и матрицами, с любым теоретико-графовым понятием можно сопоставить некоторый аналог, связанный с матрицей смежностей граф G называется связным, если не существует такого разбиения V = V1 U V2 множества вершин графа G, что ребра графа G не соединяют вершины из V1 с вершинами из V2 В матричных терминах это можно сказать так: граф G связен, если не существует такой нумерации вершин графа G, что его матрица смежностей имеет приведенную форму

A = [[A11,0],[0,A22]]

где А11 и А22— квадратные матрицы. Если А1 и А2— матрицы смежностей, соответствующие различным нумерациям одного и того же графа G, то

А1 = Р^-1А2Р для некоторой матрицы перестановки Р. Иногда выбор конкретной нумерации вершин графа не существен, как, например, в следующих результатах, в которых дается интерпретация элементов степеней матрицы смежностей.

Теорема.Пусть G - помеченный граф с матрицей смежностей А.

Тогда (i, j)-u элемент матрицы Аⁿ равен числу маршрутов длины п из Vi в Vj.

Следствие (а).Для i!=j (i, j)-u элемент матрицы А² равен числу простых (ui-vj)-цепей длины 2. Далее, (i, i)-u элемент в матрице А² равен степени вершины vi, в матрице А³- удвоенному числу треугольников, содержащих vi.

Следствие(б).Если G — связный граф, то расстояние между Vi и Vj для i!=j равно наименьшему из целых чисел n, для которых (i, j)-й элемент матрицы Аn отличен от 0.

Матрица смежностей помеченного орграфаD определяется аналогично:

А=А (D)=||aij||, где аij=1, если дуга vivj принадлежит D, и aij=0 в противном случае. Таким образом, матрица A (D) не обязательно симметрична. Из определения матрицы A (D) следует, что матрицу смежностей данного графа можно также рассматривать как матрицу смежностей симметрического орграфа. Воспользуемся этим замечанием и исследуем определитель матрицы смежностей графа, как в работе Харари .

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