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

Комбинаторика Скачать презентацию
<< Применение теории графов		Комбинаторика >>

Остовные деревья	Минимальное остовное дерево	Максимальный взвешенный лес	Эквивалентные задачи	Эквивалентность
Доказательство				Условия оптимальности
Оптимальное решение	Алгоритм Краскала	Алгоритм Краскала находит оптимальное решение	Алгоритм Краскала можно реализовать	Связный граф
Как улучшить шаг	Проверка	Время работы шага	Алгоритм Прима	Алгоритм Прима находит решение
Как реализовать шаг	Максимальный взвешенный ориентированный лес	Минимальное остовное ориентированное дерево	Корневое ориентированное дерево	Эквивалентность трех задач
Ориентированный лес	Ориентированный лес и циклы	Доказательство леммы	Покажем	Основная идея
Алгоритм Эдмондса	Шаг 4	Шаг 6	Алгоритм Эдмондса находит оптимальное решение	Последовательность
Доказательство	Z	Индукция	E	Упражнение 4.2
Упражнение 4.3	Упражнение 4.4

Картинки из презентации «Остовное дерево» к уроку алгебры на тему «Комбинаторика»

Автор: Kononov. Чтобы познакомиться с картинкой полного размера, нажмите на её эскиз. Чтобы можно было использовать все картинки для урока алгебры, скачайте бесплатно презентацию «Остовное дерево.ppt» со всеми картинками в zip-архиве размером 87 КБ.

Скачать презентацию

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

содержание презентации «Остовное дерево.ppt»

Сл	Текст	Сл	Текст
1	Остовные деревья. Лекция 4.	18	кандидатов может быть выполнена за O(n) элементарных операций.
2	Задача «Минимальное остовное дерево». Дано: Граф G, веса c:	19	Задача «Максимальный взвешенный ориентированный лес». Дано:
	E(G) ? R . Найти остовное дерево в G наименьшего веса или		Орграф G, веса c: E(G) ? R . Найти ориентированный лес в G
	определить, что G ? несвязный.		наибольшего веса.
3	Задача «Максимальный взвешенный лес». Дано: Граф G, веса c:	20	Задача «Минимальное остовное ориентированное дерево». Дано:
3	E(G) ? R . Найти лес в G наибольшего веса.		Орграф G, веса c: E(G) ? R . Найти остовное ориентированное
4	Эквивалентные задачи. Будем говорить, что задача P линейно		дерево в G наименьшего веса или определить, что оно не
	сводится к задаче Q, если существуют функции f и g, вычислимые		существует.
	за линейное время, такие что f преобразует частную задачу x из P	21	Задача «Минимальное остовное корневое ориентированное
	в частную задачу y из Q, и g преобразует решение f (x) в решение		дерево». Дано: Орграф G, вершина r ?V(G), веса c: E(G) ? R .
	x. Eсли P линейно сводится к Q и Q линейно сводится к P , то обе		Найти остовное ориентированное дерево с корнем r в G наименьшего
	задачи называются эквивалентными.		веса или определить, что оно не существует.
5	Эквивалентность. Предложение 4.1 Задача «Минимальное	22	Эквивалентность трех задач. Предложение 4.6. Задачи
	остовное дерево» и задача «Максимальный взвешенный лес»		«Максимальный взвешенный ориентированный лес», «Минимальное
	эквивалентны.		остовное ориентированное дерево» и «Минимальное остовное
6	Доказательство. (G,c) ? исходный пример задачи «Максимальный		корневое ориентированное дерево» эквивалентны. Упражнение 4.1
	взвешенный лес». Удалим все ребра отрицательного веса. Положим		Доказать предложение 4.6 .
	c'(e) = – c(e). Добавим минимальное множество ребер F, так чтобы	23	Ориентированный лес. Орграф называется ориентированным
	полученный граф G' стал связным. (Веса можно взять любые.) Решим		лесом, если соответствующий ему граф является лесом и каждая
	задачу «Минимальное остовное дерево» на примере (G',c'). Удалив		вершина v имеет не более одного входящего ребра.
	из решения множество ребер F, получим решение исходной задачи.	24	Ориентированный лес и циклы. Предложение 4.7. Пусть B ?
	(G,c) ? исходный пример задачи «Минимальное остовное дерево».		орграф с для всех x ? V(B). Тогда B имеет цикл тогда и только
	Положим c'(e) = K – c(e), где K = 1 + max e ? E(G) c(e). Решение		тогда, когда соответствующий ему граф имеет цикл. Лемма 4.8.
	задачи «Максимальный взвешенный лес» на примере (G',c') дает		(Karp [1972]) Пусть B0 ? подграф G максимального веса с для всех
	решение задачи «Минимальное остовное дерево» на исходном		v ? V(B0). Тогда существует оптимальный ориентированный лес B в
	примере.		G такой, что для каждого цикла C в B0, \|E(C)\ E(B)\| = 1.
