Графы Лекция 2

Графы Неориентированным графом (графом) называется тройка (V, E, ), где V и E конечные множества и {X V : | X | = 2}. Ориентированным графом или орграфом называется тройка (V, E, ), где V и E конечные множества и { {(v,w) V×V : v w}. Элементы множества V называются вершинами, элементы множества E называются ребрами. Два ребра e, e' с e e' называются параллельными Граф без параллельных ребер называется простым.

e={v,w} или e=(v,w) v и w называются смежными. v сосед w (и наоборот). e={v,w} соединяет v и w. v и w граничные точки e. v инцидентна e. В орграфе ребро e= (v,w) выходит из v и входит в w. Два ребра имеющие общую граничную точку называются смежными.

Графы и орграфы Для орграфа G: соответствующий неориентированный граф это неориентированный граф G' на том же множестве вершин и множество ребер, которое содержит ребро {v,w} для каждой дуги (v,w) из G. В свою очередь G называется ориентацией G'.

Подграфы Подграфом графа G = (V(G),E(G)) называется граф H=(V(H),E(H)) с V(H) V(G) и E(H) E(G). G содержит H. H индуцированный подграф G если он является подграфом G и E(H) = {(x,y) E(G) : x,y V(H) }. H подграф G индуцированный на V(H), H=G[V(H)]. Подграф H из G называется остовным если V(H) = V(G).

Множество соседей … Для графа G и X,Y V(G) определим E(X,Y): {{x,y} E(G): x X\Y y Y\X} E + (X,Y): {(x,y) E(G): x X\Y y Y\X}. Для неориентированного графа G and X V(G) определим X X, V(G)\ X Множество соседей X определяется как (X): v V(G)\ X : E(X,{v}) ø }. Для орграфа G and X V(G) определим + X + X, V(G)\ X X + V(G)\ X и X + X U X

Степень вершины …(1) Для одноэлементных множеств вершин {v} будем писать v {v} v {v} + v + {v} v {v} Степень вершины v есть | v число ребер инцидентных v. Для орграфов | v | отрицательная степень, | + v | положительная степень, и | v | + v |+ | v |. Вершина с нулевой степенью называется изолированной. Граф все вершины которого имеют степень k называются k- регулярными.

Степень вершины …(2) Лемма 2.1 Для орграфа G и двух множеств X,Y V(G): (a) | + X |+| + Y) |=| + XY |+| + X Y) |+ | + X,Y) |+| + Y,X) |; (b) | X |+| Y) |=| XY |+| X Y) |+ | + X,Y) |+| + Y,X) |. Для графа G и двух множеств X,Y V(G): (c) | X |+| Y) |=| XY |+| X Y) |+2| X,Y) |; (d) | X | | Y) || XY |+| X Y) |.

Упражнение 2.1 Доказать лемму 2.1

Функции Функция f : 2 U R называется субмодулярной, если f(XY)+f(X Y) f(X) + f(Y) для всех X,Y U ; супермодулярной, если f(XY) + f(X Y) f(X) + f(Y) для всех X,Y U ; модулярной, если f(XY) + f(X Y) = f(X) + f(Y) для всех X,Y U.

Упражнение 2.2 Привести примеры модулярных, субмодулярных и супермодулярных функций.

Графы (3) Полный граф простой граф, в котором каждые две различные вершины смежны. Дополнением простого графа G называется граф H такой что G+H полный граф. Паросочетанием в графе G называется множество попарно несмежных ребер.

Вершинное покрытие, независимое множество, клика,…(1) Вершинное покрытие в G множество S V(G) вершин, таких что каждое ребро из G инцидентно по крайней мере одной вершине в S. Реберное покрытие в G множество F E(G) ребер, таких что каждая вершина G инцидентна по крайней мере одному ребру в F. Независимое множество в G множество попарно несмежных вершин. Граф без ребер называется пустым. Клика множество попарно смежных вершин.

