3. Деревья. Остовные деревья. (1096032)
Текст из файла
Лекция 3. Деревья. Остовные деревья. Числоостовных деревьев помеченного полного графа.Достижимость промежуточного числа висячихвершин в остовном дереве. Оценка числависячих вершин в остовном дереве.Лектор — Селезнева Светлана Николаевнаselezn@cs.msu.suфакультет ВМК МГУ имени М.В. ЛомоносоваЛекции на сайте http://mk.cs.msu.ruДеревьяДостижимость числа висячих вершинЧисло висячих вершинДеревоДеревом называется связный граф без циклов.Остовным деревом связного графа называется его подграфсо всеми вершинами, являющийся деревом.ЗадачиДеревьяДостижимость числа висячих вершинЧисло висячих вершинЗадача о сетиПусть найдутся p узлов, между некоторыми из которых можнопроложить соединения.
Как связать все узлы в сеть, чтобыобщая протяженность соединений была наименьшей?ЗадачиДеревьяДостижимость числа висячих вершинЧисло висячих вершинЧисло остовных деревьевПолный граф Kn — граф с n вершинами, в котором любыедве различные вершины соединены ребром.Теорема 1 (Кэли). В помеченном полном графе Kn найдетсяровно nn−2 остовных деревьев.Доказательство.
Пусть V = {1, 2, . . . , n}.Для каждого остовного дерева D = D1 графа Kn построим егокод k(D1 ) = (j1 , . . . , jn−2 ).Пусть i1 — висячая вершина c наименьшей пометкой вдереве D1 . Она смежна с единственной вершиной j1 .Повторим рассуждения для дерева D2 = D1 − i1 и т.д.Останавливаемся, когда получим дерево Dn−1 , являющеесяребром.ЗадачиДеревьяДостижимость числа висячих вершинЧисло висячих вершинЗадачиЧисло остовных деревьевДоказательство (продолжение). Пусть получен кодk(D1 ) = (j1 , . . . , jn−2 ).Как по нему восстановить дерево D1 ?Заметим, что если i не содержится в коде k(D1 ), то i —висячая вершина дерева D.Пусть V1 = V . Выбираем наименьшее число i1 из V1 , несодержащееся в k(D1 ). Соединяем вершины i1 и j1 .
ПустьV2 = V1 \ {i1 }.Повторяем рассуждения для множества V2 и кода (j2 , . . . , jn−2 ).Заметим, что множество Vn−1 содержит ровно две вершины.Их нужно соединить ребром. Получим дерево D1 .ДеревьяДостижимость числа висячих вершинЧисло висячих вершинЗадачиЧисло остовных деревьевДоказательство (продолжение). Значит, число остовныхдеревьев в графе Kn совпадает с числом кодов (j1 , . . . , jn−2 ),где j1 , . . . , jn−2 ∈ {1, 2, .
. . , n}.Т.е. число остовных деревьев равно nn−2 .ДеревьяДостижимость числа висячих вершинЧисло висячих вершинЗадачиДостижимость промежуточного числа висячих вершинТеорема 2. Пусть D1 и D ∗ — два остовных дерева связногографа G с m и n висячими вершинами соответственно (m < n).Тогда для каждого числа k, m < k < n, в графе G найдетсяостовное дерево с k висячими вершинами.Доказательство. Пусть e1∗ ∈ E (D ∗ ) \ E (D1 ). Рассмотрим графG1 = D1 + e1∗ . В нем найдется единственный простой цикл C1 .В этом цикле выберем ребро e1 ∈/ D ∗ , и положим D2 = G1 − e1 .Граф D2 — дерево, повторим для него рассуждения и т.д.В итоге получим последовательность остовных деревьевD1 , D2 , .
. . , D ∗ .Заметим, что число висячих вершин в соседних деревьях Diи Di+1 отличается не более, чем на 2.ДеревьяДостижимость числа висячих вершинЧисло висячих вершинЗадачиДостижимость промежуточного числа висячих вершинДоказательство (продолжение). Пусть для некоторого k,m < k < n, в последовательности остовных деревьев нет деревас k висячими вершинами.Значит, найдутся два соседних дерева Di и Di+1 , такие, что вдереве Di — (k − 1) висячих вершин, а в дереве Di+1 — (k + 1)висячих вершин.Рассмотрим простой цикл Ci в графе Gi .
Концы ребра ei∗имеют степень больше двух, а концы ребра ei имеют степеньдва в цикле Ci . Значит, в цикле Ci найдется такое ребро e, чтоодин его конец имеет стень два, а другой его конец имеетстепень, большую двух.Тогда дерево D = Gi − e — остовное дерево с k висячимивершинами в графе G .ДеревьяДостижимость числа висячих вершинЧисло висячих вершинЗадачиЧисло висячих вершинСколько висячих вершин может быть в остовном деревеграфа G ?Предложение 1.
Для каждого связного графа G можнопостроить остовное дерево, в котором не менее ∆(G ) висячихвершин.Доказательство. Построим остовное дерево так: сначалавыберем вершину v ∈ V с dG (v ) = ∆(G ) вместе со всемиисходящими из нее ребрами.Затем добавим к этой звезде ребра графа G так, чтобы непоявились циклы.
В итоге получим остовное дерево, в которомне менее ∆(G ) висячих вершин.ДеревьяДостижимость числа висячих вершинЧисло висячих вершинЗадача о сети с концевыми узламиПусть найдутся p узлов, между некоторыми из которых можнопроложить соединения. Как связать все узлы в сеть, чтобычисло концевых узлов осталось наибольшим (например, кконцевым узлам подсоединяются пользователи)?ЗадачиДеревьяДостижимость числа висячих вершинЧисло висячих вершинОценка числа висячих вершинТеорема 3.
В связном графе G = (V , E ) c δ(G ) ≥ 3 найдетсяостовное дерево, в котором не менее |V |/4 висячих вершин.Доказательство. Опишем алгоритм построения такогоостовного дерева.Пусть дерево D — подграф графа G . Висячую вершинудерева D назовем устойчивой, если все смежные с нейвершины принадлежат также дереву D.Пусть v (D) — число вершин, u(D) — число висячих вершин иs(D) — число устойчивых висячих вершин дерева D.Положим α(D) = 3u(D)/4 + s(D)/4 − v (D)/4.ЗадачиДеревьяДостижимость числа висячих вершинЧисло висячих вершинОценка числа висячих вершинДоказательство (продолжение).Остовное дерево будем строить по индукции.Базис индукции: выберем в графе G произвольную вершину v .Пусть дерево D1 состоит из вершины v вместе со всемиисходящими из нее ребрами и их вторыми концами.Тогда, т.к.
α(D) = 3u(D)/4 + s(D)/4 − v (D)/4 и dG (v ) ≥ 3,верноα(D1 ) ≥ 3dG (v )/4 − (dG (v ) + 1)/4 ≥ 1/2.ЗадачиДеревьяДостижимость числа висячих вершинЧисло висячих вершинОценка числа висячих вершинДоказательство (продолжение). Пусть уже построенодерево Di , и W = V \ V (Di ).1. Если в дереве Di есть невисячая вершина v , смежная снекоторой вершиной w ∈ W , то пусть Di+1 = Di + (v , w ).Тогда, т.к. α(D) = 3u(D)/4 + s(D)/4 − v (D)/4, верноα(Di+1 ) − α(Di ) ≥ 3/4 − 1/4 = 1/2.ЗадачиДеревьяДостижимость числа висячих вершинЧисло висячих вершинОценка числа висячих вершин2. Иначе, если в дереве Di есть вершина v , смежная с хотя быс двумя вершинами w1 , w2 ∈ W , то пустьDi+1 = Di + (v , w1 ) + (v , w2 ).Тогда, т.к. α(D) = 3u(D)/4 + s(D)/4 − v (D)/4, верноα(Di+1 ) − α(Di ) ≥ 3/4 − 2 · (1/4) = 1/4.ЗадачиДеревьяДостижимость числа висячих вершинЧисло висячих вершинОценка числа висячих вершин3.
Иначе, если в множестве W есть вершина w , смежная скакой-то вершиной v дерева Di и хотя бы двумя вершинамиw1 , w2 ∈ W , то пусть Di+1 = Di + (v , w ) + (w , w1 ) + (w , w2 ).Тогда, т.к. α(D) = 3u(D)/4 + s(D)/4 − v (D)/4, верноα(Di+1 ) − α(Di ) ≥ 3/4 − 3 · (1/4) = 0.ЗадачиДеревьяДостижимость числа висячих вершинЧисло висячих вершинОценка числа висячих вершин4. Иначе, в множестве W есть вершина w , смежная свершинами дерева Di . Т.к. п. 3 не выполняется, то вершина wсмежна не более, чем с одной вершиной из множества W . НоdG (v ) ≥ 3, поэтому вершина w смежна хотя бы с двумявершинами v , v1 ∈ V (Di ). Пусть Di+1 = Di + (v , w ). Т.к.п.п. 1–2 не выполняются, вершина v1 — висячая в дереве Di исмежна рово с одной вершиной из множества W , а именно, свершиной w .
Поэтому в дереве Di+1 висячая вершина v1 —устойчивая.Тогда, т.к. α(D) = 3u(D)/4 + s(D)/4 − v (D)/4, верноα(Di+1 ) − α(Di ) ≥ 1/4 − 1/4 = 0.ЗадачиДеревьяДостижимость числа висячих вершинЧисло висячих вершинЗадачиОценка числа висячих вершин5. Если п.п. 1–4 неприменимы, то остовное дерево D построено.ДеревьяДостижимость числа висячих вершинЧисло висячих вершинЗадачиОценка числа висячих вершинДоказательство (продолжение). В остовном дереве D всевисячие вершины устойчивые.Поэтому, т.к. α(D) = 3u(D)/4 + s(D)/4 − v (D)/4, верноα(D) = u(D) − v (D)/4.Илиu(D) = v (G )/4 + α(D).Но α(D) ≥ α(D1 ) ≥ 1/2, т.к. на каждом шаге построения мытолько увеличивали этот параметр.Отсюда получаем, чтоu(D) ≥ |V |/4.ДеревьяДостижимость числа висячих вершинЧисло висячих вершинЗадачиЗадачи1.
Найти все неизоморфные остовные деревья в графе G , если:1)2)3)4)GGGG= K3 ;= K4 ;= K4 − e, где e — произвольное ребро графа K4 ;= K5 .Изобразить эти неизоморфные остовные деревья.2. По коду k(D) восстановить остовное дерево D полногопомеченного графа Kn , если:1)2)3)4)k(D) = (1, 2), n = 4;k(D) = (1, 1, 1), n = 5;k(D) = (3, 2, 1), n = 5;k(D) = (2, 3, 5, 5), n = 6.Изобразить дерево D.ДеревьяДостижимость числа висячих вершинЧисло висячих вершинЗадачи3.
По алгоритму из доказательства теоремы 2 найти остовныедеревья Dk , 1 ≤ k ≤ 5, с k висячими вершинами по остовнымдеревьям D1 и D5 графа K5 соответственно с одной и пятьювисячими вершинами, если k(D1 ) = (2, 3, 4), k(D5 ) = (2, 2, 2).Изобразить остовные деревья Dk , k = 2, 3, 4.4. Построить пример связного графа Gn с n вершинами,n = 4m, m ≥ 1, в котором степени всех вершин равны 3 илюбое остовное дерево содержит не более m + 2 висячихвершин.ЗадачиДеревьяДостижимость числа висячих вершинЧисло висячих вершинЛитература к лекции1. Емеличев В.А., Мельников О.И., Сарванов В.И., ТышкевичР.И.
Лекции по теории графов. М.: Либроком, 2009. С. 59.2. Харари Ф. Теория графов. М.: Мир, 1973. С. 183.3. Оре О. Теория графов. М.: Мир, 1980. С. 77–80.ЗадачиДеревьяДостижимость числа висячих вершинКонец лекцииЧисло висячих вершинЗадачи.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