7	Условия оптимальности. Теорема 4.2 Пусть (G ,c) ? пример	25	Доказательство леммы. Пусть B – оптимальный орлес в G
	задачи «Минимальное остовное дерево», и пусть T ? остовное		имеющий макси -мально много ребер из B0. b1. a1. С ? b0. a2. b3.
	дерево в G. Тогда следующие условия эквивалентны: T ? оптимум.		E(C)\ E(B)={(a1, b1),…, (ak, bk)}. b2. a3. Покажем, что в B есть
	Для любого e = {x, y}? E(G)\ E(T), все ребра из x-y-пути в T не		bi-bi-1-путь для всех i.
	дороже чем e. Для любого e ? E(T), e ? ребро наименьшей	26	Покажем, что в B есть bi-bi-1-путь для всех i. bi-1. ai-1. С
	стоимости из ?(V(C)), где C ? связная компонента на T– e.		? b0. ai. P?B. bi+1. bi. ai+1. E(B?):={(x,y)?E(B)}\{e}U{(ai
8	(c)?(a). (с) Пусть T такое, что для любого e ? E(T), e ?		,bi)}. B?? не орлес. e?E(B). [bi-1 ai]?B.
	ребро наименьшей стоимости из ?(V(C)), где C ? связная	27	Основная идея. Найти B0 ориентированный подграф G
	компонента на T– e. Пусть T* оптимальное решение, такое что E(T)		максимального веса, в котором в каждую вершину входит не больше
	? E(T) максимально возможное. Покажем, что T = T. Пусть e =		одной дуги. Стянуть каждый цикл в B0 в вершину. Перераспредилить
	{x,y} ? E(T)\ E(T). Пусть C ? связная компонента на T– e. T +		веса в новом графе G1, так чтобы любой оптимальный орлес в G1
	e содержит цикл D. Так как e ? E(D) ? ?(C), то существует f ? e,		соответствовал оптимальному орлесу в G.
	f ? E(D) ? ?(C). Тогда (T* + e) – f является остовным деревом.	28	Алгоритм Эдмондса построения ориентированного леса
	T* оптимум ? c(e) ? c(f) и (с) ? c(f) ? c(e). c(f) = c(e) и (T*		максимального веса (1967). Input: орграф G, веса c: E(G) ? R+ .
	+ e) – f является оптимальным остовным деревом. Противоречие,		Output: орлес максимального веса B of G. Set i ??0, G0 ?? G, и
	так как в (T* + e) – f больше на одно общее ребро с T, чем в T*		c0 ?? c. Пусть Bi подграф G максимального веса с для всех v? Bi
	.		. If Bi не содержит циклов then B ?? Bi и go to (5). Построим
9	Алгоритм Краскала (1956). Input: Связный граф G, веса c:		(Gi+1, ci+1) из (Gi, ci): do для каждого цикла C из Bi . Стянем
	E(G) ? R . Output: Остовное дерево T наименьшего веса. Сортируем		C к одной вершине vC в Gi+1. For каждого ребра e = ( z, y)
	ребра так, что c(e1) ?c(e2) ?…?c(em). Set T ?? (V(G), ?). For i		?E(Gi) с z?V(C), y?V(C) do: Set ci+1 (e?) ?? ci (e) – ci
	?? 1 to m do: If T+ei не содержит цикла then T ?? T +ei.		(?(e,C)) + ci (eC) и ?(e?) ??e, где e? ?? ( z, vC), ?(e,C)=(x,y)
