Скачать

Матрицы графов

БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИНФОРМАТИКИ И РАДИОЭЛЕКТРОНИКИ

Кафедра информатики

РЕФЕРАТ

На тему:

«Матрицы графов»

МИНСК, 2008


В теоретико-множественной и геометрической форм определения (задания) графов, часто используется матричная форма их представления. Существуют различные виды матриц графов, однако все они, как правило, полностью передают основные свойства графов. Матричная форма задания графов обладает достаточной наглядностью при любой степени сложности графа и, что самое важное, позволяет автоматизировать процесс обработки информации, представленной в терминах теории графов, – любая матрица графа может быть введена в ЭВМ.

При задании графов в матричной форме могут учитываться либо отношения смежностей (вершин или ребер (дуг)), либо отображения инцидентности (вершин и ребер (дуг)). В связи с этим матрицы графов делятся на два основных класса: матрицы смежностей и матрицы инциденций.

Определение.1. Матрицей смежности вершин неориентированного графа G называется квадратная матрица A(G)=(aij) порядка p=p(G) (p – количество вершин графа), элементы aij которой равны числу ребер, соединяющих вершины xi и xj.


x1x2x3x4x5x6x7x8
x120001010
x200100110
x301010100
A(G)=x400101000
x510010001
x601100000
x711000000
x800001000

На рис. 1 приведен неориентированный граф G(X, E) и справа – соответствующая ему матрица смежностей вершин A(G).

Из определения 1 непосредственно вытекают основные свойства матриц этого вида.

1. Матрица смежностей вершин неориентированного графа A(G) является квадратной и симметричной относительно главной диагонали.

2. Элементами матрицы A(G) являются целые положительные числа и число ноль.

3. Сумма элементов матрицы A(G) по i-й строке (или по i-му столбцу) равна степени соответствующей вершины d(xi).

Из определения матрицы смежностей вершин неориентированного графа и ее основных свойств следуют некоторые особенности соответствия между графом G(X, E) и его матрицей A(G). На рис. 1 указана некоторая нумерация вершин графа; расположенная рядом матрица соответствует именно этой нумерации. Если же в графе G(X, E), приведенном на этом рисунке, использовать другую нумерацию вершин (например, сдвинув ее относительно вершин по часовой стрелке), то это приведет к тому, что в матрице A(G) произойдет перестановка отдельных строк и столбцов. Поэтому говорят, что каждый неориентированный граф имеет единственную с точностью до перестановки строк и столбцов матрицу смежностей вершин. И наоборот, каждая квадратная симметричная относительно главной диагонали матрица, элементами которой являются целые положительные числа и число ноль, определяет единственный с точностью до изоморфизма неориентированный граф, матрицей смежностей вершин которого является данная матрица.

Рекомендуется самостоятельно построить матрицу смежностей вершин графа G(X, E), показанного на рис. 1, с использованием другой нумерации вершин и сравнить полученную при этом матрицу с матрицей смежностей вершин приведенного графа.

Определение 2. Матрицей смежности вершин ориентированного графа G называется квадратная матрица A(G)=(aij) порядка n (n – число вершин графа), элементы которой aij равны числу дуг, исходящих из вершины xi и заходящих в вершину xj.


x1x2x3x4x5x6x7x8
x100000000
x200000100
x301001010
A(G)=x410000000
x500001100
x600000001
x700000100
x810001000

На рис. 2 показан ориентированный граф G(X, E) и справа – матрица смежностей его вершин. Из определения следует, что сумма элементов i-й строки матрицы A(G) орграфа равна полустепени исхода d+(xi), а по i-му столбцу – полустепени захода d-(xi). По-прежнему элементы этой матрицы – целые положительные числа и число ноль. Матрица смежностей вершин орграфа может оказаться симметричной относительно главной диагонали лишь в редких частных случаях.

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

Определение 3. Матрицей инцидентности неориентированного графа G называется матрица B(G)=(bij) размером (p x q) (p и q – количество вершин и ребер графа), элементы bij которой равны единице, если вершина xi инцидентна ребру ej и нулю, если соответствующие вершины и ребра не инцидентны.

Свойства матрицы инцидентности неориентированного графа.

1. Сумма элементов матрицы на i-й строке равна d(xi).

2. Сумма элементов матрицы по i-му столбцы равна 2.

Матрица инцидентности графа, изображенного на рис. 1, а имеет вид:

