Комбинаторика
<<  Графы Тема: Вероятность и комбинаторика  >>
Графы
Графы
Графы
Графы
E={v,w} или e=(v,w)
E={v,w} или e=(v,w)
Графы и орграфы
Графы и орграфы
Подграфы
Подграфы
Множество соседей …
Множество соседей …
Степень вершины …(1)
Степень вершины …(1)
Степень вершины …(2)
Степень вершины …(2)
Упражнение 2.1
Упражнение 2.1
Функции
Функции
Упражнение 2.2
Упражнение 2.2
Графы (3)
Графы (3)
Вершинное покрытие, независимое множество, клика,…(1)
Вершинное покрытие, независимое множество, клика,…(1)
Вершинное покрытие, независимое множество, клика,…(2)
Вершинное покрытие, независимое множество, клика,…(2)
Минимальный элемент
Минимальный элемент
Минимальный элемент и мощность
Минимальный элемент и мощность
Маршрут
Маршрут
Цепь и цикл
Цепь и цикл
Гамильтонов цикл
Гамильтонов цикл
Расстояние
Расстояние
Связные графы
Связные графы
Критерий связности
Критерий связности
Доказательство a)
Доказательство a)
Дерево, лес, …
Дерево, лес, …
Упражнение 2.2
Упражнение 2.2
Характеризация деревьев
Характеризация деревьев
Упражнение 2.3
Упражнение 2.3
Остовное дерево
Остовное дерево
Ориентированное дерево
Ориентированное дерево
Корень
Корень
Характеризация ориентированных деревьев
Характеризация ориентированных деревьев
Упражнение 2.4
Упражнение 2.4
Разрезы
Разрезы
Лемма Минти
Лемма Минти
Доказательство леммы Минти
Доказательство леммы Минти
Пример
Пример
X помечена
X помечена
X не помечена
X не помечена
Либо цикл, либо разрез
Либо цикл, либо разрез
Сильно связные орграфы (1)
Сильно связные орграфы (1)
Сильно связные орграфы (2)
Сильно связные орграфы (2)
Доказательство
Доказательство
Ациклические орграфы
Ациклические орграфы
Топологический порядок
Топологический порядок

Презентация на тему: «Графы». Автор: alvenko. Файл: «Графы.ppt». Размер zip-архива: 71 КБ.

Графы

содержание презентации «Графы.ppt»
СлайдТекст
1 Графы

Графы

Лекция 2

2 Графы

Графы

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

3 E={v,w} или e=(v,w)

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. Два ребра имеющие общую граничную точку называются смежными.

4 Графы и орграфы

Графы и орграфы

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

5 Подграфы

Подграфы

Подграфом графа 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).

6 Множество соседей …

Множество соседей …

Для графа 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) определим d(X):=E(X, V(G)\ X). Множество соседей X определяется как G(X):={v?V(G)\ X : E(X,{v}) ? ?}. Для орграфа G and X ? V(G) определим d+(X):=E+(X, V(G)\ X), d?(X):= d+(V(G)\ X), и d(X):= d+(X)Ud?(X).

7 Степень вершины …(1)

Степень вершины …(1)

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

8 Степень вершины …(2)

Степень вершины …(2)

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

9 Упражнение 2.1

Упражнение 2.1

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

10 Функции

Функции

Функция f : 2U ? R называется субмодулярной, если 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 ; модулярной, если f(X?Y) + f(X?Y) = f(X) + f(Y) для всех X,Y ? U.

11 Упражнение 2.2

Упражнение 2.2

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

12 Графы (3)

Графы (3)

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

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

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

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

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

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

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

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

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

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

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

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

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

v

w

u

{U, w} ? минимальное вершинное покрытие.

17 Маршрут

Маршрут

Маршрутом 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 . Если ei ? ej для всех 1? i < j ? k , W называется обходом или цепью в G. W замкнут, если v1= vk+1 .

18 Цепь и цикл

Цепь и цикл

Путь ? граф P = ({v1,…,vk+1 },{e1,…,ek}) такой, что vi ? vj для 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. Длина пути и цикла ? число его ребер.

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

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

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

20 Расстояние

Расстояние

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

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

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

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

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

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

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

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

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

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

24 Дерево, лес, …

Дерево, лес, …

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

25 Упражнение 2.2

Упражнение 2.2

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

26 Характеризация деревьев

Характеризация деревьев

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

27 Упражнение 2.3

Упражнение 2.3

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

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

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

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

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

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

30 Корень

Корень

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

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

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

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

32 Упражнение 2.4

Упражнение 2.4

33 Разрезы

Разрезы

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

34 Лемма Минти

Лемма Минти

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

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

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

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

36 Пример

Пример

y

x

37 X помечена

X помечена

y

x

38 X не помечена

X не помечена

y

x

39 Либо цикл, либо разрез

Либо цикл, либо разрез

?

y

x

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

«Графы»
http://900igr.net/prezentacija/algebra/grafy-95500.html
cсылка на страницу
Урок

Алгебра

35 тем
Слайды