10	Алгоритм Краскала (2). Теорема 4.3 Алгоритм Краскала находит		?E(C), и eC самое дешевое ребро C. If i = 0 then stop. For
10	оптимальное решение за O(mn).		каждого цикла C из Bi-1 do: If есть ребро e? ? ( z, vC) ? E(B)
11	Алгоритм Краскала (3). Теорема 4.4 Алгоритм Краскала можно		then E(B) ?? (E(B)\{e? }) ??(e?) ?(E(C)\{?(?(e?),C)}) else E(B)
11	реализовать за O(m log n).		?? E(B) ?(E(C)\{eC}). Set V(B) ?? V(Gi-1), i ?? i–1 и go to (5).
12	Алгоритм Краскала (1956). Input: Связный граф G, веса c:	29	Шаг 4. z. z. e. x. ?(e,C). vC. e? y. С ? bi. eC. For каждого
	E(G) ? R . Output: Остовное дерево T наименьшего веса. Сортируем		ребра e = ( z, y) ?e(gi) с z?v(c), y?v(c) do: set ci+1 (e?) ??
	ребра так, что c(e1) ?c(e2) ?…?c(em). Set T ?? (V(G), ?). For i		ci (e) – ci (?(e,c)) + ci (ec) и ?(e?) ??e, где e? ?? ( z, vc),
	?? 1 to m do: If T+ei не содержит цикла then T ?? T +ei.		?(e,c)=(x,y) ?E(C), и ec самое дешевое ребро C.
13	Как улучшить шаг 3. Основная цель шага 3 проверить не	30	Шаг 6. z. e. z. x. ?(e,C). y. vC. e?? E(B). С ? bi. eC. x.
	приведет ли добавление ребра ei = {v,w} к образованию цикла. Это	30	?(e,C). y. vC. С ? bi. eC.
	эквивалентно проверки лежат ли v и w в одной связной компоненте.	31	Алгоритм Эдмондса. Теорема 4.9 Алгоритм Эдмондса находит
	По ходу алгоритма будем строить дополнительный орлес B с V(B) =	31	оптимальное решение.
	V(G), такой что связные компоненты B индуцированы на тех же	32	Доказательство. Последовательно применяя шаг 4 алгоритма, мы
	вершинах, что и связные компоненты T.		получили последовательность (Gi, ci), i = 0,…, k. Ясно, что
14	Проверка. Первоначально, B = (V(G), ?) и h(v) = 0, для всех		полученный на последнем применении шага 4 орлес B является
	v ?V(G), где h(v) длина максимального пути из v в B. 3.1 Для		оптимальным для (Gk, ck). Покажем, что на шаге 6 мы
	ребра ei = {v,w} находим корни rv и rw ордеревьев в B,		последовательно строим оптимальные решения для (Gi, ci), i =
	содержащих v и w. 3.2 Если rv = rw , то переходим к следующему		k–1,…,0. Мы хотим показать, что шаг 6 переводит ориентированный
	ребру и идем на 3.1. 3.3 Если rv ? rw , то добавляем ei к T.		лес наибольшего веса B для Gi в ориентированный лес наибольшего
	3.4. Если h(rv) ? h(rw), то добавляем дугу (rv, rw) к B, иначе		веса B* для Gi–1.
	добавляем дугу (rw, rv) к B.	33	Доказательство (2). Пусть B'i–1 ? произвольный орлес в Gi–1,