e1E2e3e4e5e6e7e8e9e10
x11120000000
x20001110000
x30000011100
B(G)=x40000000110
x51000000011
x60000101000
x70101000000
x80000000001

Следует отметить, что петле ej=(xi, xi) в матрицах этого вида соответствует j-й столбец, состоящий из нулей и одной единицы, расположенной на i-м месте. Ребру ek={xm, xn} соответствует в матрице инциденций k-й столбец, состоящий из нулей и двух единиц, расположенных на m-м и n-м местах. Нулевая строка матрицы соответствует изолированной вершине, а нулевой столбец – петле. Следует иметь ввиду, что нулевой столбец матрицы инцидентности лишь указывает на наличие петли, но не содержит информации о том, с какой именно вершиной связана эта петля.

Необходимо отметить, что между строками матрицы инцидентности B(G) существует очевидная зависимость. Так как каждый столбец этой матрицы содержит только два единичных элемента или состоит только из нулей, если столбец соответствует петле, то сумма по модулю 2 всех строк равна нулю. Поэтому без потери информации о графе вместо матрицы B(G) можно рассматривать сокращенную матрицу Bo(G), получаемую из B(G) вычеркиванием любой строки (чаще всего вычеркивается последняя строка). Таким образом, из p строк матрицы B(G) связного графа (см. п. 5) одна строка всегда линейно зависима, т.е. ранг матрицы B(G) не может превышать p-1 (ранг матрицы B(G) в точности равен p-1).

Любое подмножество столбцов матрицы B(G) можно рассматривать как матрицу инцидентности B´(G) некоторого суграфа G´(X, E´), содержащего все вершины исходного графа и соответствующее выделенным столбцам подмножество E´CE его ребер. Все столбцы матрицы B´(G) линейно независимы тогда и только тогда, когда суграф G´(X, E´) не содержит циклов. Действительно, если совокупность ребер образует цикл, то каждая вершина инцидента четному числу ребер этого цикла. Следовательно, сумма по модулю 2 соответствующих столбцов дает нулевой столбец, что означает из зависимость. Если же суграф не содержит циклов, то он имеет по меньшей мере две (вообще, четное число) концевых вершин, каждая из которых инцидентна только одному ребру, являющемуся концевым. Поэтому сумма по модулю 2 соответствующих столбцов будет содержать два (или четное число) единичных элемента и, следовательно, совокупность этих столбцов независима.

В связном графе с p вершинами всегда можно выделить p-1 ребер так, чтобы они образовали суграф без циклов, представляющий собой дерево графа, являющееся каркасом. Поэтому матрица инцидентности содержит не менее p-1 независимых столбцов. В то же время любой суграф, имеющий более p-1 ребер, обязательно содержит цикл, т.е. в матрице инциденций не может быть больше p-1 независимых столбцов. Отсюда следует, что матрица инцидентности связного графа содержит в точности p-1 независимых столбцов, и поэтому ее ранг равен p-1. Число n=p-1 и определяет ранг графа.

Определение 4. Матрицей инцидентности орграфа G с p вершинами и q ребрами называется матрица B(G) = (bij) размером (p ´ q), элементы которой определяются следующим образом:

ì1, если вершина xi является началом дуги ej

bij =í -1, если вершина xi является концом дуги ej;

î 0, если вершина xi не инцидентна дугу ej .

Ниже приведена матрица инцидентности графа, изображенного на рис. 2:


e1e2e3e4e5e6e7e8e9e10e11

x10000-100000-1

x21-1000000000

x301110000000
B(G)=x400001000000

x5000-10±1100-10

x6-100000-11-100

x700-100000100

x80000000-1011

Матрица инцидентности орграфа G обладает следующими свойствами.

Сумма строк матрицы B(G) является нулевой строкой.

Любая строка матрицы B(G) является линейной комбинацией остальных строк.

Ранг матрицы B(G) равен p-1.

Определение 5. Матрицей смежности ребер неориентированного графа G называется квадратная матрица A*(G) = (a*ij) порядка q, элементы a*ij которой равны единице, если ребра ei и ej смежны, и нулю – в противном случае.

Для графа, изображенного на рис. 1, матрица смежности ребер имеет вид

e1e2e3e4e5e6e7e8e9e10
e10110000011
e21011000000
e31120000000
e40100110000
e50001011000
A*(G)=e60001101100
e70000110100
e80000011010
e91000000101
e101000000010