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




НазваниеЛекция 2 Графы
Дата конвертации06.02.2013
Размер445 b.
ТипЛекция


Графы

  • Лекция 2


Графы

  • Неориентированным графом (графом) называется тройка (V, E, ), где V и E конечные множества и {XV : | 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): xX\Y yY\X} E+(X,Y):{(x,y)E(G): xX\Y yY\X}.

  • Для неориентированного графа G and X V(G) определим XX, V(G)\ XМножество соседей X определяется как (X):vV(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|+|+XY)|+ |+X,Y)|+|+Y,X)|;

  • (b) |−X|+|−Y)|=|−XY|+|−XY)|+ |+X,Y)|+|+Y,X)|.

  • Для графа G и двух множеств X,Y V(G):

  • (c) |X|+|Y)|=|XY|+|XY)|+2|X,Y)|;

  • (d)|X||Y)|≥|XY|+|XY)|.



Упражнение 2.1

  • Доказать лемму 2.1



Функции

  • Функция f : 2UR называется

  • субмодулярной, если f(XY)+f(X⋃Y) ≤ f(X) + f(Y) для всех X,Y U ;

  • супермодулярной, если f(X∩Y) + f(X⋃Y) ≥ f(X) + f(Y) для всех X,Y U ;

  • модулярной, если f(X∩Y) + f(X⋃Y) = f(X) + f(Y) для всех X,Y U.



Упражнение 2.2

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



Графы (3)

  • Полный граф простой граф, в котором каждые две различные вершины смежны.

  • Дополнением простого графа G называется граф H такой что G+H ― полный граф.

  • Паросочетанием в графе G называется множество попарно несмежных ребер.



Вершинное покрытие, независимое множество, клика,…(1)

  • Вершинное покрытие в G ― множество SV(G) вершин, таких что каждое ребро из G инцидентно по крайней мере одной вершине в S.

  • Реберное покрытие в G ― множество FE(G) ребер, таких что каждая вершина G инцидентна по крайней мере одному ребру в F.

  • Независимое множество в G ― множество попарно несмежных вершин.

  • Граф без ребер называется пустым.

  • Клика ― множество попарно смежных вершин.



Вершинное покрытие, независимое множество, клика,…(2)

  • Предложение 2.2.

  • Пусть G ― граф и XV(G). Тогда следующие утверждения эквивалентны:

  • X вершинное покрытие G,

  • V(G)\X независимое множество в G,

  • V(G)\X клика в дополнении к G.



Минимальный элемент

  • Пусть F ― семейство графов.

  • F называется минимальным элементом F , если F F и F не содержит собственных подграфов F.

  • F называется максимальным элементом F , если F F и F не является собственным подграфом никакого элемента из F .



Минимальный элемент и мощность

  • Заметим, что минимальный элемент не всегда имеет минимальную мощность.



Маршрут

  • Маршрутом W в G называется последовательность v1,e1,v2 ,e2 ,…,vk ,ek , vk+1 , k ≥ 0, и ei=(vi ,vi+1)E(G) (ei={vi ,vi+1}E(G)), i = 1,…,k .

  • Если eiej для всех 1≤ i < j k , W называется обходом или цепью в G.

  • W замкнут, если v1= vk+1 .



Цепь и цикл

  • Путь граф P = ({v1,…,vk+1 },{e1,…,ek}) такой, что vivj для 1≤ i < j k+1, и последовательность v1,e1,v2 ,e2 ,…,vk ,ek ,vk+1 является обходом.

  • Циклом называется граф ({v1,…,vk }, {e1,…,ek}) такой, что последовательность v1,e1,v2 ,e2 ,…,vk ,ek ,v1 является замкнутым обходом и vi vj for 1 ≤ i < j k +1.

  • Длина пути и цикла ― число его ребер.



Гамильтонов цикл

  • Остовный путь в G называется гамильтоновым путем.

  • Остовный цикл в G называется гамильтоновым циклом.

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



Расстояние

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

  • Если такого пути нет, то есть w недостижима от v, полагаем dist(v,w) = ∞.

  • В неориентированном случае dist(v,w) = dist(w,v) для всех v, wV (G).



Связные графы

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

  • В противном случае граф называется несвязным.

  • Максимальный связный подграф G называется его связной компонентой.

  • Вершина v такая что G – v имеет больше связных компонент чем G называется разделяющей (сочленяющей) вершиной.

  • Ребро e называется мостом, если G – e имеет больше связных компонент чем G.



Критерий связности

  • Предложение 2.3.

  • Граф G связный тогда и только тогда, когда X) ≠ ø для всех ø ≠ X V (G).

  • Пусть G ― орграф и r V(G). Тогда существует r-v-путь для каждой v V(G) тогда и только тогда, когда +X≠ ø для всех X V (G) с r X.



Доказательство a)

  • If: Пусть существует X V(G) с rX,

  • 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 вершинах. Тогда следующие утверждения эквивалентны:

  • G ― дерево (связный граф без циклов).

  • G имеет n-1 ребро и не имеет циклов.

  • G имеет n-1 ребро и связен.

  • G ― минимальный связный граф ( каждое ребро ― мост)

  • G ― минимальный граф с (X) ≠ ø для всех ø ≠ X V (G).

  • G ― максимальный граф без циклов (добавление любого ребра образует цикл)

  • G содержит единственный путь между любой парой вершин.



