Матрица инцидентности и список рёбер. Матрица смежности графа.

Обычно рассматриваемые графы конечны, то есть, конечны множества их элементов – вершин и рёбер. Поэтому в дальнейшем конечность графов не будет оговариваться, тем более, что важнейшие понятия и результаты, приводимые ниже относятся к произвольным графам.

Задать граф – значит, описать множества его вершин и рёбер и задать между ними отношение инцидентности. Когда граф конечный, для описания его вершин и рёбер достаточно их занумеровать. Пусть - вершины графа, а - его рёбра. Отношение инцидентности можно определить матрицей размерности . Столбцы этой матрицы будут соответствовать вершинам графа, а строки – его рёбрам. Если ребро инцидентно вершине , то , в противном случае - . Такая матрица называется матрицей инцидентности неориентированного графа, поскольку по способу её задания невозможно различить начало и конец каждого ребра.

Пример 1. Составить матрицу инцидентности неориентированного графа, изображённого на рисунке 3.

Рисунок 3.

Строим матрицу инцидентности в виде таблицы:

Для ориентированного графа матрица инцидентности составляется иначе. Это матрица размерности .

Если вершина - начало ребра , то . Если вершина - конец ребра , то . Если вершине инцидентна петля , то , где любое число, кроме чисел (обычно берут 2). В любом противном случае - .

Пример 2. Построить матрицу инцидентности для графа, изображённого на рисунке 4.

Строим матрицу инцидентности в виде таблицы:

Ещё проще задавать граф с помощью таблицы рёбер. Она состоит из двух столбцов; в левых содержатся названия рёбер, а в правых – инцидентные им вершины (для ориентированных графов обязательно сначала указывается начало ребра, потом конец). Ниже приведены таблицы рёбер для графов из примеров 1 и 2.

Для примера 1:

Для примера 2:

Очевидно, по списку рёбер можно построить его таблицу инцидентности. Действительно, каждая строка этого списка соответствует строке матрицы с тем же номером; аналогично можно выполнить обратную процедуру.

Ещё одним способом представления графа является построение для него матрицы смежности. Это квадратная матрица , в которой количество строк и столбцов равно количеству вершин графа. Для неориентированного графа эта матрица определяется следующим образом. Если вершины и являются смежными, то есть если выполняется , то . В противном случае, . Для графа из примера 1 таблица смежности имеет вид:

Матрица смежности неориентированного графа обязательно симметрична. Размерность матрицы указывает на количество вершин, а число рёбер равно половине единиц, имеющихся в матрице.

Матрица смежности ориентированного графа отличается только тем, что в том и только в том случае, когда в паре смежных вершин и вершина является началом, а вершина - концом ребра. Для графа из примера 2 матрица смежности выглядит следующим образом:

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

Ориентированный граф с симметричной матрицей смежности канонически соответствует неориентированному графу, имеющему ту же таблицу смежности (но не наоборот).