Теория графов

Теория графов

Общие определения

Пусть V есть множество, состоящее из соединенных некоторым образом точек. Это множество V является множеством вершин.

Граф G = G(V) есть некоторое отношение на множестве декартовых произведений VÄV. При этом если некоторая пара вершин (v,u) Î G, то вершины соединены ребром e(v,u). v и u – смежные вершины, концы ребра e.

Ребро может быть: неориентированным, при этом (v,u) = (u,v); ориентированным, т. е. дуга (v,u) ≠ (u,v). Дуга e = (v,u1) направлена от v к u1; v – начало, u1 – конец.

Если e = (v,u), то ребро e инцидентно вершинам v и u; вершины v и u инцидентны ребру e.

Если все ребра графа неориентированные, то граф – неориентированный. Граф – ориентированный, если все ребра ориентированы. В иных случаях граф смешанный.

Пример. Карту города можно представить в виде графа, где улицы – ребра, перекрестки – вершины.

Графически граф может выглядеть по-разному.

Два графа G1 и G2 называются изоморфными, если множество вершин V1 = V2 и существует такое взаимно однозначное соответствие между V1 и V2, при котором в графе G2 существует дуга (v,u) тогда и только тогда, когда дуга (u,v) существует в графе G1.

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

Граф, в котором содержатся все возможные ребра, называется полным.

Полный ориентированный граф – граф, у которого две вершины соединены хотя бы в одном направлении.

Петлей называется дуга, у которой совпадает начало и конец.

Полный граф с петлями – полный неориентированный граф с петлей в каждой вершине.

Мультиграф – граф, у которого две вершины могут быть соединены несколькими дугами или ребрами.

Дополнение графа G(V) – это граф G(V), ребра которого, будучи добавленными к исходному графу G, приводят к образованию полного графа.

Граф G-1 называется обратным к графу G, если все дуги имеют в нем противоположное направление по сравнению с исходным графом G.

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

Локальные степени

Граф называется конечным, если число вершин и ребер в нем конечно, в противном случае – бесконечным.

Рассмотрим неориентированный граф G. Число ребер ρ(v), инцидентных вершине v, назовем локальной степенью графа в вершине v.

Если все числа ρ(v) для "vÎV, то граф называется локально-конечным.

Обозначим ρ(v,u) = ρ(u,v) – это число ребер, соединяющих вершины v и u, т. е. это кратность ребра (v,u). Тогда

Обозначим m(G) – число ребер в графе G. Т. к. каждое ребро будет учитываться в двух локальных степенях v и u, то запишем:

(1)

Теорема. Число вершин нечетной локальной степени в графе четно.

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

Граф называется однородным в степени k, если локальные степени всех вершин равны k. Примерами однородных графов являются правильные треугольники, многоугольники, многогранники.

Для однородных графов можно записать:

,

где n – число вершин графа G.

Для куба:

Пусть G – ориентированный граф. Тогда введем следующие обозначения:

od(v) – число дуг, выходящих из вершины; id(v) – число дуг, заходящих в вершину.

Это локальные степени графа.

Петли, если они есть, считаются по одному разу и в od(v), и в id(v).

Аналогично считаются две кратности. Обозначим как ρo(v,u), ρi(v,u) число дуг, выходящих из v в u и из u в v соответственно.

Ориентированный граф называется однородным, если для "vÎV выполняется следующее: od(v) = id(v) = k.

Части и подграфы

Граф H называется частью графа G и обозначается H Ì G, если множество VH Ì VG и EH Ì EG. Часть H является ориентированной или нет, в зависимости от вида графа G.

Пусть A Ì VG. Подграфом G(A) с множеством вершин A является такая часть графа, множеством вершин которой является A, а ребрами – все ребра графа G, оба конца которых лежат в A.

Звездой, определяемой вершиной v, называется часть, состоящая из всех ребер, инцидентных вершине v.

Для любой части H существует дополнение, состоящее из всех ребер графа G, не вошедших в граф H.

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

Операции над графами

Пусть даны два графа: граф G1 с множеством вершин V1 и множеством ребер E1 и граф G2 с множеством вершин V2 и множеством ребер E2.

Объединением (или суммой) графов G1 и G2 называется граф G с множеством вершин V и множеством ребер E, если V = V1 È V2, E = E1 È E2. Если при этом V1 Ç V2 = Æ, то G = G1 È G2 называется прямой суммой по вершинам. Если E1 Ç E2 = Æ, то G называется прямой суммой по ребрам.

Пересечением (или произведением) графов G1 и G2 называется граф G = G1 Ç G2, множеством вершин которого является V = V1 Ç V2, множеством ребер – E = E1 Ç E2.

Декартовым произведением графов G1 и G2 называется граф G(V) = G1(V1) Ä G2(V2), множеством вершин которого является V = V1 Ä V2, причем вершина (v1,u1) смежна с вершиной (v2,u2) тогда и только тогда, когда в графе G1 смежны вершины v1 и v2, а в графе G2 смежны вершины u1 и u2.

Декартовой суммой графов G1 и G2 называется граф G(V) = G1(V1) Å G2(V2), множеством вершин которого является V = V1 Ä V2. При этом в графе G вершина (v1,u1) смежна с вершиной (v2,u2) тогда и только тогда, когда либо в графе G1 смежны вершины v1 и v2, либо в графе G2 смежны вершины u1 и u2.

Транзитивным замыканием нетранзитивного графа G(V) называется граф G*(V), который получается добавлением для каждой пары дуг (x,v), (v,y) дуги (x,y).

