Что такое findslide.org?

FindSlide.org - это сайт презентаций, докладов, шаблонов в формате PowerPoint.


Для правообладателей

Обратная связь

Email: Нажмите что бы посмотреть 

Яндекс.Метрика

Презентация на тему Тема Графы

Содержание

ВведениеГрафы возникли в восемнадцатом веке, когда известный математик Леонард Эйлер пытался решить теперь уже классическую задачу о Кенигсбергских мостах. В то время в городе Кенигсберге было два острова, соединенных семью мостами с берегами реки Преголь и
ГРАФЫ ВведениеГрафы возникли в восемнадцатом веке, когда известный математик Леонард Эйлер пытался решить Задача состоит в следующем: осуществить прогулку по городу таким образом, чтобы, пройдя Как мы увидим, Эйлеру удалось доказать, что искомого маршрута обхода города не существует. В этом разделе мы введем стандартную терминологию, используемую в теории графов, и Деревья — естественная модель, представляющая данные, организованные в иерархическую систему. Поиск по Графы. Терминология На рис. 7.1 изображены семь мостов Кенигсберга так, как они Модель задачи — это граф, состоящий из множества вершин и множества ребер, Проход ребра, очевидно, соответствует пересечению реки по мосту. Граф, в котором найдется маршрут, начинающийся и заканчивающийся в одной вершине, и Эйлер заметил, что если в графе есть эйлеров цикл, то для каждого Кроме того, Эйлеру удалось доказать и противоположное утверждение, так что граф, в Если вершина v графа является концом ребра x, то говорят, что v С легкой руки Эйлера графы, подобные тому, который мы исследовали при решении Простой граф определяется как пара G = (V, Е), где V — Граф, изображенный на рис. 7.2, не является простым, поскольку, например, вершины А Две вершины u и v в простом графе называются смежными, если они Отсутствие рефлексивности связано с тем, что в простом графе нет петель, т.е. Логическая матрица отношения на множестве вершин графа, которое задается его ребрами, называется Пример 7.1. Нарисуйте граф G(V, E) с множеством вершин V = {а, Его матрица смежности имеет вид: Для восстановления графа нам достаточно только тех элементов матрицы смежности, которые стоят Пример 7.2. Найдите среди графов Н, К и L, изображенных на рис. Маршрутом длины k в графе G называется такая последовательность вершин v0, v1, Циклом в графе называется последовательность вершин v0, v1, ..., vk, каждая пара Пример 7.3. Найдите циклы в графе G из примера 7.2.Решение. В этом Граф, в котором нет циклов, называется ацикличным ( или ациклическим). Частным случаем Граф называется связным, если любую пару его вершин соединяет какой-нибудь маршрут. Любой Вопросы связности имеют важное значение в приложениях теории графов к компьютерным сетям. Алгоритм связностиПусть G = (V, Е) — граф. Алгоритм предназначен для вычисления найти все вершины, соединенные 		маршрутом с у; удалить 			вершину у из V' Пример 7.4. Проследите за работой алгоритма связности на графе, изображенном на рис. На первом шаге удалены вершины 1,6,3,8. В итоге, c(G) = 3. Соответствующие Гамильтоновы графы Мы начали этот раздел с изучения эйлеровых графов, обладающих замкнутым Гамильтоновы графы служат моделью при составлении расписания движения поездов, для телекоммуникационных сетей Тем не менее, многие графы являются гамильтоновыми. Если в графе любая пара Полный граф K5 изображен на рис. 7.8. Его цикл  а b Далее будет три варианта для выбора третей вершины и два для четвертой, Поиск гамильтонова цикла (если он существует) в произвольном (связном) графе — задача Пример 7.5. Покажите, что граф, изображенный на рис. 7.9, не является гамильтоновым. Решение. Предположим, что в связном графе найдется гамильтонов цикл. Каждая вершина v Все степени вершин данного графа — только 2 или 3. Вершины степени Ребро bf не может быть частью цикла С, поскольку каждая вершина такого Это вынуждает нас включить в цикл ребро ed, что приводит к противоречию: Гамильтоновы графы применяются для моделирования многих практических задач. Основой всех таких задач Коммивояжер должен совершить поездку по городам и вернуться обратно, побывав в каждом Графическая модель задачи коммивояжера состоит из гамильтонова графа, вершины которого изображают города, Кроме того, каждое ребро оснащено весом, обозначающим транспортные затраты, необходимые для путешествия Для решения задачи нам необходимо найти гамильтонов цикл минимального общего веса.К сожалению, Однако существуют алгоритмы поиска субоптимального решения.Субоптимальное решение необязательно даст цикл минимального общего Алгоритм ближайшего соседаЭтот алгоритм выдает субоптимальное решение задачи коммивояжера, генерируя гамильтоновы циклы begin	выбрать v  V; 	маршрут := v; 	w := 0; 	v' :=v;	отметить маршрут := маршрут u;			w : = w + вес ребра v'u;			v' := Пример 7.6. Примените алгоритм ближайшего соседа к графу, изображенному на рис. 7.11. Решение. См. табл. 7.2. В результате работы алгоритма был найден гамильтонов цикл D C A B В полном графе с двадцатью вершинами существует приблизительно 6,1 ∙ 1016 гамильтоновых Деревья Как упоминалось ранее в этом разделе, есть класс графов, называемых деревьями, Пусть G = (V, Е) — граф с n вершинами и т Эквивалентность большинства из этих условий устанавливается без особого труда. Наиболее сложно разобраться Пример 7.7. Докажите с помощью индукции по числу вершин, что для дерева Решение. Поскольку дерево с единственной вершиной вообще не содержит ребер, то доказываемое Удалим ребро из T. По третьему свойству дерево T после этой процедуры Обозначим новые деревья через T1 и Т2. Пусть n 1 — количество Несложно доказать, что в любом связном графе найдется подграф, являющийся деревом. Подграф Остовное дерево в графе G строится просто: выбираем произвольное его ребро и Пример 7.8. Найдите два разных остовных дерева в графе, изображенном на рис. 7.12. Решение. В этом графе существует несколько остовных деревьев. Одно из них получается Процесс, описанный в примере 7.8, можно приспособить для решения задачи поиска кратчайшего На языке теории графов нам нужно в нагруженном графе найти остовное дерево В отличие от задачи коммивояжера, здесь есть эффективный алгоритм, находящий действительно минимальное Алгоритм поиска минимального остовного дереваПустьG = (V, Е) — связный взвешенный граф. begin	е : = ребро графа G с наименьшим весом; 			T := {e}; е': = ребро из Е' наименьшего веса; T:=T  {e'};		Е':= множество ребер Пример 7.9. В таблице 7.3 дано расстояние (в милях) между пятью деревнями Решение. Ребра выбираются следующим образом: первое — ребро DE веса 2; второе Следующие по весу ребра — AD, АЕ и CD, каждое из которых Зачастую нам хотелось бы иметь деревья, представляющие информацию с учетом естественной иерархической Генеалогическое древо можно изобразить и более сжато. Схема, приведенная на рис. 7.16, Корень, в некотором смысле, можно назвать «величайшей» вершиной (например, родоначальник математиков Бернулли). Дерево с корнем можно определить рекуррентным образом. Отдельная вершина является деревом с Вершины v 1,…, vk графа Т — это сыновья корня v. Мы Как мы уже говорили, вершина на самом верху дерева — его корень, Область применения деревьев с корнем обширна. Это, например, и информатика, и биология, Таким образом, можно сказать, что каждой вершине двоичного дерева с корнем соответствует Если оказалось, что у какой-то вершины дерева отсутствует потомок слева, то ее Пример 7.10. Пусть T — двоичное дерево с корнем, изображенное на рис. 7.18. Определите(а)	корень T;(б)	корень левого поддерева вершины В;(в)	листья Т;(г)	сыновей вершины С.Нарисуйте двоичное дерево с Решение.(а) А; (б) D; (в) G, Н, Е, I и J; (г) Краткое содержание главыГраф G = (V, Е) состоит из множества V, чьи Граф, в котором существует маршрут (называемый эйлеровым), начинающийся и заканчивающийся в одной Лемма об эстафете утверждает, что сумма степеней вершин произвольного графа G = Логическая матрица отношения на множестве вершин простого графа G, которое задается его Маршрутом длины k в графе называют такую последовательность различных вершин v0, v1, Граф, не содержащий циклов, называют ацикличным.Связным является тот граф, в котором каждая Гамильтоновым называют такой цикл в графе, который проходит через каждую вершину графа, Задача коммивояжера состоит в поиске гамильтонова цикла минимального общего веса в нагруженном Связный ацикличный граф G = (V, Е) является деревом. Следующие утверждения о Остовным деревом графа G называют такой его подграф, который является деревом и Дерево с одной выделенной вершиной называют деревом с корнем, а выделенную вершину Вершины, расположенные в самом низу дерева (они не имеют сыновей), называются листьями. Каждая вершина дерева с корнем Т является корнем какого-то другого дерева, называемого Глубиной вершины v дерева с корнем Т принято считать длину единственного маршрута, Сортировка и поискДвоичные деревья с корнем очень полезны при решении задач о Упорядоченные данные, такие как множество чисел, упорядоченных по величине или множество строк При этом мы стремимся к тому, чтобы данные, стоящие в левом поддереве Например, в дереве двоичного поиска, приведенном на рис. 7.26, слова фразы «У Заметим, что каждое слово в левом поддереве любой вершины предшествует (относительно алфавитного Преимущество организации упорядоченных данных в виде двоичного дерева поиска заключается в возможности Предположим, что в университете хранится список студентов (упорядоченный в алфавитном порядке), в Допустим также, что возникла необходимость найти какую-то информацию в списке или добавить Записи о студентах организованы в двоичное дерево поиска (каждая запись соответствует одной Чтобы это осуществить, необходимо приписать каждой вершине некоторый ключ для идентификации и Из всех ключей организуется линейно упорядоченное множество (в нашей ситуации оно упорядочено Поиск (дерево) 	begin		if дерево нулевое then			поиск := ложь; 		else			if ключ поиска = if ключ поиска < ключ корня then		поиск := поиск (левое поддерево); 	else		поиск := поиск (правое поддерево);	end Задача 1. Проследите за работой алгоритма над двоичным деревом поиска, изображенном на Решение. Поскольку R > К, то поиск продолжается в правом поддереве вершины Алгоритм вставки вставляет новые вершины (ключи вставок) в двоичное дерево поиска, создавая Вставка (запись, дерево) 	begin		if дерево нулевое then			добавить новую вершину; 		else			if ключ вставки if ключ вставки < ключ корня then 			вставка := вставка (запись, 			левое Задача 2. Проследите за работой алгоритма вставки на примере вершин R, А Решение. Поскольку R > К, мы применяем алгоритм вставки к правому поддереву Алгоритм вставки можно использовать для создания двоичного дерева поиска, начиная с нулевого Например, двоичное дерево поиска на рис. 7.26 является результатом применения алгоритма вставки Алгоритм правильного обхода выводит на печать всю информацию, содержащуюся в двоичном дереве Для каждой вершины, начиная с корня, печатается вся информация, содержащаяся в вершинах Правильный обход(дерево) begin	if дерево нулевое then		ничего не делать; 	else		begin		правильный обход (левое поддерево); Задача 3. Примените алгоритм правильного обхода к дереву, полученному в задаче 2
Слайды презентации

Слайд 2 Введение
Графы возникли в восемнадцатом веке, когда известный математик

ВведениеГрафы возникли в восемнадцатом веке, когда известный математик Леонард Эйлер пытался

Леонард Эйлер пытался решить теперь уже классическую задачу о

Кенигсбергских мостах. В то время в городе Кенигсберге было два острова, соединенных семью мостами с берегами реки Преголь и друг с другом так, как показано на рис. 7.1.

Слайд 3 Задача состоит в следующем: осуществить прогулку по городу

Задача состоит в следующем: осуществить прогулку по городу таким образом, чтобы,

таким образом, чтобы, пройдя ровно по одному разу по

каждому мосту, вернуться в то же место, откуда начиналась прогулка. Решая эту задачу, Эйлер изобразил Кенигсберг в виде графа, отождествив его вершины с частями города, а ребра — с мостами, которыми связаны эти части.


Слайд 4 Как мы увидим, Эйлеру удалось доказать, что искомого

Как мы увидим, Эйлеру удалось доказать, что искомого маршрута обхода города не существует.

маршрута обхода города не существует.


Слайд 5 В этом разделе мы введем стандартную терминологию, используемую

В этом разделе мы введем стандартную терминологию, используемую в теории графов,

в теории графов, и разберем несколько конкретных задач, решаемых

с помощью графов. В частности, мы познакомимся с классом графов, называемым деревьями.

Слайд 6 Деревья — естественная модель, представляющая данные, организованные в

Деревья — естественная модель, представляющая данные, организованные в иерархическую систему. Поиск

иерархическую систему. Поиск по дереву для выделения отдельных предметов

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


Слайд 7 Графы. Терминология
На рис. 7.1 изображены семь мостов

Графы. Терминология На рис. 7.1 изображены семь мостов Кенигсберга так, как

Кенигсберга так, как они были расположены в восемнадцатом веке.

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

Слайд 8 Модель задачи — это граф, состоящий из множества

Модель задачи — это граф, состоящий из множества вершин и множества

вершин и множества ребер, соединяющих вершины. Вершины А, В,

С и D символизируют берега реки и острова, а ребра а, b, с, d, е, f и g обозначают семь мостов (см. рис. 7.2). Искомый маршрут (если он существует) соответствует обходу ребер графа таким образом, что каждое из них проходится только один раз.


Слайд 9 Проход ребра, очевидно, соответствует пересечению реки по мосту.

Проход ребра, очевидно, соответствует пересечению реки по мосту.

Слайд 10 Граф, в котором найдется маршрут, начинающийся и заканчивающийся

Граф, в котором найдется маршрут, начинающийся и заканчивающийся в одной вершине,

в одной вершине, и проходящий по всем ребрам графа

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

Слайд 11 Эйлер заметил, что если в графе есть эйлеров

Эйлер заметил, что если в графе есть эйлеров цикл, то для

цикл, то для каждого ребра, ведущего в какую-то вершину,

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


Слайд 12 Кроме того, Эйлеру удалось доказать и противоположное утверждение,

Кроме того, Эйлеру удалось доказать и противоположное утверждение, так что граф,

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

некоторой последовательностью ребер, является Эйлеровым тогда и только тогда, когда все его вершины имеют четную степень. Степенью вершины v называется число δ(v) ребер, ей инцидентных.

Слайд 13
Если вершина v графа является концом ребра x,

Если вершина v графа является концом ребра x, то говорят, что

то говорят, что v и x инцидентны.
Теперь совершенно очевидно,

что в графе, моделирующем задачу о мостах Кенигсберга, эйлерова цикла найти нельзя.
Действительно, степени всех его вершин нечетны: δ(В) = δ(С) = δ(D) = 3 и δ (А) = 5.


Слайд 14
С легкой руки Эйлера графы, подобные тому, который

С легкой руки Эйлера графы, подобные тому, который мы исследовали при

мы исследовали при решении задачи о мостах, стали использоваться

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

Слайд 15 Простой граф определяется как пара G = (V,

Простой граф определяется как пара G = (V, Е), где V

Е), где V — конечное множество вершин, а Е

— конечное множество ребер, причем G не может содержать петель (ребер, начинающихся и заканчивающихся в одной вершине) и кратных ребер (кратными называются несколько ребер, соединяющих одну и ту же пару вершин).


Слайд 16
Граф, изображенный на рис. 7.2, не является простым,

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

поскольку, например, вершины А и В соединяются двумя ребрами

(как раз эти ребра и называются кратными).

Слайд 17 Две вершины u и v в простом графе

Две вершины u и v в простом графе называются смежными, если

называются смежными, если они соединяются каким-то ребром е, про

которое говорят, что оно инцидентно вершине и (и вершине v). Таким образом, мы можем представлять себе множество Е ребер как множество пар смежных вершин, определяя тем самым нерефлексивное, симметричное отношение на множестве V.


Слайд 18 Отсутствие рефлексивности связано с тем, что в простом

Отсутствие рефлексивности связано с тем, что в простом графе нет петель,

графе нет петель, т.е. ребер, оба конца которых находятся

в одной вершине. Симметричность же отношения вытекает из того факта, что ребро е, соединяющее вершину и с v, соединяет и v с и (иначе говоря, ребра не ориентированы, т. е. не имеют направления). Единственное ребро простого графа, соединяющее пару вершин u и v, мы будем обозначать как uv (или vu).

Слайд 19 Логическая матрица отношения на множестве вершин графа, которое

Логическая матрица отношения на множестве вершин графа, которое задается его ребрами,

задается его ребрами, называется матрицей смежности.
Симметричность отношения в

терминах матрицы смежности М означает, что М симметрична относительно главной диагонали. А из-за нерефлексивности этого отношения на главной диагонали матрицы М стоит символ «Л» - ложь.

Слайд 20 Пример 7.1. Нарисуйте граф G(V, E) с множеством

Пример 7.1. Нарисуйте граф G(V, E) с множеством вершин V =

вершин V = {а, b, с, d, е} и

множеством ребер Е = {ab, ae, bc, bd, ce, de}. Выпишите его матрицу смежности.
Решение. Граф G показан на рис. 7.3.

Слайд 21 Его матрица смежности имеет вид:

Его матрица смежности имеет вид:

Слайд 22 Для восстановления графа нам достаточно только тех элементов

Для восстановления графа нам достаточно только тех элементов матрицы смежности, которые

матрицы смежности, которые стоят над главной диагональю.

Подграфом графа G

= (V, Е) называется граф G' = (V', E'), для которого Е' Е и V' V.

Слайд 23 Пример 7.2. Найдите среди графов Н, К и

Пример 7.2. Найдите среди графов Н, К и L, изображенных на

L, изображенных на рис. 7.4, подграфы графа G.
Решение. Обозначим

вершины графов G, Н и К как показано на рис. 7.5. Графы Н и К — подграфы G, как видно из обозначений. Сразу можно сказать - граф L не является подграфом G, поскольку видно, что у него есть вершина степени 4, а у графа G такой нет.

Слайд 26 Маршрутом длины k в графе G называется такая

Маршрутом длины k в графе G называется такая последовательность вершин v0,

последовательность вершин v0, v1, ..., vk, что для каждого

i = 1, ..., k пара vi - 1 vi образует ребро графа.
Такой маршрут обозначается v0 v1 ... vk.
Например, 1 4 3 2 5 — это маршрут длины 4 в графе G из примера 7.2.


Слайд 27 Циклом в графе называется последовательность вершин v0, v1,

Циклом в графе называется последовательность вершин v0, v1, ..., vk, каждая

..., vk, каждая пара которых является концами одного ребра,

причем v0 = vk, а остальные вершины (и ребра) не повторяются.
Иными словами, цикл — это замкнутый маршрут, проходящий через каждую свою вершину и ребро только один раз.

Слайд 28 Пример 7.3. Найдите циклы в графе G из

Пример 7.3. Найдите циклы в графе G из примера 7.2.Решение. В

примера 7.2.
Решение. В этом графе есть два разных цикла

длины 5 (см. рис.7.5):
1 3 2 5 4 1 и 1 2 5 4 3 1.
Мы можем пройти эти циклы как в одном направлении, так и в другом, начиная с произвольной вершины цикла. Кроме того, в графе есть три разных цикла длины 4:
1 2 5 4 1, 1 2 3 4 1 и 2 5 4 3 2,
и два цикла длины 3:
1 2 3 1 и 1 3 4 1.

Слайд 29 Граф, в котором нет циклов, называется ацикличным (

Граф, в котором нет циклов, называется ацикличным ( или ациклическим). Частным

или ациклическим).

Частным случаем ациклических графов являются деревья.


Слайд 30 Граф называется связным, если любую пару его вершин

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

соединяет какой-нибудь маршрут.
Любой граф можно разбить на связные

подграфы.
Минимальное число таких связных компонент называется числом связности графа и обозначается через c(G).


Слайд 31 Вопросы связности имеют важное значение в приложениях теории

Вопросы связности имеют важное значение в приложениях теории графов к компьютерным

графов к компьютерным сетям.

Следующий алгоритм применяется для определения

числа связности графа.


Слайд 32 Алгоритм связности
Пусть G = (V, Е) — граф.

Алгоритм связностиПусть G = (V, Е) — граф. Алгоритм предназначен для

Алгоритм предназначен для вычисления значения с = c(G), т.е.

числа компонент связности данного графа G.
begin
V' := V;
с := 0;
while V' Ø do begin
выбрать у V';


Слайд 33 найти все вершины, соединенные маршрутом с у; удалить

найти все вершины, соединенные 		маршрутом с у; удалить 			вершину у из

вершину у из V' и
соответствующие ребра из Е;
с

:= с + 1;
end
end


Слайд 34 Пример 7.4. Проследите за работой алгоритма связности на

Пример 7.4. Проследите за работой алгоритма связности на графе, изображенном на

графе, изображенном на рис. 7.6.
Решение. См. табл. 7.1:

Таблица 7.1


Слайд 36 На первом шаге удалены вершины 1,6,3,8. В итоге,

На первом шаге удалены вершины 1,6,3,8. В итоге, c(G) = 3.

c(G) = 3. Соответствующие компоненты связности приведены на рис.

7.7.

Слайд 37 Гамильтоновы графы
Мы начали этот раздел с изучения

Гамильтоновы графы Мы начали этот раздел с изучения эйлеровых графов, обладающих

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

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

Слайд 38 Гамильтоновы графы служат моделью при составлении расписания движения

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

поездов, для телекоммуникационных сетей и т.д.
В отличие от

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


Слайд 39 Тем не менее, многие графы являются гамильтоновыми.
Если

Тем не менее, многие графы являются гамильтоновыми. Если в графе любая

в графе любая пара вершин соединена ребром, то такой

граф называется полным и обозначается через Kn, где n — число его вершин.
Очевидно, в любом полном графе можно найти гамильтонов цикл.


Слайд 40 Полный граф K5 изображен на рис. 7.8.
Его

Полный граф K5 изображен на рис. 7.8. Его цикл а b

цикл а b с d e а,

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

Слайд 42 Далее будет три варианта для выбора третей вершины

Далее будет три варианта для выбора третей вершины и два для

и два для четвертой, после чего мы вернемся в

вершину а. Таким образом, у нас есть 4 ∙ 3 ∙ 2 = 24 цикла.
Поскольку каждый цикл можно проходить как в одном направлении, так и в другом, то реально в графе K5 есть только 12 разных гамильтоновых циклов.


Слайд 43 Поиск гамильтонова цикла (если он существует) в произвольном

Поиск гамильтонова цикла (если он существует) в произвольном (связном) графе —

(связном) графе — задача далеко не всегда простая.

Ответ

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

Слайд 44 Пример 7.5. Покажите, что граф, изображенный на рис.

Пример 7.5. Покажите, что граф, изображенный на рис. 7.9, не является гамильтоновым.

7.9, не является гамильтоновым.


Слайд 45 Решение. Предположим, что в связном графе найдется гамильтонов

Решение. Предположим, что в связном графе найдется гамильтонов цикл. Каждая вершина

цикл.

Каждая вершина v включается в гамильтонов цикл С

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

Слайд 46 Все степени вершин данного графа — только 2

Все степени вершин данного графа — только 2 или 3. Вершины

или 3.
Вершины степени 2 должны входить в возможный

цикл вместе с обоими инцидентными с ними ребрами.
Следовательно, ребра ab, ae, cd, cb, hi, hg и ij в том или ином порядке могут входить в возможный гамильтонов цикл С, если, конечно, он существует (см. рис. 7.10).


Слайд 48 Ребро bf не может быть частью цикла С,

Ребро bf не может быть частью цикла С, поскольку каждая вершина

поскольку каждая вершина такого цикла должна иметь степень 2

(а у вершины b тогда будет степень 3).
Значит, ребра fj и fg обязаны входить в цикл С, чтобы включить в этот цикл вершину f.
Но тогда ребра je и gd никак не могут принадлежать циклу С, поскольку в противном случае в нем появятся вершины (d и e) степени 3.

Слайд 49 Это вынуждает нас включить в цикл ребро ed,

Это вынуждает нас включить в цикл ребро ed, что приводит к

что приводит к противоречию:
ребра, которые мы

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


Слайд 50
Гамильтоновы графы применяются для моделирования многих практических задач.

Гамильтоновы графы применяются для моделирования многих практических задач. Основой всех таких


Основой всех таких задач служит классическая задача коммивояжера, формулировка

которой приведена ниже.

Слайд 51
Коммивояжер должен совершить поездку по городам и вернуться

Коммивояжер должен совершить поездку по городам и вернуться обратно, побывав в

обратно, побывав в каждом городе ровно один раз, сведя

при этом затраты на передвижения к минимуму.


Слайд 52
Графическая модель задачи коммивояжера состоит из гамильтонова графа,

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

вершины которого изображают города, а ребра — связывающие их

дороги.

Слайд 53 Кроме того, каждое ребро оснащено весом, обозначающим транспортные

Кроме того, каждое ребро оснащено весом, обозначающим транспортные затраты, необходимые для

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

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


Слайд 54 Для решения задачи нам необходимо найти гамильтонов цикл

Для решения задачи нам необходимо найти гамильтонов цикл минимального общего веса.К

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

пока не известен.
Для сложных сетей число гамильтоновых циклов, которые необходимо просмотреть для выделения минимального, непомерно огромно.

Слайд 55
Однако существуют алгоритмы поиска субоптимального решения.
Субоптимальное решение необязательно

Однако существуют алгоритмы поиска субоптимального решения.Субоптимальное решение необязательно даст цикл минимального

даст цикл минимального общего веса, но найденный цикл будет,

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


Слайд 56 Алгоритм ближайшего соседа
Этот алгоритм выдает субоптимальное решение задачи

Алгоритм ближайшего соседаЭтот алгоритм выдает субоптимальное решение задачи коммивояжера, генерируя гамильтоновы

коммивояжера, генерируя гамильтоновы циклы в нагруженном графе с множеством

вершин V.
Цикл, полученный в результате работы алгоритма, будет совпадать с конечным значением переменной маршрут, а его общая длина — конечное значение переменной w.


Слайд 57 begin
выбрать v V;
маршрут := v;
w

begin	выбрать v V; 	маршрут := v; 	w := 0; 	v' :=v;	отметить

:= 0;
v' :=v;
отметить v';
while остаются неотмеченные вершины do


begin
выбрать неотмеченную вершину и,
ближайшую к v';



Слайд 58 маршрут := маршрут u;
w : = w +

маршрут := маршрут u;			w : = w + вес ребра v'u;			v'

вес ребра v'u;
v' := u;
отметить v';
end
маршрут := маршрут v;


w := w + вес ребра v'v;
end


Слайд 59 Пример 7.6. Примените алгоритм ближайшего соседа к графу,

Пример 7.6. Примените алгоритм ближайшего соседа к графу, изображенному на рис.

изображенному на рис. 7.11. За исходную вершину возьмите вершину

D.

Слайд 60 Решение. См. табл. 7.2.

Решение. См. табл. 7.2.

Таблица 7.2

Слайд 61 В результате работы алгоритма был найден гамильтонов цикл

В результате работы алгоритма был найден гамильтонов цикл D C A

D C A B D общего веса 24.
Делая

полный перебор всех циклов в этом маленьком графе, можно обнаружить еще два других гамильтоновых цикла: A B C D A общего веса 23 и A C B D A общего веса 31.

Слайд 62
В полном графе с двадцатью вершинами существует приблизительно

В полном графе с двадцатью вершинами существует приблизительно 6,1 ∙ 1016

6,1 ∙ 1016 гамильтоновых циклов, перечисление которых требует чрезвычайно

много машинной памяти и времени.


Слайд 63 Деревья
Как упоминалось ранее в этом разделе, есть

Деревья Как упоминалось ранее в этом разделе, есть класс графов, называемых

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

вычислительных приложениях.

Граф G = (V, Е) называется деревом, если он связен и ацикличен (т.е. не содержит циклов).


Слайд 64 Пусть G = (V, Е) — граф с

Пусть G = (V, Е) — граф с n вершинами и

n вершинами и т ребрами. Можно сформулировать несколько необходимых

и достаточных условий, при которых граф G является деревом:
любая пара вершин в графе G соединена единственным путем;
граф G связен и т = n – 1;
граф G связен, а удаление хотя бы одного его ребра нарушает связность графа;
граф G ацикличен, но если добавить хотя бы одно ребро, то в G появится цикл.

Слайд 65
Эквивалентность большинства из этих условий устанавливается без особого

Эквивалентность большинства из этих условий устанавливается без особого труда. Наиболее сложно

труда.
Наиболее сложно разобраться со вторым из них.
В

следующем примере мы докажем, что дерево с n вершинами имеет ровно n - 1 ребро.

Слайд 66 Пример 7.7. Докажите с помощью индукции по числу

Пример 7.7. Докажите с помощью индукции по числу вершин, что для

вершин, что для дерева T c n вершинами и

т ребрами выполнено соотношение: т = n - 1.

Слайд 67 Решение. Поскольку дерево с единственной вершиной вообще не

Решение. Поскольку дерево с единственной вершиной вообще не содержит ребер, то

содержит ребер, то доказываемое утверждение справедливо при n =

1.

Рассмотрим дерево T с n вершинами (и т ребрами), где n > 1 и предположим, что любое дерево с k < n вершинами имеет ровно k - 1 ребро.


Слайд 68 Удалим ребро из T. По третьему свойству дерево

Удалим ребро из T. По третьему свойству дерево T после этой

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

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

Слайд 69 Обозначим новые деревья через T1 и Т2. Пусть

Обозначим новые деревья через T1 и Т2. Пусть n 1 —

n 1 — количество вершин у дерева T 1,

а n2 — у Т2. Поскольку n1 + n2 = n, то n1 < n и n2 < n.
По предположению индукции дерево T1 имеет n1 - 1 ребро, а Т2 — n2 - 1.
Следовательно, исходное дерево T насчитывало (с учетом одного удаленного) (n1 - 1) + (n2 - 1) + 1 = n - 1 ребро, что и требовалось доказать.



Слайд 70
Несложно доказать, что в любом связном графе найдется

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

подграф, являющийся деревом.

Подграф графа G, являющийся деревом и

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

Слайд 71 Остовное дерево в графе G строится просто: выбираем

Остовное дерево в графе G строится просто: выбираем произвольное его ребро

произвольное его ребро и последовательно добавляем другие ребра, не

создавая при этом циклов, до тех пор, пока нельзя будет добавить никакого ребра, не получив при этом цикла.
Благодаря примеру 7.7, мы знаем, что для построения остовного дерева в графе из n вершин необходимо выбрать ровно n - 1 ребро.


Слайд 72 Пример 7.8. Найдите два разных остовных дерева в

Пример 7.8. Найдите два разных остовных дерева в графе, изображенном на рис. 7.12.

графе, изображенном на рис. 7.12.


Слайд 73 Решение. В этом графе существует несколько остовных деревьев.

Решение. В этом графе существует несколько остовных деревьев. Одно из них

Одно из них получается последовательным выбором ребер: а, b,

d и f. Другое — b, с, е и d. Названные деревья показаны на рис. 7.13.

Слайд 74 Процесс, описанный в примере 7.8, можно приспособить для

Процесс, описанный в примере 7.8, можно приспособить для решения задачи поиска

решения задачи поиска кратчайшего соединения:
Нужно построить железнодорожную сеть, связывающую

некоторое число городов. Известна стоимость строительства отрезка путей между любой парой городов. Требуется найти сеть минимальной стоимости.


Слайд 75 На языке теории графов нам нужно в нагруженном

На языке теории графов нам нужно в нагруженном графе найти остовное

графе найти остовное дерево наименьшего общего веса. Такое дерево

принято называть минимальным остовным деревом или, сокращенно, МОД.

Слайд 76 В отличие от задачи коммивояжера, здесь есть эффективный

В отличие от задачи коммивояжера, здесь есть эффективный алгоритм, находящий действительно

алгоритм, находящий действительно минимальное остовное дерево. Он похож на

алгоритм Прима, с которым мы познакомились в главе 1 при решении задачи поиска кратчайшего соединения для набора из шести шотландских городов.


Слайд 78 Алгоритм поиска минимального остовного дерева
Пусть
G = (V, Е)

Алгоритм поиска минимального остовного дереваПустьG = (V, Е) — связный взвешенный

— связный взвешенный граф. Алгоритм строит МОД в графе

G, последовательно выбирая ребра наименьшего возможного веса до образования остовного дерева. МОД в памяти компьютера хранится в виде множества T ребер.



Слайд 79 begin
е : = ребро графа G с наименьшим

begin	е : = ребро графа G с наименьшим весом; 			T :=

весом;
T := {e};
Е' := Е \ {е}


while E' Ø begin


Слайд 80 е': = ребро из Е' наименьшего веса; T:=T

е': = ребро из Е' наименьшего веса; T:=T {e'};		Е':= множество ребер

{e'};
Е':= множество ребер из Е' \ {Т}, чье

добавление к Т не ведет к образованию циклов;
end
end



Слайд 81 Пример 7.9. В таблице 7.3 дано расстояние (в

Пример 7.9. В таблице 7.3 дано расстояние (в милях) между пятью

милях) между пятью деревнями А, В, С, D и

Е. Найдите минимальное остовное дерево.
Таблица 7.3

Слайд 82 Решение. Ребра выбираются следующим образом: первое — ребро

Решение. Ребра выбираются следующим образом: первое — ребро DE веса 2;

DE веса 2; второе — АС веса 3; третье

— СЕ веса 7. На этой стадии строящееся дерево выглядит так, как на рис. 7.14

Слайд 83 Следующие по весу ребра — AD, АЕ и

Следующие по весу ребра — AD, АЕ и CD, каждое из

CD, каждое из которых имеет вес 9. Однако какое

бы из них мы ни добавили, получится цикл. Поэтому перечисленные ребра следует исключить из числа доступных для строительства. Далее идут ребра ВС и BD веса 11. Можно присоединить любое из них, получив при этом два разных МОД: {АС, ВС, СЕ, DE} или {AC, BD, CE, DE} веса 23 каждое.

Слайд 84 Зачастую нам хотелось бы иметь деревья, представляющие информацию

Зачастую нам хотелось бы иметь деревья, представляющие информацию с учетом естественной

с учетом естественной иерархической структуры, такие, как, например, генеалогическое

древо (рис. 7.15). На нем показаны некоторые члены семьи Бернулли, каждый из которых был известным швейцарским математиком.


Слайд 85 Генеалогическое древо можно изобразить и более сжато. Схема,

Генеалогическое древо можно изобразить и более сжато. Схема, приведенная на рис.

приведенная на рис. 7.16, представляет собой пример так называемого

дерева с корнем. Деревом с корнем называется дерево с одной выделенной вершиной. Именно эта выделенная вершина и является корнем дерева.

Слайд 86 Корень, в некотором смысле, можно назвать «величайшей» вершиной

Корень, в некотором смысле, можно назвать «величайшей» вершиной (например, родоначальник математиков

(например, родоначальник математиков Бернулли). Вершины дерева, лежащие непосредственно под

данной, называются сыновьями. С другой стороны, вершина, стоящая непосредственно перед сыном, называется ее отцом.


Слайд 89 Дерево с корнем можно определить рекуррентным образом. Отдельная

Дерево с корнем можно определить рекуррентным образом. Отдельная вершина является деревом

вершина является деревом с корнем (она же служит и

корнем такого дерева). Если T1, T2, …, Tk — несвязанные друг с другом деревья с корнями v1, v2, …, vk, то граф, получающийся присоединением новой вершины v к каждой из вершин v1, v2, …, vk отдельным ребром, является деревом Т с корнем v.

Слайд 90 Вершины v 1,…, vk графа Т — это

Вершины v 1,…, vk графа Т — это сыновья корня v.

сыновья корня v. Мы изображаем такое дерево с корнем,

расположенным наверху, и сыновьями, стоящими ниже, непосредственно под корнем (см. рис. 7.17). Каждую вершину дерева с корнем можно рассматривать как корень другого дерева, которое «растет» из него. Мы будем называть его поддеревом дерева Т.


Слайд 91 Как мы уже говорили, вершина на самом верху

Как мы уже говорили, вершина на самом верху дерева — его

дерева — его корень, а вот те, которые находятся

в самом низу дерева (и не имеют сыновей) принято называть листьями. Остальные вершины, отличные от корня и листьев, называют внутренними.

Слайд 92 Область применения деревьев с корнем обширна. Это, например,

Область применения деревьев с корнем обширна. Это, например, и информатика, и

и информатика, и биология, и менеджмент. Для приложения к

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


Слайд 94 Таким образом, можно сказать, что каждой вершине двоичного

Таким образом, можно сказать, что каждой вершине двоичного дерева с корнем

дерева с корнем соответствует не более, чем два поддерева,

которые принято называть левым и правым поддеревьями этой вершины.

Слайд 95 Если оказалось, что у какой-то вершины дерева отсутствует

Если оказалось, что у какой-то вершины дерева отсутствует потомок слева, то

потомок слева, то ее левое поддерево называют нулевым, деревом

(т.е. нулевое дерево — это дерево без единой вершины). Аналогично, если у вершины отсутствует правый потомок, то ее правое поддерево будет нулевым.


Слайд 96 Пример 7.10. Пусть T — двоичное дерево с

Пример 7.10. Пусть T — двоичное дерево с корнем, изображенное на рис. 7.18.

корнем, изображенное на рис. 7.18.


Слайд 97 Определите
(а) корень T;
(б) корень левого поддерева вершины В;
(в) листья Т;
(г) сыновей вершины

Определите(а)	корень T;(б)	корень левого поддерева вершины В;(в)	листья Т;(г)	сыновей вершины С.Нарисуйте двоичное дерево

С.
Нарисуйте двоичное дерево с корнем Т', полученное из Т

перестановкой левых и правых поддеревьев у каждой вершины.

Слайд 98 Решение.(а) А; (б) D; (в) G, Н, Е,

Решение.(а) А; (б) D; (в) G, Н, Е, I и J;

I и J; (г) F.
Двоичное дерево с корнем Т'

начерчено на рис. 7.19.

Слайд 99 Краткое содержание главы
Граф G = (V, Е) состоит

Краткое содержание главыГраф G = (V, Е) состоит из множества V,

из множества V, чьи элементы называют вершинами графа, и

множества Е его ребер, соединяющих некоторые пары вершин.
Вершины u и v графа называют смежными, если они соединены каким-то ребром е, про которое говорят, что оно инцидентно вершинам u и v.
Степенью вершины v считают число δ(v) ребер графа, инцидентных V.

Слайд 100 Граф, в котором существует маршрут (называемый эйлеровым), начинающийся

Граф, в котором существует маршрут (называемый эйлеровым), начинающийся и заканчивающийся в

и заканчивающийся в одной и той же вершине и

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

Слайд 101 Лемма об эстафете утверждает, что сумма степеней вершин

Лемма об эстафете утверждает, что сумма степеней вершин произвольного графа G

произвольного графа G = (V, Е) равна удвоенному числу

его ребер.
Простым принято называть граф G = (V, Е) с конечным множеством вершин V и конечным множеством ребер Е, в котором нет петель и кратных ребер.


Слайд 102
Логическая матрица отношения на множестве вершин простого графа

Логическая матрица отношения на множестве вершин простого графа G, которое задается

G, которое задается его ребрами, называется матрицей смежности.
Подграфом графа

G = (V, Е) называют граф G' = (V', Е'), в котором Е' Е и V' V.




Слайд 103 Маршрутом длины k в графе называют такую последовательность

Маршрутом длины k в графе называют такую последовательность различных вершин v0,

различных вершин v0, v1, ..., vk, в которой каждая

пара соседних вершин vi -1 vi соединена ребром.
Циклом в графе является замкнутый маршрут v0, v1, ..., v0, у которого все вершины, кроме первой и последней, различны.

Слайд 104 Граф, не содержащий циклов, называют ацикличным.
Связным является тот

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

граф, в котором каждая пара вершин соединена маршрутом.
Количество компонент

связности графа можно подсчитать с помощью алгоритма связности.


Слайд 105 Гамильтоновым называют такой цикл в графе, который проходит

Гамильтоновым называют такой цикл в графе, который проходит через каждую вершину

через каждую вершину графа, причем только один раз. Граф,

в котором существует гамильтонов цикл, называют гамильтоновым.

Слайд 106 Задача коммивояжера состоит в поиске гамильтонова цикла минимального

Задача коммивояжера состоит в поиске гамильтонова цикла минимального общего веса в

общего веса в нагруженном графе. Алгоритм ближайшего соседа позволяет

найти субоптимальное решение задачи коммивояжера.


Слайд 107 Связный ацикличный граф G = (V, Е) является

Связный ацикличный граф G = (V, Е) является деревом. Следующие утверждения

деревом. Следующие утверждения о связном графе G = (V,

Е) с n вершинами и т ребрами эквивалентны:
(а) G — дерево;
(б) любую пару вершин G связывает единственный путь;
(в) G связен и т = n - 1;
(г) G связен, а удаление любого его ребра нарушает это свойство;
(д) G ацикличен, но соединяя любую пару вершин новым ребром, мы получаем цикл.

Слайд 108 Остовным деревом графа G называют такой его подграф,

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

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

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

Слайд 109 Дерево с одной выделенной вершиной называют деревом с

Дерево с одной выделенной вершиной называют деревом с корнем, а выделенную

корнем, а выделенную вершину — его корнем. Вершины, стоящие

непосредственно под вершиной v (и соединенные с ней ребрами), называются сыновьями вершины v.

Слайд 110 Вершины, расположенные в самом низу дерева (они не

Вершины, расположенные в самом низу дерева (они не имеют сыновей), называются

имеют сыновей), называются листьями. Вершины, отличные от корня и

листьев, называют внутренними вершинами графа. Нулевое дерево — это дерево, не имеющее ни одной вершины.


Слайд 111 Каждая вершина дерева с корнем Т является корнем

Каждая вершина дерева с корнем Т является корнем какого-то другого дерева,

какого-то другого дерева, называемого поддеревом Т. В двоичном дереве

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

Слайд 112 Глубиной вершины v дерева с корнем Т принято

Глубиной вершины v дерева с корнем Т принято считать длину единственного

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

графа Т называют максимальную глубину его вершин.


Слайд 113 Сортировка и поиск
Двоичные деревья с корнем очень полезны

Сортировка и поискДвоичные деревья с корнем очень полезны при решении задач

при решении задач о выборе, в частности, о выборе

такого сорта, при котором нужно классифицировать упорядоченные данные или вести в них поиск.

Слайд 114 Упорядоченные данные, такие как множество чисел, упорядоченных по

Упорядоченные данные, такие как множество чисел, упорядоченных по величине или множество

величине или множество строк литер, упорядоченных лексикографически (в алфавитном

порядке), можно организовать в виде вершин двоичного дерева с корнем в соответствии с их порядком.


Слайд 115 При этом мы стремимся к тому, чтобы данные,

При этом мы стремимся к тому, чтобы данные, стоящие в левом

стоящие в левом поддереве данной вершины v были бы

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

Слайд 116 Например, в дереве двоичного поиска, приведенном на рис.

Например, в дереве двоичного поиска, приведенном на рис. 7.26, слова фразы

7.26, слова фразы «У МОЕГО КОМПЬЮТЕРА ЕСТЬ ЧИП НА

МАТЕРИНСКОЙ ПЛАТЕ» организованы именно таким образом.


Слайд 117 Заметим, что каждое слово в левом поддереве любой

Заметим, что каждое слово в левом поддереве любой вершины предшествует (относительно

вершины предшествует (относительно алфавитного порядка) слову, стоящему в этой

вершине, а каждое слово ее правого поддерева следует за словом выбранной вершины.


Слайд 119 Преимущество организации упорядоченных данных в виде двоичного дерева

Преимущество организации упорядоченных данных в виде двоичного дерева поиска заключается в

поиска заключается в возможности создания эффективного алгоритма поиска каких-то

конкретных данных, включения новых данных в дерево и печати всей информации, содержащейся в дереве в виде упорядоченного списка.


Слайд 120 Предположим, что в университете хранится список студентов (упорядоченный

Предположим, что в университете хранится список студентов (упорядоченный в алфавитном порядке),

в алфавитном порядке), в котором кроме фамилий и имен

имеются дополнительные важные сведения о студентах.

Слайд 121 Допустим также, что возникла необходимость найти какую-то информацию

Допустим также, что возникла необходимость найти какую-то информацию в списке или

в списке или добавить новые записи к списку. Мы

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


Слайд 122 Записи о студентах организованы в двоичное дерево поиска

Записи о студентах организованы в двоичное дерево поиска (каждая запись соответствует

(каждая запись соответствует одной вершине), и наши алгоритмы будут

исследовать вершины этого дерева. Поскольку каждая вершина является также и корнем некоторого двоичного дерева поиска, алгоритмы будут последовательно проверять левые и правые поддеревья вершин.

Слайд 123 Чтобы это осуществить, необходимо приписать каждой вершине некоторый

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

ключ для идентификации и ссылок на ее левое и

правое поддеревья (в структурах данных для этих целей используются так называемые дважды связанные списки).


Слайд 124 Из всех ключей организуется линейно упорядоченное множество (в

Из всех ключей организуется линейно упорядоченное множество (в нашей ситуации оно

нашей ситуации оно упорядочено лексикографически).
Алгоритм поиска определяет, является ли

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

Слайд 125 Поиск (дерево)
begin
if дерево нулевое then
поиск := ложь;

Поиск (дерево) 	begin		if дерево нулевое then			поиск := ложь; 		else			if ключ поиска


else
if ключ поиска = ключ корня then
поиск := истина;


else


Слайд 126 if ключ поиска < ключ корня then
поиск :=

if ключ поиска < ключ корня then		поиск := поиск (левое поддерево); 	else		поиск := поиск (правое поддерево);	end

поиск (левое поддерево);
else
поиск := поиск (правое поддерево);
end


Слайд 127 Задача 1. Проследите за работой алгоритма над двоичным

Задача 1. Проследите за работой алгоритма над двоичным деревом поиска, изображенном

деревом поиска, изображенном на рис. 7.27. Известно, что ключ

поиска — буква Л, а ключи вершин упорядочены лексикографически.


Слайд 128 Решение. Поскольку R > К, то поиск продолжается

Решение. Поскольку R > К, то поиск продолжается в правом поддереве

в правом поддереве вершины К. Так как R

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



Слайд 130 Алгоритм вставки вставляет новые вершины (ключи вставок) в

Алгоритм вставки вставляет новые вершины (ключи вставок) в двоичное дерево поиска,

двоичное дерево поиска, создавая при этом новую вершину слева

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

Слайд 131 Вставка (запись, дерево)
begin
if дерево нулевое then
добавить новую

Вставка (запись, дерево) 	begin		if дерево нулевое then			добавить новую вершину; 		else			if ключ

вершину;
else
if ключ вставки = ключ корня then
вывести на

печать:
«запись содержится в дереве»;
else


Слайд 132 if ключ вставки < ключ корня then
вставка

if ключ вставки < ключ корня then 			вставка := вставка (запись,

:= вставка (запись, левое поддерево);
else
вставка := вставка (запись, правое

поддерево);
end


Слайд 133 Задача 2. Проследите за работой алгоритма вставки на

Задача 2. Проследите за работой алгоритма вставки на примере вершин R,

примере вершин R, А и L в дерево из

задачи 1.

Слайд 134 Решение. Поскольку R > К, мы применяем алгоритм

Решение. Поскольку R > К, мы применяем алгоритм вставки к правому

вставки к правому поддереву вершины К. Далее мы видим,

что R < Т. Значит, алгоритм вставки переключается на левое поддерево вершины Т. Так как R > М и правое поддерево вершины М нулевое, то мы ставим вершину R справа от М и получаем дерево, изображенное на рис. 7.28. Теперь вставим А и L, построив дерево, показанное на рис. 7.29.


Слайд 136 Алгоритм вставки можно использовать для создания двоичного дерева

Алгоритм вставки можно использовать для создания двоичного дерева поиска, начиная с

поиска, начиная с нулевого дерева и последовательно добавляя новые

данные в удобном для нас порядке.

Слайд 137 Например, двоичное дерево поиска на рис. 7.26 является

Например, двоичное дерево поиска на рис. 7.26 является результатом применения алгоритма

результатом применения алгоритма вставки к нулевому дереву в процессе

добавления слов фразы «У МОЕГО КОМПЬЮТЕРА ЕСТЬ ЧИП НА МАТЕРИНСКОЙ ПЛАТЕ» в том порядке, в котором они в ней записаны.

Слайд 139 Алгоритм правильного обхода выводит на печать всю информацию,

Алгоритм правильного обхода выводит на печать всю информацию, содержащуюся в двоичном

содержащуюся в двоичном дереве поиска, в надлежащем порядке. При

этом все вершины дерева осматриваются в определенном порядке. Алгоритм работает следующим образом.

Слайд 140 Для каждой вершины, начиная с корня, печатается вся

Для каждой вершины, начиная с корня, печатается вся информация, содержащаяся в

информация, содержащаяся в вершинах левого поддерева. Затем выводится информация,

хранящаяся в этой вершине, и наконец, информация, соответствующая вершинам правого поддерева.


Слайд 141 Правильный обход(дерево)
begin
if дерево нулевое then
ничего не делать;

Правильный обход(дерево) begin	if дерево нулевое then		ничего не делать; 	else		begin		правильный обход (левое


else
begin
правильный обход (левое поддерево);
напечатать корневой ключ;
правильный обход (правое

поддерево);
end
end

Слайд 142 Задача 3. Примените алгоритм правильного обхода к дереву,

Задача 3. Примените алгоритм правильного обхода к дереву, полученному в задаче

полученному в задаче 2 после вставки R, А и

L.
Решение. После работы алгоритма над указанным деревом получается список: А, С, К, L, М, R, Т, V.
Он соответствует обходу дерева против часовой стрелки (рис. 7.30) и печати информации, содержащейся в вершинах, как только Вы прошли под вершиной.

  • Имя файла: tema-grafy.pptx
  • Количество просмотров: 296
  • Количество скачиваний: 0