Упражнение 2.3



Остовное дерево

  • Остовный подграф, который является деревом, называется остовным деревом.

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



Ориентированное дерево

  • Орграф называется связным если его соответствующий граф связный.

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

  • Связный ориентированный лес называется ориентированным деревом (ордерево).



Корень

  • По Теореме 2.4 ориентированное дерево с n вершинами имеет n –1 ребро.

  • Следовательно оно имеет ровно одну вершину r с −r)=ø.

  • Эта вершина называется корень.

  • Вершины v с +v=ø называются листья.



Характеризация ориентированных деревьев

  • Теорема 2.5.

  • Пусть G ― орграф на n вершинах. Тогда следующие утверждения эквивалентны:

  • G ордерево с корнем в r .

  • G ориентированный лес с n1 ребром и −r)=ø.

  • G имеет n 1 ребро и каждая вершина достижима из r.

  • Каждая вершина достижима из r, но удаление любого ребра нарушает это свойство.

  • G минимальный граф с +X≠ ø для всех X V (G) с r X.

  • −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с sX и t X называется s-t- разрезом.

  • s-t-разрез в графе ― разрез Xдля некоторогоX V(G) с s X и t X.

  • r-разрез в орграфе ― множество ребер +Xтаких, что X V(G) с rX.



Лемма Минти

  • Лемма 2.6. (Minty [1960])

  • Пусть G ― орграф и e E(G). Предположим e покрашена в черный цвет, а все другие дуги в красный, черный или зеленый. Тогда выполнено ровно одно из следующих утверждений:

  • Существует неориентированный цикл, содержащий e, и только красные и черные ребра, так что все черные ребра имеют одинаковую ориентацию.

  • Существует неориентированный разрез, содержащий e, и только зеленые и черные ребра, так что все черные ребра имеют одинаковую ориентацию.



Доказательство леммы Минти

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











Сильно связные орграфы (1)

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

  • Сильно связными компонентами орграфа называются максимально сильно связные подграфы.



Сильно связные орграфы (2)

  • Следствие 2.7.

  • В орграфе G, каждая дуга принадлежит либо ориентированному циклу, либо ориентированному разрезу и следующие утверждения эквивалентны:

  • a) G ― сильно связный.

  • b) G не содержит ориентированного разреза.

  • c) G ― связный и каждая его дуга принадлежит ориентированному циклу.



Доказательство

  • с)  a)

  • Рассмотрим произвольную вершину rV(G) и докажем, что из нее существуют r-v-путь в каждую vV(G). Пусть это не так.

  • Предложение 2.3 b)   X V(G) c rX и +X=ø.

  • Так как G связный, то +X⋃–X≠ø.

  • e–X

  • Но эта дуга не может принадлежать циклу, так как нет дуг выходящих из X.



Ациклические орграфы

  • Орграф называется ациклическим, если в нем нет ориентированных циклов.

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

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



Топологический порядок

  • Определение 2.8. Пусть G ― орграф. Топологическим порядком G называется порядок вершин V(G)={v1,…,vn } такой, что для каждого ребра (vi ,vj)  E(G) имеем i < j.

  • Предложение 2.9. Орграф имеет топологический порядок тогда и только тогда, когда онациклический.



Похожие:

Лекция 2 Графы iconЛекция 18 Раскраска графов Эйлеровы графы Гамильтоновы графы Раскраска графов
Справедливо и обратное, любое такое расписание определяет правильную раскраску графа G. Следовательно, кратчайшее время необходимое...
Лекция 2 Графы iconЛекции по курсу «Алгоритмизация и программирование» Лекция 14. Графы и их представление. Основные алгоритмы на графах

Лекция 2 Графы iconЛекции по курсу «Алгоритмизация и программирование» Лекция 12. Динамические структуры данных: связные списки, деревья, графы

Лекция 2 Графы iconЛекция 9 Отношения, графы Определения Определение. Пусть а и b объекты. Определение. Пусть а и b объекты. Через ( а, b )
Определение. Отношение {(b, а) | (а, b)  R} называется обратным к отношению r и часто обозначается через r-1
Лекция 2 Графы iconГрафы

Лекция 2 Графы iconГрафы: определения и примеры Графы: определения и примеры

Лекция 2 Графы iconГрафы, Планарность, Триангуляция, Делоне, Сетки Графы, Планарность, Триангуляция, Делоне, Сетки

Лекция 2 Графы iconПрограмма первого семестра Введение Графы Остовные деревья Кратчайшие пути Потоки в сетях Максимальное паросочетание

Лекция 2 Графы iconЯзыки и методы конструирования программ
...
Лекция 2 Графы iconРешение задач методом «графы»
С помощью таких графов могут быть представлены схемы двухсторонних (симметричных) отношений
Разместите кнопку на своём сайте:
dok.opredelim.com


База данных защищена авторским правом ©dok.opredelim.com 2015
обратиться к администрации
dok.opredelim.com
Главная страница