Цепи и циклы графов

Пусть G – неориентированный граф. Маршрутом в графе G называется такая конечная или бесконечная последовательность ребер S = (e0, e1, …, en, …), в которой каждые два соседних ребра имеют общую концевую точку. Одно и то же ребро может встречаться в маршруте несколько раз. Если e0 = (v0,v1) и e0 – первое ребро маршрута, то v0 – начальная вершина маршрута. Соответственно, если маршрут конечен и en = (vn,vn+1) – последнее ребро маршрута, то вершина vn+1 – конечная вершина маршрута. Любая вершина маршрута, кроме v0 и vn+1, называется промежуточной.

Если маршрут состоит из n ребер, то он имеет длину n. Введем обозначение: S = S(a0,an)n. Это маршрут, соединяющий вершины a0 и an, причем a0 – начальная, an – конечная вершины маршрута. В случае если a0 = an, то маршрут называется циклическим.

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

Нециклическая цепь называется простой цепью, если в ней ни одна вершина не повторяется. Цикл называется простым, если в нем повторяется только начальная вершина a0, совпадающая с конечной an.

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

Связность на графах

Пусть G – неориентированный граф. Вершины v и u называются связанными, если существует маршрут с концами в v и u. Если этот маршрут проходит через некоторую вершину a более одного раза, то, удалив циклический участок, можно получить простую цепь. Это означает, что связанные вершины всегда связаны простой цепью.

Граф называется связным, если любая пара вершин в нем связана.

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

,

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

.

Соответственно,

.

Подграфы Gi(Vi) называются связными компонентами графа G.

Таким образом, доказана следующая теорема.

Теорема. Каждый неориентированный граф распадается, причем единственным образом, на прямую сумму своих связных компонентов.

Эта теорема позволяет сводить большинство задач на графы к связным графам.

Теорема. Если в конечном графе G ровно две вершины, вершина v и вершина u, имеют нечетную локальную степень, то они связаны.

Доказательство. Мы показали, что число вершин с нечетной локальной степенью в графе четно. Если вершина v принадлежит связной компоненте графа G1, то и вершина u должна принадлежать G1, т. е. v и u связаны. Теорема доказана.

Теорема. Если граф G с однократными ребрами и без петель имеет n вершин и q связных компонент, то максимальное число в графе G равно:

.

Доказательство. Пусть в графе G компонента Gi имеет ni вершин. Тогда максимальное число ребер равно:

.

Это число достигается, если каждая связная компонента есть полный граф с числом вершин ni, ni ³ 1. Пусть есть хотя бы два подграфа G1 и G2, число вершин которых подчиняется следующему правилу: n2 ³ n1 > 1. Построим вместо исходного графа G граф G' с тем же числом вершин и компонент, заменив подграфы G1 и G2 подграфами G1' и G2' с количеством вершин n1-1 и n2+1. При этом число ребер увеличится на следующую величину: n2 - (n= n2 – n1 +1 ³ 1. Следовательно, если из каждой компоненты переносить вершины всем, кроме одной (чтобы не менять число связных компонент), в какую-то одну компоненту, то число ребер будет увеличиваться. Следовательно, максимальное число ребер будет получено, когда каждая из q-1 компонент будет представлять собой изолированную вершину, и одна компонента – полный граф с n-q+1 вершиной, т. е. N(n,q) = ½(n-q+1)(n-q). Теорема доказана.

Следствие. Граф с n вершинами и с числом ребер, большим, чем

N(n,2) = ½(n-2)(n-1) связен.

Бинарные отношения и графы

Нами было дано определение графа: G Ì VÄV, т. е. граф является некоторым бинарным отношением R на множестве вершин V. Поэтому для графов можно определить все свойства, которые справедливы для отношений на множествах. При этом будем понимать, что (v,u) Î G тогда и только тогда, когда в графе G существует ребро (v,u).

Очевидно, что нулевому отношению, которое не выполняется ни для одной пары элементов, соответствует нуль-граф.

Универсальному отношению U, которое выполняется для любой пары элементов, соответствует полный неориентированный граф.

Отношение является дополнительным для R в том случае, если ребро (v,u) Î тогда и только тогда, когда (v,u) Ï R.

Очевидно, что дополнение до полного графа соответствует дополнительному отношению.

Отношение R-1 называется обратным отношением к R, если (x,y) Î R-1 тогда и только тогда, когда (y,x) Î R. Обратному отношению соответствует обратный граф.

Рассмотрим свойства отношений.

1.  Симметричность.

xRy Þ yRx

В графе это означает наличие двух дуг (x,y) и (y,x) для любой пары вершин. Также это эквивалентно неориентированности графа. Антисимметричность означает отсутствие в графе неориентированных ребер.

2.  Рефлексивность.

"x, xRx

Это соответствует наличию петли в каждой вершине, антирефлексивность – полному отсутсвию петель.

3.  Тождественность.

xRy, yRx Þ x = y

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

4.  Транзитивность.

xRy, yRz Þ xRz

Это означает, что наличие двух дуг (x,y) и (y,z) требует обязательного наличия дуги (x,z).

5.  Полнота.

Это означает, что мы имеем полный, возможно, ориентированный граф.

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

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

По определению отношение порядка является рефлексивным, тождественным и транзитивным. Соответственно граф является ориентированным, транзитивно-замкнутым с петлями.

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

Отношению полного порядка соответствует граф порядка без изолированных вершин, т. е. с одной компонентой связности.