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

Граф задается парой множеств. Пусть - — непустое множество, - — множество всех его двухэлементных подмножеств, . Тогда пара называется неориентированным графом.Элементы множества называются вершинами графа, а элементы множества - — ребрами. Итак, граф - — это конечное множество вершин и множество ребер .

Вершины графа обозначают по-разному: или большими буквами, или малыми с индексами; для ребер наиболее употребительное обозначение - с индексом, например, . Взаимное расположение, форма и длина ребер значения не имеют. Важно лишь то, что они соединяют две данные вершины множества .

Если в паре вершин и указано направление связи, т. е. какая из вершин является первой, то соединяющий их отрезок называется дугой, а вершины, определяющие дугу , называют концевыми вершинами. Если концевые вершины совпадают, то дугу называют петлей. В графе могут существовать дуги (ребра) с одинаковыми концевыми вершинами. Такие дуги называются параллельными.

Если в графе все элементы множества изображаются дугами, то граф называется ориентированным или орграфом, если ребрами, то неориентированным. Два ребра называются смежными, если они имеют общий конец.

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

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

Граф называется простымой, если он не содержит петель и параллельных дуг. Простой граф, в котором каждая пара вершин смежна, называется полным. Граф, содержащий хотя бы две параллельные дуги (ребра), — называется мультиграфом. Граф, содержащий петли, называется — псевдографом.

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

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

Способов задания графов – — великое множество. Самый простой способ – — задание множеств и . Граф также может быть задан просто рисунком. В силу изоморфизма один и тот же граф может быть изображен разными рисунками.

Рис. 1.13.Основной и Определение дополнительныйого графыа

Граф называется плоским (планарным), если он может быть изображен на плоскости так, что все пересечения ребер являются его вершинами. Для произвольного графа следующим образом определяется дополнительный граф (дополнение) . В этом графе вершин столько же, сколько в графе , причем любые две несовпадающие вершины смежны в тогда и только тогда, когда они не смежны в (см. рис. 1.13).

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

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

Важным понятием теории графов является связность. Граф называется связным, если любые две его несовпадающие вершины соединены маршрутом.

Рис. 1.14.Граф

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

Рассмотрим изображенный на рисунке . 1.14 граф. Как для орграфов, так и для неориентированных графов можно определить матрицу смежности вершин. Это квадратная матрица

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

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

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

Строки матрицы инциденций называют векторами инциденций графа . Матрица инциденций

также однозначно определяет структуру графа.

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

Рассмотрим связный граф , пусть и — две его вершины. Длина кратчайшего -маршрута называется расстоянием между вершинами и , обозначается через . Очевидно, что расстояние между вершинами является простой цепью и . Для любой вершины величина

(1.13.6)

называется эксцентриситетом вершины . Максимальный из всех эксцентриситетов вершин называется диаметром графа и обозначается , т. е.

. (1.13.7)

Минимальный из эксцентриситетов вершин графа называется его радиусом и обозначается через :

. (1.13.8)

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

Рис. 1.15.Центр графа

Вершина центральная, если . Множество всех центральных вершин графа называется его центром. Центром может быть единственная вершина графа или несколько вершин. На рис. 1.15 , , . Таким образом, . Периферийные вершины и , диаметральные цепи и , центральная вершина .