Элементы теории графов

 

Пара множеств называется графом, если элементами множества являются двухэлементные подмножества множества . Принято называть: — множеством вершин или узлов, - множеством ребер графа . Если , то вершины и ,называют концами ребра , которое соединяет их. На рисун­ках вершины изображают точками или кружками, ребра — от­резками прямых или кривых. На рис. 1.14. приведен граф множеством вершин и множеством ребер .

	A	B	C	D
A
B
C
D

 

	A	B	C	D
(A,B)
(B,C)

Рис. 1.14. Неориентированный граф и его матрицы смежности и инцидентности

 

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

Ясно, что матрицы смежности графов симметричны относительно главной диагонали, поэтому в памяти ком­пьютера их можно представлять верхним или нижним треуголь­ником.

Матрицей инцидентности графа называется матрица размера , содержащая в пересечении строки и столбца единицу, если — конец ребра .

Граф называется двудольным, если множество его вершин разбивается на такие две доли, что концы любого ребра графа оказываются в разных долях. Граф является двудольным с долями и . Подмножество вершин гра­фа называется независимым или внутренне устойчивым, если ни­какие две принадлежащие ему вершины не соединены ребром. Например, в графе , независимыми множествами являются и . Графы называют неориентированными, когда хотят отличить их от ориентированных.

Пара множеств называется ориентированным гра­фом, или короче — орграфом, если элементами множества яв­ляются двучленные последовательности элементов множества . Здесь тоже называется множеством вершин или узлов, а — множеством дуг или ориентированных ребер. Запись будем использовать для обозначения дуги и говорить, что она выходит из вершины и входит в вершину , или — начало, — конец дуги. На рисунках дуги изображают стрелками. На рис. 1.15 приведен орграф , где . Петлей называется дуга вида , но мы будем рассматривать орграфы без петель. Дуга называется обратной по отношению к дуге , а в паре их называют взаимно обратными.

	A	B	C	D
A
B
C
D

 

	A	B	C	D
				-1
				-1

Рис. 1.15. Ориентированный граф и его матрицы смежности и инцидентности

Соотнесенный орграф для неориентированного графа получается из заменой каждого ребра парой взаимно обратных дуг, а соотнесенный неориентированный граф для орграфа получается из заменой каждой дуги и каждой пары взаимно обратных дуг на ребро. Если две вершины связаны ребром или дугой, то говорят, что эти ребро или дуга инцидентны им, а сами вершины называют смежными или соседями. Степенью вершины называется число инцидентных ей ребер или дуг. Вершина с ну­левой степенью называется изолированной, с единичной — тупиковой. В орграфах число входящих в вершину (выходящих из вершины) дуг называется степенью входа (выхода}, а неизолированная вершина с нулевой степенью входа (выхода) называется истоком (стоком). В графе : вершины и смежны, — изоли­рованная, и — тупиковые вершины. В орграфе имеем: вершины и - истоки с единичной степенью выхода, вершина — сток со степенью входа два.

Далее будем использовать термин «граф», если неважно, о каком типе графа идет речь или если тип графа ясен из контекста. Хотя большинство следующих определений будет дано для не­ориентированных графов, все они, естественно, переносятся на орграфы. Особые пояснения для орграфов даются в скобках.