15	Время работы шага 3. Время работы пропорционально длине		такой что \|E(C)\ E(B'i–1)\| = 1 для любого C из Bi–1. Пусть B'i
	rv-v-пути в B. Покажем, что любое ордерево в B с корнем r имеет		получается из B'i–1 стягиванием циклов в Bi–1. Тогда B'i орлес в
	по крайней мере 2h(r) вершин. Когда B = (V(G), ?) утверждение		Gi.
	очевидно. Пусть алгоритм добавляет дугу (x,y) в B. Получаем	34	Шаг 4. z. z. e. x. ?(e,C). vC. e? y. С ? bi. eC. Set ci+1
	новое ордерево с корнем в x и числом вершин ? 2h(x) + 2h(y).	34	(e?) ?? ci (e) – ci (?(e,C)) + ci (eC).
	Если h(x) > h(y), то значение h(x) не меняется и утверждение	35	Индукция. По индукции, B ? ориентированный лес наибольшего
	справедливо. Если h(x) = h(y), то значение h(x) увеличивается на	35	веса в Gi . ci(B) ? ci(B'i).
	1. Число вершин в новом ордереве ? 2h(x) + 2h(y) =2h(x)+1. h(r)	36	Шаг 6. z. e. z. x. ?(e,C). y. vC. e?? E(B). С ? bi. eC. x.
	? log n, и трудоемкость шага 3 ? mlog n.	36	?(e,C). y. vC. С ? bi. eC.
16	Алгоритм Прима (1957). Input: Связный граф G, веса c: E(G) ?	37	Упражнение 4.2. Пусть (V,T1) и (V,T2) два дерева на одном
	R . Output: Остовное дерево T минимального веса. Выбрать v ?		множестве вершин V. Доказать, что для любого ребра e?T1
	V(G). T ?? ({v}, ?). While V(T) ?V(G) do: Выбрать ребро e ?		существует ребро f?T2 такое, что (V,(T1 \{e})U{f}) и (V,(T2
	?G(V(T)) минимальной стоимости. T ?? T +e.		\{f})U{e}) ? деревья.
17	Алгоритм Прима (2). Теорема 4.5 Алгоритм Прима находит	38	Упражнение 4.3. Дан граф G с произвольными весами c: E(G) ?
17	решение за O(n2) элементарных операций.	38	R . Найти остовный подграф в G наименьшего веса.
18	Как реализовать шаг 2. While V(T) ?V(G) do: Выбрать ребро e	39	Упражнение 4.4. Дан граф G с произвольными весами c: E(G) ?
	? ?G(V(T)) минимальной стоимости. T ?? T +e. Для каждой вершины		R . Найти остовное дерево T в G, такое что вес максимального
	v?V(T) будем хранить самое дешевое ребро (кандидата) из v в		ребра в T наименьший (max{c(e)\|e ?T}? min).
	V(T). Тогда выбор ребра минимальной стоимости и замена
«Остовное дерево» \| Остовное дерево.ppt

http://900igr.net/kartinki/algebra/Ostovnoe-derevo/Ostovnoe-derevo.html

cсылка на страницу

Комбинаторика

другие презентации о комбинаторике

«Решение комбинаторных зада» - Сочетание. Флаг в виде четырех горизонтальных полос. Простые и наглядные методы. Вова умеет решать все 5 задач. Виды выборок. Вершины правильного 10-угольника. Сколько различных трехзначных чисел. Сколько ребер имеет полный граф. Лейбниц. Число различных комбинаций. Решение комбинаторных задач. Разные значки.

«Виды графов» - Состав графа. Изображение вершин. Дерево – граф иерархической структуры. Граф отношения «переписываются». Как называется взвешенный граф иерархической структуры. Самое главное. Неориентированный граф. Семантическая сеть. Корень – главная вершина дерева. Ориентированный граф. Взвешенный граф. Какая связь между графом и таблицей.

«Комбинаторика и её применение» - Опыт с листом бумаги. Четырехзначное число. Костюм. Комбинаторика. Решение комбинаторных задач. Обществознание и математика. Владелец золотой медали. Самостоятельная работа. Устный счет. Обед. Проблемный вопрос. Применение комбинаторики. Комбинаторика вокруг нас. На полке лежат 3 книги. Ученик. Трехзначное число.

«Формулы для перестановок, сочетаний, размещений» - Слово «факториал». Очередь. Формулы для подсчёта количества перестановок. Количество сочетаний. Сочетания. Лесник. Количество перестановок. Количество размещений. Размещения. Перестановки. Подарок.

«Понятие комбинаторики» - Формула включений и исключений. Решение. Граф. Комбинаторная задача. Правило произведения. Цифры. Область математики. Размещение без повторения. Дерево возможных вариантов. Комбинаторика. Решение элементарных задач. Правило размещения. Варианты решения задачи. Сигналы. Правило перестановки. Капля в море.

«Принцип Дирихле» - Доказательство. Задачи. Биография. Область применения. Принцип Дирихле. Средние линии треугольника. Принцип Дирихле для длин и площадей. 11 различных целых чисел. Попарно не пересекающиеся отрезки. Формулировка.

Урок