Вершинное покрытие, независимое множество, клика,…(2) Предложение 2.2. Пусть G граф и X V(G). Тогда следующие утверждения эквивалентны: (a) X вершинное покрытие G, (b) V(G)\X независимое множество в G, (c) V(G)\X клика в дополнении к G.

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

Минимальный элемент и мощность Заметим, что минимальный элемент не всегда имеет минимальную мощность. u v w {u, w} минимальное вершинное покрытие.

Маршрут Маршрутом W в G называется последовательность v 1,e 1,v 2,e 2,…,v k,e k, v k+1, k 0, и e i =(v i,v i+1 ) E(G) (e i ={v i,v i+1 } E(G)), i = 1,…,k. Если e i e j для всех 1 i < j k, W называется обходом или цепью в G. W замкнут, если v 1 = v k+1.

Цепь и цикл Путь граф P = ({v 1,…,v k+1 },{e 1,…,e k }) такой, что v i v j для 1 i < j k+1, и последовательность v 1,e 1,v 2,e 2,…,v k,e k,v k+1 является обходом. Циклом называется граф ({v 1,…,v k }, {e 1,…,e k }) такой, что последовательность v 1,e 1,v 2,e 2,…,v k,e k,v 1 является замкнутым обходом и v i v j for 1 i < j k +1. Длина пути и цикла число его ребер.

Гамильтонов цикл Остовный путь в G называется гамильтоновым путем. Остовный цикл в G называется гамильтоновым циклом. Граф, содержащий гамильтонов цикл называется гамильтоновым графом.

Расстояние Расстоянием (dist(v,w), dist G (v,w) ) для двух вершин v и w называется длина кратчайшего v-w-пути в G. Если такого пути нет, то есть w недостижима от v, полагаем dist(v,w) =. В неориентированном случае dist(v,w) = dist(w,v) для всех v, w V (G).

Связные графы Непустой граф G называется связным, если любые две его вершины соединены путем в G. В противном случае граф называется несвязным. Максимальный связный подграф G называется его связной компонентой. Вершина v такая что G – v имеет больше связных компонент чем G называется разделяющей (сочленяющей) вершиной. Ребро e называется мостом, если G – e имеет больше связных компонент чем G.

Критерий связности Предложение 2.3. a)Граф G связный тогда и только тогда, когда X) ø для всех ø X V (G). b)Пусть G орграф и r V(G). Тогда существует r-v-путь для каждой v V(G) тогда и только тогда, когда + X ø для всех X V (G) с r X.

Доказательство a) If: Пусть существует X V(G) с r X, v V(G)\X и X) = ø. Не существует r-v-пути. G не связный. Only if: G не связный Не существует r-v-пути. Пусть R множество вершин достижимых из r. r R, v R и R) = ø.

Дерево, лес, … Граф без циклов называется лесом. Связный лес называется деревом. Вершина степени 1 называется листом. Звезда дерево, в котором не более одной вершины не являются листьями.

Упражнение 2.2 Доказать, что если граф лес с n вершинами, m ребрами и p связными компонентами, то n = m + p.

Характеризация деревьев Теорема 2.4. Пусть G граф на n вершинах. Тогда следующие утверждения эквивалентны: a)G дерево (связный граф без циклов). b)G имеет n-1 ребро и не имеет циклов. c)G имеет n-1 ребро и связен. d)G минимальный связный граф ( каждое ребро мост) e)G минимальный граф с (X) ø для всех ø X V (G). f)G максимальный граф без циклов (добавление любого ребра образует цикл) g)G содержит единственный путь между любой парой вершин.

Упражнение 2.3

Остовное дерево Остовный подграф, который является деревом, называется остовным деревом. Теорема 2.4 влечет, что граф связный тогда и только тогда, когда он содержит остовное дерево.

