- Главная
- Разное
- Бизнес и предпринимательство
- Образование
- Развлечения
- Государство
- Спорт
- Графика
- Культурология
- Еда и кулинария
- Лингвистика
- Религиоведение
- Черчение
- Физкультура
- ИЗО
- Психология
- Социология
- Английский язык
- Астрономия
- Алгебра
- Биология
- География
- Геометрия
- Детские презентации
- Информатика
- История
- Литература
- Маркетинг
- Математика
- Медицина
- Менеджмент
- Музыка
- МХК
- Немецкий язык
- ОБЖ
- Обществознание
- Окружающий мир
- Педагогика
- Русский язык
- Технология
- Физика
- Философия
- Химия
- Шаблоны, картинки для презентаций
- Экология
- Экономика
- Юриспруденция
Что такое findslide.org?
FindSlide.org - это сайт презентаций, докладов, шаблонов в формате PowerPoint.
Обратная связь
Email: Нажмите что бы посмотреть
Презентация на тему Тема Графы
Содержание
- 2. ВведениеГрафы возникли в восемнадцатом веке, когда известный
- 3. Задача состоит в следующем: осуществить прогулку по
- 4. Как мы увидим, Эйлеру удалось доказать, что искомого маршрута обхода города не существует.
- 5. В этом разделе мы введем стандартную терминологию,
- 6. Деревья — естественная модель, представляющая данные, организованные
- 7. Графы. Терминология На рис. 7.1 изображены семь
- 8. Модель задачи — это граф, состоящий из
- 9. Проход ребра, очевидно, соответствует пересечению реки по мосту.
- 10. Граф, в котором найдется маршрут, начинающийся и
- 11. Эйлер заметил, что если в графе есть
- 12. Кроме того, Эйлеру удалось доказать и противоположное
- 13. Если вершина v графа является концом ребра
- 14. С легкой руки Эйлера графы, подобные тому,
- 15. Простой граф определяется как пара G =
- 16. Граф, изображенный на рис. 7.2, не является
- 17. Две вершины u и v в простом
- 18. Отсутствие рефлексивности связано с тем, что в
- 19. Логическая матрица отношения на множестве вершин графа,
- 20. Пример 7.1. Нарисуйте граф G(V, E) с
- 21. Его матрица смежности имеет вид:
- 22. Для восстановления графа нам достаточно только тех
- 23. Пример 7.2. Найдите среди графов Н, К
- 26. Маршрутом длины k в графе G называется
- 27. Циклом в графе называется последовательность вершин v0,
- 28. Пример 7.3. Найдите циклы в графе G
- 29. Граф, в котором нет циклов, называется ацикличным
- 30. Граф называется связным, если любую пару его
- 31. Вопросы связности имеют важное значение в приложениях
- 32. Алгоритм связностиПусть G = (V, Е) —
- 33. найти все вершины, соединенные маршрутом с у;
- 34. Пример 7.4. Проследите за работой алгоритма связности
- 36. На первом шаге удалены вершины 1,6,3,8. В
- 37. Гамильтоновы графы Мы начали этот раздел с
- 38. Гамильтоновы графы служат моделью при составлении расписания
- 39. Тем не менее, многие графы являются гамильтоновыми.
- 40. Полный граф K5 изображен на рис. 7.8.
- 42. Далее будет три варианта для выбора третей
- 43. Поиск гамильтонова цикла (если он существует) в
- 44. Пример 7.5. Покажите, что граф, изображенный на рис. 7.9, не является гамильтоновым.
- 45. Решение. Предположим, что в связном графе найдется
- 46. Все степени вершин данного графа — только
- 48. Ребро bf не может быть частью цикла
- 49. Это вынуждает нас включить в цикл ребро
- 50. Гамильтоновы графы применяются для моделирования многих практических
- 51. Коммивояжер должен совершить поездку по городам и
- 52. Графическая модель задачи коммивояжера состоит из гамильтонова
- 53. Кроме того, каждое ребро оснащено весом, обозначающим
- 54. Для решения задачи нам необходимо найти гамильтонов
- 55. Однако существуют алгоритмы поиска субоптимального решения.Субоптимальное решение
- 56. Алгоритм ближайшего соседаЭтот алгоритм выдает субоптимальное решение
- 57. begin выбрать v V; маршрут := v;
- 58. маршрут := маршрут u; w : = w
- 59. Пример 7.6. Примените алгоритм ближайшего соседа к
- 60. Решение. См. табл. 7.2.
- 61. В результате работы алгоритма был найден гамильтонов
- 62. В полном графе с двадцатью вершинами существует
- 63. Деревья Как упоминалось ранее в этом разделе,
- 64. Пусть G = (V, Е) — граф
- 65. Эквивалентность большинства из этих условий устанавливается без
- 66. Пример 7.7. Докажите с помощью индукции по
- 67. Решение. Поскольку дерево с единственной вершиной вообще
- 68. Удалим ребро из T. По третьему свойству
- 69. Обозначим новые деревья через T1 и Т2.
- 70. Несложно доказать, что в любом связном графе
- 71. Остовное дерево в графе G строится просто:
- 72. Пример 7.8. Найдите два разных остовных дерева в графе, изображенном на рис. 7.12.
- 73. Решение. В этом графе существует несколько остовных
- 74. Процесс, описанный в примере 7.8, можно приспособить
- 75. На языке теории графов нам нужно в
- 76. В отличие от задачи коммивояжера, здесь есть
- 78. Алгоритм поиска минимального остовного дереваПустьG = (V,
- 79. begin е : = ребро графа G с
- 80. е': = ребро из Е' наименьшего веса;
- 81. Пример 7.9. В таблице 7.3 дано расстояние
- 82. Решение. Ребра выбираются следующим образом: первое —
- 83. Следующие по весу ребра — AD, АЕ
- 84. Зачастую нам хотелось бы иметь деревья, представляющие
- 85. Генеалогическое древо можно изобразить и более сжато.
- 86. Корень, в некотором смысле, можно назвать «величайшей»
- 89. Дерево с корнем можно определить рекуррентным образом.
- 90. Вершины v 1,…, vk графа Т —
- 91. Как мы уже говорили, вершина на самом
- 92. Область применения деревьев с корнем обширна. Это,
- 94. Таким образом, можно сказать, что каждой вершине
- 95. Если оказалось, что у какой-то вершины дерева
- 96. Пример 7.10. Пусть T — двоичное дерево с корнем, изображенное на рис. 7.18.
- 97. Определите(а) корень T;(б) корень левого поддерева вершины В;(в) листья Т;(г) сыновей
- 98. Решение.(а) А; (б) D; (в) G, Н,
- 99. Краткое содержание главыГраф G = (V, Е)
- 100. Граф, в котором существует маршрут (называемый эйлеровым),
- 101. Лемма об эстафете утверждает, что сумма степеней
- 102. Логическая матрица отношения на множестве вершин простого
- 103. Маршрутом длины k в графе называют такую
- 104. Граф, не содержащий циклов, называют ацикличным.Связным является
- 105. Гамильтоновым называют такой цикл в графе, который
- 106. Задача коммивояжера состоит в поиске гамильтонова цикла
- 107. Связный ацикличный граф G = (V, Е)
- 108. Остовным деревом графа G называют такой его
- 109. Дерево с одной выделенной вершиной называют деревом
- 110. Вершины, расположенные в самом низу дерева (они
- 111. Каждая вершина дерева с корнем Т является
- 112. Глубиной вершины v дерева с корнем Т
- 113. Сортировка и поискДвоичные деревья с корнем очень
- 114. Упорядоченные данные, такие как множество чисел, упорядоченных
- 115. При этом мы стремимся к тому, чтобы
- 116. Например, в дереве двоичного поиска, приведенном на
- 117. Заметим, что каждое слово в левом поддереве
- 119. Преимущество организации упорядоченных данных в виде двоичного
- 120. Предположим, что в университете хранится список студентов
- 121. Допустим также, что возникла необходимость найти какую-то
- 122. Записи о студентах организованы в двоичное дерево
- 123. Чтобы это осуществить, необходимо приписать каждой вершине
- 124. Из всех ключей организуется линейно упорядоченное множество
- 125. Поиск (дерево) begin if дерево нулевое then поиск :=
- 126. if ключ поиска < ключ корня then поиск := поиск (левое поддерево); else поиск := поиск (правое поддерево); end
- 127. Задача 1. Проследите за работой алгоритма над
- 128. Решение. Поскольку R > К, то поиск
- 130. Алгоритм вставки вставляет новые вершины (ключи вставок)
- 131. Вставка (запись, дерево) begin if дерево нулевое then добавить
- 132. if ключ вставки < ключ корня then
- 133. Задача 2. Проследите за работой алгоритма вставки
- 134. Решение. Поскольку R > К, мы применяем
- 136. Алгоритм вставки можно использовать для создания двоичного
- 137. Например, двоичное дерево поиска на рис. 7.26
- 139. Алгоритм правильного обхода выводит на печать всю
- 140. Для каждой вершины, начиная с корня, печатается
- 141. Правильный обход(дерево) begin if дерево нулевое then ничего не
- 142. Задача 3. Примените алгоритм правильного обхода к
- 143. Скачать презентацию
- 144. Похожие презентации
ВведениеГрафы возникли в восемнадцатом веке, когда известный математик Леонард Эйлер пытался решить теперь уже классическую задачу о Кенигсбергских мостах. В то время в городе Кенигсберге было два острова, соединенных семью мостами с берегами реки Преголь и
Слайд 3 Задача состоит в следующем: осуществить прогулку по городу
таким образом, чтобы, пройдя ровно по одному разу по
каждому мосту, вернуться в то же место, откуда начиналась прогулка. Решая эту задачу, Эйлер изобразил Кенигсберг в виде графа, отождествив его вершины с частями города, а ребра — с мостами, которыми связаны эти части.Слайд 5 В этом разделе мы введем стандартную терминологию, используемую
в теории графов, и разберем несколько конкретных задач, решаемых
с помощью графов. В частности, мы познакомимся с классом графов, называемым деревьями.Слайд 6 Деревья — естественная модель, представляющая данные, организованные в
иерархическую систему. Поиск по дереву для выделения отдельных предметов
и сортировка данных в дереве представляют собой важные точки приложения усилий в информатике. В приложении к этому разделу мы займемся сортировкой и поиском данных, организованных в деревья.
Слайд 7
Графы. Терминология
На рис. 7.1 изображены семь мостов
Кенигсберга так, как они были расположены в восемнадцатом веке.
В задаче, к которой обратился Эйлер, спрашивается: можно ли найти маршрут прогулки, который проходит ровно один раз по каждому из мостов и начинается и заканчивается в одном и том же месте города?Слайд 8 Модель задачи — это граф, состоящий из множества
вершин и множества ребер, соединяющих вершины. Вершины А, В,
С и D символизируют берега реки и острова, а ребра а, b, с, d, е, f и g обозначают семь мостов (см. рис. 7.2). Искомый маршрут (если он существует) соответствует обходу ребер графа таким образом, что каждое из них проходится только один раз.Слайд 10 Граф, в котором найдется маршрут, начинающийся и заканчивающийся
в одной вершине, и проходящий по всем ребрам графа
ровно один раз, называется эйлеровым графом. Последовательность вершин (может быть и с повторениями), через которые проходит искомый маршрут, как и сам маршрут, называется эйлеровым циклом.Слайд 11 Эйлер заметил, что если в графе есть эйлеров
цикл, то для каждого ребра, ведущего в какую-то вершину,
должно найтись другое ребро, выходящее из этой вершины, и получил из этого простого наблюдения такой вывод: если в данном графе существует эйлеров цикл, то к каждой вершине должно подходить четное число ребер.Слайд 12 Кроме того, Эйлеру удалось доказать и противоположное утверждение,
так что граф, в котором любая пара вершин связана
некоторой последовательностью ребер, является Эйлеровым тогда и только тогда, когда все его вершины имеют четную степень. Степенью вершины v называется число δ(v) ребер, ей инцидентных.
Слайд 13
Если вершина v графа является концом ребра x,
то говорят, что v и x инцидентны.
Теперь совершенно очевидно,
что в графе, моделирующем задачу о мостах Кенигсберга, эйлерова цикла найти нельзя. Действительно, степени всех его вершин нечетны: δ(В) = δ(С) = δ(D) = 3 и δ (А) = 5.
Слайд 14
С легкой руки Эйлера графы, подобные тому, который
мы исследовали при решении задачи о мостах, стали использоваться
при решении многих практических задач, а их изучение выросло в значительную область математики.Слайд 15 Простой граф определяется как пара G = (V,
Е), где V — конечное множество вершин, а Е
— конечное множество ребер, причем G не может содержать петель (ребер, начинающихся и заканчивающихся в одной вершине) и кратных ребер (кратными называются несколько ребер, соединяющих одну и ту же пару вершин).
Слайд 16
Граф, изображенный на рис. 7.2, не является простым,
поскольку, например, вершины А и В соединяются двумя ребрами
(как раз эти ребра и называются кратными).Слайд 17 Две вершины u и v в простом графе
называются смежными, если они соединяются каким-то ребром е, про
которое говорят, что оно инцидентно вершине и (и вершине v). Таким образом, мы можем представлять себе множество Е ребер как множество пар смежных вершин, определяя тем самым нерефлексивное, симметричное отношение на множестве V.Слайд 18 Отсутствие рефлексивности связано с тем, что в простом
графе нет петель, т.е. ребер, оба конца которых находятся
в одной вершине. Симметричность же отношения вытекает из того факта, что ребро е, соединяющее вершину и с v, соединяет и v с и (иначе говоря, ребра не ориентированы, т. е. не имеют направления). Единственное ребро простого графа, соединяющее пару вершин u и v, мы будем обозначать как uv (или vu).Слайд 19 Логическая матрица отношения на множестве вершин графа, которое
задается его ребрами, называется матрицей смежности.
Симметричность отношения в
терминах матрицы смежности М означает, что М симметрична относительно главной диагонали. А из-за нерефлексивности этого отношения на главной диагонали матрицы М стоит символ «Л» - ложь.Слайд 20 Пример 7.1. Нарисуйте граф G(V, E) с множеством
вершин V = {а, b, с, d, е} и
множеством ребер Е = {ab, ae, bc, bd, ce, de}. Выпишите его матрицу смежности.Решение. Граф G показан на рис. 7.3.
Слайд 22 Для восстановления графа нам достаточно только тех элементов
матрицы смежности, которые стоят над главной диагональю.
Подграфом графа G
= (V, Е) называется граф G' = (V', E'), для которого Е' Е и V' V.Слайд 23 Пример 7.2. Найдите среди графов Н, К и
L, изображенных на рис. 7.4, подграфы графа G.
Решение. Обозначим
вершины графов G, Н и К как показано на рис. 7.5. Графы Н и К — подграфы G, как видно из обозначений. Сразу можно сказать - граф L не является подграфом G, поскольку видно, что у него есть вершина степени 4, а у графа G такой нет.Слайд 26 Маршрутом длины k в графе G называется такая
последовательность вершин v0, v1, ..., vk, что для каждого
i = 1, ..., k пара vi - 1 vi образует ребро графа.Такой маршрут обозначается v0 v1 ... vk.
Например, 1 4 3 2 5 — это маршрут длины 4 в графе G из примера 7.2.
Слайд 27 Циклом в графе называется последовательность вершин v0, v1,
..., vk, каждая пара которых является концами одного ребра,
причем v0 = vk, а остальные вершины (и ребра) не повторяются.Иными словами, цикл — это замкнутый маршрут, проходящий через каждую свою вершину и ребро только один раз.
Слайд 28 Пример 7.3. Найдите циклы в графе G из
примера 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, Е) — граф.
Алгоритм предназначен для вычисления значения с = c(G), т.е.
числа компонент связности данного графа G.begin
V' := V;
с := 0;
while V' Ø do begin
выбрать у V';
Слайд 33 найти все вершины, соединенные маршрутом с у; удалить
вершину у из V' и
соответствующие ребра из Е;
с
:= с + 1; end
end
Слайд 34 Пример 7.4. Проследите за работой алгоритма связности на
графе, изображенном на рис. 7.6.
Решение. См. табл. 7.1:
Таблица 7.1Слайд 36 На первом шаге удалены вершины 1,6,3,8. В итоге,
c(G) = 3. Соответствующие компоненты связности приведены на рис.
7.7.
Слайд 37
Гамильтоновы графы
Мы начали этот раздел с изучения
эйлеровых графов, обладающих замкнутым маршрутом, который проходит по всем
ребрам графа ровно один раз. Похожая задача состоит в поиске цикла, проходящего через каждую вершину графа в точности один раз. Такой цикл, если он существует, называется гамильтоновым, а соответствующий граф — гамильтоновым графом.Слайд 38 Гамильтоновы графы служат моделью при составлении расписания движения
поездов, для телекоммуникационных сетей и т.д.
В отличие от
задачи Эйлера, простого критерия гамильтоновости графа пока не известно. Поиск хорошего критерия остается одной из главных нерешенных задач теории графов.
Слайд 39
Тем не менее, многие графы являются гамильтоновыми.
Если
в графе любая пара вершин соединена ребром, то такой
граф называется полным и обозначается через Kn, где n — число его вершин.Очевидно, в любом полном графе можно найти гамильтонов цикл.
Слайд 40
Полный граф K5 изображен на рис. 7.8.
Его
цикл а b с d e а,
очевидно, является гамильтоновым.В нем есть и другие гамильтоновы циклы.
Поскольку каждая вершина смежна с остальными, то начиная с вершины а, в качестве второй вершины цикла можно выбрать любую из четырех оставшихся вершин.
Слайд 42 Далее будет три варианта для выбора третей вершины
и два для четвертой, после чего мы вернемся в
вершину а. Таким образом, у нас есть 4 ∙ 3 ∙ 2 = 24 цикла.Поскольку каждый цикл можно проходить как в одном направлении, так и в другом, то реально в графе K5 есть только 12 разных гамильтоновых циклов.
Слайд 43 Поиск гамильтонова цикла (если он существует) в произвольном
(связном) графе — задача далеко не всегда простая.
Ответ
на вопрос о гамильтоновости графа может оказаться довольно трудоемким.Слайд 45 Решение. Предположим, что в связном графе найдется гамильтонов
цикл.
Каждая вершина v включается в гамильтонов цикл С
выбором двух инцидентных с ней ребер, а значит, степень каждой вершины в гамильтоновом цикле (после удаления лишних ребер) равна 2. Слайд 46 Все степени вершин данного графа — только 2
или 3.
Вершины степени 2 должны входить в возможный
цикл вместе с обоими инцидентными с ними ребрами. Следовательно, ребра ab, ae, cd, cb, hi, hg и ij в том или ином порядке могут входить в возможный гамильтонов цикл С, если, конечно, он существует (см. рис. 7.10).
Слайд 48 Ребро bf не может быть частью цикла С,
поскольку каждая вершина такого цикла должна иметь степень 2
(а у вершины b тогда будет степень 3).Значит, ребра fj и fg обязаны входить в цикл С, чтобы включить в этот цикл вершину f.
Но тогда ребра je и gd никак не могут принадлежать циклу С, поскольку в противном случае в нем появятся вершины (d и e) степени 3.
Слайд 49 Это вынуждает нас включить в цикл ребро ed,
что приводит к противоречию:
ребра, которые мы
были вынуждены выбрать, образуют два несвязных цикла, а не один, существование которого мы предполагали. Вывод: граф, изображенный на рис. 7.10, не является гамильтоновым.
Слайд 50
Гамильтоновы графы применяются для моделирования многих практических задач.
Основой всех таких задач служит классическая задача коммивояжера, формулировка
которой приведена ниже.
Слайд 51
Коммивояжер должен совершить поездку по городам и вернуться
обратно, побывав в каждом городе ровно один раз, сведя
при этом затраты на передвижения к минимуму.
Слайд 52
Графическая модель задачи коммивояжера состоит из гамильтонова графа,
вершины которого изображают города, а ребра — связывающие их
дороги.Слайд 53 Кроме того, каждое ребро оснащено весом, обозначающим транспортные
затраты, необходимые для путешествия по соответствующей дороге, такие, как,
например, расстояние между городами, стоимость проезда или время движения по дороге.Граф, каждое ребро которого снабжено весом, называется нагруженным.
Слайд 54 Для решения задачи нам необходимо найти гамильтонов цикл
минимального общего веса.
К сожалению, эффективный алгоритм решения данной задачи
пока не известен. Для сложных сетей число гамильтоновых циклов, которые необходимо просмотреть для выделения минимального, непомерно огромно.
Слайд 55
Однако существуют алгоритмы поиска субоптимального решения.
Субоптимальное решение необязательно
даст цикл минимального общего веса, но найденный цикл будет,
как правило, значительно меньшего веса, чем большинство произвольных гамильтоновых циклов.Один из таких алгоритмов мы сейчас изучим.
Слайд 56
Алгоритм ближайшего соседа
Этот алгоритм выдает субоптимальное решение задачи
коммивояжера, генерируя гамильтоновы циклы в нагруженном графе с множеством
вершин V.Цикл, полученный в результате работы алгоритма, будет совпадать с конечным значением переменной маршрут, а его общая длина — конечное значение переменной w.
Слайд 57
begin
выбрать v V;
маршрут := v;
w
:= 0;
v' :=v;
отметить v';
while остаются неотмеченные вершины do
begin
выбрать неотмеченную вершину и,
ближайшую к v';
Слайд 58
маршрут := маршрут u;
w : = w +
вес ребра v'u;
v' := u;
отметить v';
end
маршрут := маршрут v;
w := w + вес ребра v'v;
end
Слайд 59 Пример 7.6. Примените алгоритм ближайшего соседа к графу,
изображенному на рис. 7.11. За исходную вершину возьмите вершину
D.Слайд 61 В результате работы алгоритма был найден гамильтонов цикл
D C A B D общего веса 24.
Делая
полный перебор всех циклов в этом маленьком графе, можно обнаружить еще два других гамильтоновых цикла: A B C D A общего веса 23 и A C B D A общего веса 31.
Слайд 62
В полном графе с двадцатью вершинами существует приблизительно
6,1 ∙ 1016 гамильтоновых циклов, перечисление которых требует чрезвычайно
много машинной памяти и времени.
Слайд 63
Деревья
Как упоминалось ранее в этом разделе, есть
класс графов, называемых деревьями, которые особенно интенсивно используются в
вычислительных приложениях.Граф G = (V, Е) называется деревом, если он связен и ацикличен (т.е. не содержит циклов).
Слайд 64 Пусть G = (V, Е) — граф с
n вершинами и т ребрами. Можно сформулировать несколько необходимых
и достаточных условий, при которых граф G является деревом:любая пара вершин в графе G соединена единственным путем;
граф G связен и т = n – 1;
граф G связен, а удаление хотя бы одного его ребра нарушает связность графа;
граф G ацикличен, но если добавить хотя бы одно ребро, то в G появится цикл.
Слайд 65
Эквивалентность большинства из этих условий устанавливается без особого
труда.
Наиболее сложно разобраться со вторым из них.
В
следующем примере мы докажем, что дерево с n вершинами имеет ровно n - 1 ребро.Слайд 66 Пример 7.7. Докажите с помощью индукции по числу
вершин, что для дерева T c n вершинами и
т ребрами выполнено соотношение: т = n - 1.Слайд 67 Решение. Поскольку дерево с единственной вершиной вообще не
содержит ребер, то доказываемое утверждение справедливо при n =
1.Рассмотрим дерево T с n вершинами (и т ребрами), где n > 1 и предположим, что любое дерево с k < n вершинами имеет ровно k - 1 ребро.
Слайд 68 Удалим ребро из T. По третьему свойству дерево
T после этой процедуры превратится в несвязный граф.
Получится ровно
две компоненты связности, ни одна из которых не имеет циклов (в противном случае исходный граф T тоже содержал бы циклы и не мог бы быть деревом). Таким образом, полученные компоненты связности — тоже деревья.
Слайд 69 Обозначим новые деревья через T1 и Т2. Пусть
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 строится просто: выбираем
произвольное его ребро и последовательно добавляем другие ребра, не
создавая при этом циклов, до тех пор, пока нельзя будет добавить никакого ребра, не получив при этом цикла.Благодаря примеру 7.7, мы знаем, что для построения остовного дерева в графе из n вершин необходимо выбрать ровно n - 1 ребро.
Слайд 73 Решение. В этом графе существует несколько остовных деревьев.
Одно из них получается последовательным выбором ребер: а, b,
d и f. Другое — b, с, е и d. Названные деревья показаны на рис. 7.13.Слайд 74 Процесс, описанный в примере 7.8, можно приспособить для
решения задачи поиска кратчайшего соединения:
Нужно построить железнодорожную сеть, связывающую
некоторое число городов. Известна стоимость строительства отрезка путей между любой парой городов. Требуется найти сеть минимальной стоимости.Слайд 75 На языке теории графов нам нужно в нагруженном
графе найти остовное дерево наименьшего общего веса. Такое дерево
принято называть минимальным остовным деревом или, сокращенно, МОД.Слайд 76 В отличие от задачи коммивояжера, здесь есть эффективный
алгоритм, находящий действительно минимальное остовное дерево. Он похож на
алгоритм Прима, с которым мы познакомились в главе 1 при решении задачи поиска кратчайшего соединения для набора из шести шотландских городов.
Слайд 78
Алгоритм поиска минимального остовного дерева
Пусть
G = (V, Е)
— связный взвешенный граф. Алгоритм строит МОД в графе
G, последовательно выбирая ребра наименьшего возможного веса до образования остовного дерева. МОД в памяти компьютера хранится в виде множества T ребер.
Слайд 80 е': = ребро из Е' наименьшего веса; T:=T
{e'};
Е':= множество ребер из Е' \ {Т}, чье
добавление к Т не ведет к образованию циклов; end
end
Слайд 81 Пример 7.9. В таблице 7.3 дано расстояние (в
милях) между пятью деревнями А, В, С, D и
Е. Найдите минимальное остовное дерево.Таблица 7.3
Слайд 82 Решение. Ребра выбираются следующим образом: первое — ребро
DE веса 2; второе — АС веса 3; третье
— СЕ веса 7. На этой стадии строящееся дерево выглядит так, как на рис. 7.14Слайд 83 Следующие по весу ребра — AD, АЕ и
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. Мы изображаем такое дерево с корнем,
расположенным наверху, и сыновьями, стоящими ниже, непосредственно под корнем (см. рис. 7.17). Каждую вершину дерева с корнем можно рассматривать как корень другого дерева, которое «растет» из него. Мы будем называть его поддеревом дерева Т.Слайд 91 Как мы уже говорили, вершина на самом верху
дерева — его корень, а вот те, которые находятся
в самом низу дерева (и не имеют сыновей) принято называть листьями. Остальные вершины, отличные от корня и листьев, называют внутренними.Слайд 92 Область применения деревьев с корнем обширна. Это, например,
и информатика, и биология, и менеджмент. Для приложения к
информатике наиболее важны так называемые двоичные или бинарные деревья с корнем. Двоичное дерево отличает от остальных то, что каждая его вершина имеет не более двух сыновей. В двоичном дереве с корнем вниз от каждой вершины идет не более двух ребер.Слайд 94 Таким образом, можно сказать, что каждой вершине двоичного
дерева с корнем соответствует не более, чем два поддерева,
которые принято называть левым и правым поддеревьями этой вершины.Слайд 95 Если оказалось, что у какой-то вершины дерева отсутствует
потомок слева, то ее левое поддерево называют нулевым, деревом
(т.е. нулевое дерево — это дерево без единой вершины). Аналогично, если у вершины отсутствует правый потомок, то ее правое поддерево будет нулевым.
Слайд 97
Определите
(а) корень T;
(б) корень левого поддерева вершины В;
(в) листья Т;
(г) сыновей вершины
С.
Нарисуйте двоичное дерево с корнем Т', полученное из Т
перестановкой левых и правых поддеревьев у каждой вершины.Слайд 98 Решение.(а) А; (б) D; (в) G, Н, Е,
I и J; (г) F.
Двоичное дерево с корнем Т'
начерчено на рис. 7.19.
Слайд 99
Краткое содержание главы
Граф G = (V, Е) состоит
из множества V, чьи элементы называют вершинами графа, и
множества Е его ребер, соединяющих некоторые пары вершин.Вершины u и v графа называют смежными, если они соединены каким-то ребром е, про которое говорят, что оно инцидентно вершинам u и v.
Степенью вершины v считают число δ(v) ребер графа, инцидентных V.
Слайд 100 Граф, в котором существует маршрут (называемый эйлеровым), начинающийся
и заканчивающийся в одной и той же вершине и
проходящий по каждому ребру графа ровно один раз, называется Эйлеровым графом. Связный граф с двумя или более вершинами является эйлеровым тогда и только тогда, когда каждая его вершина имеет четную степень.Слайд 101 Лемма об эстафете утверждает, что сумма степеней вершин
произвольного графа G = (V, Е) равна удвоенному числу
его ребер.Простым принято называть граф G = (V, Е) с конечным множеством вершин V и конечным множеством ребер Е, в котором нет петель и кратных ребер.
Слайд 102
Логическая матрица отношения на множестве вершин простого графа
G, которое задается его ребрами, называется матрицей смежности.
Подграфом графа
G = (V, Е) называют граф G' = (V', Е'), в котором Е' Е и V' V.
Слайд 103 Маршрутом длины k в графе называют такую последовательность
различных вершин v0, v1, ..., vk, в которой каждая
пара соседних вершин vi -1 vi соединена ребром.Циклом в графе является замкнутый маршрут v0, v1, ..., v0, у которого все вершины, кроме первой и последней, различны.
Слайд 104
Граф, не содержащий циклов, называют ацикличным.
Связным является тот
граф, в котором каждая пара вершин соединена маршрутом.
Количество компонент
связности графа можно подсчитать с помощью алгоритма связности.Слайд 105 Гамильтоновым называют такой цикл в графе, который проходит
через каждую вершину графа, причем только один раз. Граф,
в котором существует гамильтонов цикл, называют гамильтоновым.Слайд 106 Задача коммивояжера состоит в поиске гамильтонова цикла минимального
общего веса в нагруженном графе. Алгоритм ближайшего соседа позволяет
найти субоптимальное решение задачи коммивояжера.Слайд 107 Связный ацикличный граф G = (V, Е) является
деревом. Следующие утверждения о связном графе G = (V,
Е) с n вершинами и т ребрами эквивалентны:(а) G — дерево;
(б) любую пару вершин G связывает единственный путь;
(в) G связен и т = n - 1;
(г) G связен, а удаление любого его ребра нарушает это свойство;
(д) G ацикличен, но соединяя любую пару вершин новым ребром, мы получаем цикл.
Слайд 108 Остовным деревом графа G называют такой его подграф,
который является деревом и содержит все вершины графа G.
Алгоритм поиска минимального остовного дерева позволяет найти остовное дерево минимального общего веса в нагруженном графе и может быть использован для решения задачи поиска кратчайшего соединения.Слайд 109 Дерево с одной выделенной вершиной называют деревом с
корнем, а выделенную вершину — его корнем. Вершины, стоящие
непосредственно под вершиной v (и соединенные с ней ребрами), называются сыновьями вершины v.Слайд 110 Вершины, расположенные в самом низу дерева (они не
имеют сыновей), называются листьями. Вершины, отличные от корня и
листьев, называют внутренними вершинами графа. Нулевое дерево — это дерево, не имеющее ни одной вершины.Слайд 111 Каждая вершина дерева с корнем Т является корнем
какого-то другого дерева, называемого поддеревом Т. В двоичном дереве
с корнем каждая вершина имеет не более двух сыновей, а два поддерева вершины v называют левым и правым поддеревьями, ассоциированными с v. Двоичное дерево с корнем называют полным, если каждая его вершина, за исключением листьев, имеет ровно по два сына.Слайд 112 Глубиной вершины v дерева с корнем Т принято
считать длину единственного маршрута, соединяющего ее с корнем. Глубиной
графа Т называют максимальную глубину его вершин.
Слайд 113
Сортировка и поиск
Двоичные деревья с корнем очень полезны
при решении задач о выборе, в частности, о выборе
такого сорта, при котором нужно классифицировать упорядоченные данные или вести в них поиск.Слайд 114 Упорядоченные данные, такие как множество чисел, упорядоченных по
величине или множество строк литер, упорядоченных лексикографически (в алфавитном
порядке), можно организовать в виде вершин двоичного дерева с корнем в соответствии с их порядком.Слайд 115 При этом мы стремимся к тому, чтобы данные,
стоящие в левом поддереве данной вершины v были бы
меньше данных, соответствующих этой вершине, а данные, расположенные в правом ее поддереве — больше. Дерево данных, удовлетворяющее указанному условию, называют двоичным деревом поиска.Слайд 116 Например, в дереве двоичного поиска, приведенном на рис.
7.26, слова фразы «У МОЕГО КОМПЬЮТЕРА ЕСТЬ ЧИП НА
МАТЕРИНСКОЙ ПЛАТЕ» организованы именно таким образом.Слайд 117 Заметим, что каждое слово в левом поддереве любой
вершины предшествует (относительно алфавитного порядка) слову, стоящему в этой
вершине, а каждое слово ее правого поддерева следует за словом выбранной вершины.Слайд 119 Преимущество организации упорядоченных данных в виде двоичного дерева
поиска заключается в возможности создания эффективного алгоритма поиска каких-то
конкретных данных, включения новых данных в дерево и печати всей информации, содержащейся в дереве в виде упорядоченного списка.Слайд 120 Предположим, что в университете хранится список студентов (упорядоченный
в алфавитном порядке), в котором кроме фамилий и имен
имеются дополнительные важные сведения о студентах.Слайд 121 Допустим также, что возникла необходимость найти какую-то информацию
в списке или добавить новые записи к списку. Мы
сейчас познакомимся с алгоритмами, которые осуществляют поиск конкретной информации, добавляют новых студентов к списку и выводят на печать все записи в алфавитном порядке.Слайд 122 Записи о студентах организованы в двоичное дерево поиска
(каждая запись соответствует одной вершине), и наши алгоритмы будут
исследовать вершины этого дерева. Поскольку каждая вершина является также и корнем некоторого двоичного дерева поиска, алгоритмы будут последовательно проверять левые и правые поддеревья вершин.Слайд 123 Чтобы это осуществить, необходимо приписать каждой вершине некоторый
ключ для идентификации и ссылок на ее левое и
правое поддеревья (в структурах данных для этих целей используются так называемые дважды связанные списки).Слайд 124 Из всех ключей организуется линейно упорядоченное множество (в
нашей ситуации оно упорядочено лексикографически).
Алгоритм поиска определяет, является ли
данная запись (ключ поиска) вершиной в двоичном дереве поиска, сравнивая ключ поиска с ключом корня дерева, и, при необходимости, осуществляет аналогичные сравнения в левом или правом поддеревьях.
Слайд 125
Поиск (дерево)
begin
if дерево нулевое then
поиск := ложь;
else
if ключ поиска = ключ корня then
поиск := истина;
else
Слайд 126
if ключ поиска < ключ корня then
поиск :=
поиск (левое поддерево);
else
поиск := поиск (правое поддерево);
end
Слайд 127 Задача 1. Проследите за работой алгоритма над двоичным
деревом поиска, изображенном на рис. 7.27. Известно, что ключ
поиска — буква Л, а ключи вершин упорядочены лексикографически.Слайд 128 Решение. Поскольку R > К, то поиск продолжается
в правом поддереве вершины К. Так как R
T, процесс поиска переключается на левое поддерево вершины Г. Наконец, ввиду неравенства R М и отсутствия поддеревьев у вершины М. алгоритм заканчивается и сообщает, что искомая вершина не была найдена.
Слайд 130 Алгоритм вставки вставляет новые вершины (ключи вставок) в
двоичное дерево поиска, создавая при этом новую вершину слева
или справа от уже существующей. Это делается таким образом, чтобы все ключи вершин в получившемся дереве подчинялись установившемуся порядку.
Слайд 131
Вставка (запись, дерево)
begin
if дерево нулевое then
добавить новую
вершину;
else
if ключ вставки = ключ корня then
вывести на
печать: «запись содержится в дереве»;
else
Слайд 132
if ключ вставки < ключ корня then
вставка
:= вставка (запись, левое поддерево);
else
вставка := вставка (запись, правое
поддерево);end
Слайд 133 Задача 2. Проследите за работой алгоритма вставки на
примере вершин R, А и L в дерево из
задачи 1.Слайд 134 Решение. Поскольку R > К, мы применяем алгоритм
вставки к правому поддереву вершины К. Далее мы видим,
что R < Т. Значит, алгоритм вставки переключается на левое поддерево вершины Т. Так как R > М и правое поддерево вершины М нулевое, то мы ставим вершину R справа от М и получаем дерево, изображенное на рис. 7.28. Теперь вставим А и L, построив дерево, показанное на рис. 7.29.Слайд 136 Алгоритм вставки можно использовать для создания двоичного дерева
поиска, начиная с нулевого дерева и последовательно добавляя новые
данные в удобном для нас порядке.Слайд 137 Например, двоичное дерево поиска на рис. 7.26 является
результатом применения алгоритма вставки к нулевому дереву в процессе
добавления слов фразы «У МОЕГО КОМПЬЮТЕРА ЕСТЬ ЧИП НА МАТЕРИНСКОЙ ПЛАТЕ» в том порядке, в котором они в ней записаны.Слайд 139 Алгоритм правильного обхода выводит на печать всю информацию,
содержащуюся в двоичном дереве поиска, в надлежащем порядке. При
этом все вершины дерева осматриваются в определенном порядке. Алгоритм работает следующим образом.Слайд 140 Для каждой вершины, начиная с корня, печатается вся
информация, содержащаяся в вершинах левого поддерева. Затем выводится информация,
хранящаяся в этой вершине, и наконец, информация, соответствующая вершинам правого поддерева.
Слайд 141
Правильный обход(дерево)
begin
if дерево нулевое then
ничего не делать;
else
begin
правильный обход (левое поддерево);
напечатать корневой ключ;
правильный обход (правое
поддерево); end
end
Слайд 142 Задача 3. Примените алгоритм правильного обхода к дереву,
полученному в задаче 2 после вставки R, А и
L.Решение. После работы алгоритма над указанным деревом получается список: А, С, К, L, М, R, Т, V.
Он соответствует обходу дерева против часовой стрелки (рис. 7.30) и печати информации, содержащейся в вершинах, как только Вы прошли под вершиной.