Ориентированное дерево Орграф называется связным если его соответствующий граф связный. Орграф называется ориентированным лесом если его соответствующий граф лес и каждая вершина v имеет не более одного входящего ребра. Связный ориентированный лес называется ориентированным деревом (ордерево).

Корень По Теореме 2.4 ориентированное дерево с n вершинами имеет n – 1 ребро. Следовательно оно имеет ровно одну вершину r с r) =ø. Эта вершина называется корень. Вершины v с + v =ø называются листья.

Характеризация ориентированных деревьев Теорема 2.5. Пусть G орграф на n вершинах. Тогда следующие утверждения эквивалентны: a)G ордерево с корнем в r. b)G ориентированный лес с n –1 ребром и r) =ø. c)G имеет n – 1 ребро и каждая вершина достижима из r. d) Каждая вершина достижима из r, но удаление любого ребра нарушает это свойство. e)G минимальный граф с + X ø для всех X V (G) с r X. f) r) =ø и существует единственный r-v-путь для всех v V(G)\{r}.

Упражнение 2.4

Разрезы Множество ребер X ø X V(G) называется разрезом в графе G. Множество ребер + X называется ориентированным разрезом, если øX V(G) и – X) =ø. Множество ребер F E(G) разделяет две вершины s и t, если t достижимо из s в G но не в (V(G), E(G)\F). В орграфе, множество ребер + X с s X и t X называется s-t- разрезом. s-t-разрез в графе разрез X для некоторого X V(G) с s X и t X. r-разрез в орграфе множество ребер + X таких, что X V(G) с r X.

Лемма Минти Лемма 2.6. (Minty [1960]) Пусть G орграф и e E(G). Предположим e покрашена в черный цвет, а все другие дуги в красный, черный или зеленый. Тогда выполнено ровно одно из следующих утверждений: a)Существует неориентированный цикл, содержащий e, и только красные и черные ребра, так что все черные ребра имеют одинаковую ориентацию. b)Существует неориентированный разрез, содержащий e, и только зеленые и черные ребра, так что все черные ребра имеют одинаковую ориентацию.

Доказательство леммы Минти Пусть e= (x,y). Пометим вершины графа G с помощью следующего алгоритма. Сначала пометим вершину y. В случае, если v уже помечена, а w нет, пометим w, если существует черная дуга (v,w), красная дуга (v,w) или красная дуга (w,v). При этом запишем, pred(w) = v.

Пример x y

x помечена x y

x не помечена y x

Либо цикл, либо разрез. y x ?

Сильно связные орграфы (1) Орграф называется сильно связным если существует путь из s в t и путь из t в s для всех s, t V(G). Сильно связными компонентами орграфа называются максимально сильно связные подграфы.

Сильно связные орграфы (2) Следствие 2.7. В орграфе G, каждая дуга принадлежит либо ориентированному циклу, либо ориентированному разрезу и следующие утверждения эквивалентны: a) G сильно связный. b) G не содержит ориентированного разреза. c) G связный и каждая его дуга принадлежит ориентированному циклу.

Доказательство с) a) Рассмотрим произвольную вершину r V(G) и докажем, что из нее существуют r-v-путь в каждую v V(G). Пусть это не так. Предложение 2.3 b) X V(G) c r X и + X = ø. Так как G связный, то + X – X ø. e – X Но эта дуга не может принадлежать циклу, так как нет дуг выходящих из X.

Ациклические орграфы Орграф называется ациклическим, если в нем нет ориентированных циклов. Из Следствия 2.7. орграф ациклический тогда и только тогда, когда каждая его дуга принадлежит ориентированному разрезу. Орграф ациклический тогда и только тогда, когда его сильно связные компоненты одноточечные множества.

Топологический порядок Определение 2.8. Пусть G орграф. Топологическим порядком G называется порядок вершин V(G)={v 1,…,v n } такой, что для каждого ребра (v i,v j ) E(G) имеем i < j. Предложение 2.9. Орграф имеет топологический порядок тогда и только тогда, когда он ациклический.