Лекции Русакова, страница 9

Келли успешно применилдля определения количества химических изомеров углеродов CnH2n+2.Структурные формулы таких молекул таких соединений (вершины —атомы, дуги — валентные связи) представляют собой деревья.HHHHHHccHcccHHHHcHHHHHcHcHHБутанHИзобутон76Важным для приложений классом ориентированных деревьев являютсякорневые, или растущие деревья, то есть такие, у которых существуетвершина называемая корнем, из которой существуют простые пути во всеостальные вершины (в силу общих свойств деревьев путь из корня в каждуювершину — единственный).Вершины корневого дерева отличные от корня и висячих называютпромежуточными. Такие структуры принято использовать для организациисистем хранения информации, в частности, такими являются компьютерныефайловые системы. Корневое дерево файловой системы обычно называютдеревомдиректорий,вкоторомкорень–корневаядиректория,промежуточные вершины – поддиректории, а висячие вершины – отдельныефайлы или пустые поддиректории.2.13.

Задача поиска маршрутов в графе.Алгоритм Тэрри поиска маршрута в связном графе, соединяющеговершины υ и ω υ ≠ ω .Правила.1) Идя по произвольному ребру всегда отмечать направление егопрохождения.2) Исходя из некоторой вершины υ′ всегда следовать по тому ребру,которое не было пройдено или было пройдено в противоположномнаправлении.3) Для всякой вершины υ′ ≠ υ отмечать ребро по которому в вершинуυ′ попали в первый раз4) Исходя из некоторой вершины υ′ ≠ υ идти по первому заходящему вυ′ ребру лишь тогда, когда нет других возможностей.77Пример.+υ2+υ3υ4+Найти маршрутсоед. υ1 и υ5+, значитпрошлиυ1⊕υ5⊕Замечание: из полученного пути можно выделить простую цепь.2.14. Поиск оптимального пути (маршрута)Утверждение 1Каждый минимальный путь (маршрут) является простой цепьюДоказательство.ПустьП = υ1 υ 2 ...υ kυ1 ≠ υ k минимальный путь в орграфе D, неявляющийся простой цепью.

Тогда ∃ i и j такие, что 1 ≤ i < j ≤ k и vi=vj.Рассмотрим путьυ1...υi υ j+1...υ k . Его длина меньше, чем Π, чтопротиворечит предположению.Утверждение 2Минимальный подпуть из минимального пути минимален.Пусть П = υ1 υ 2 ...υ kυ1 ≠ υ k - минимальный путь (маршрут) в орграфеD (в графе G). Тогда для ∀ i и j таких, что 1 ≤ i < j ≤ k путь (маршрут)П 0 = υi υi +1...υ j тоже является минимальным.Доказательство.Предположим, что П 0 не является оптимальным, тогда ∃ П1 = υi ...υ jт.ч.

он короче чем Π 0 . Тогда заменив Π 0 на Π1 в Π можно найти более78короткий, чем Π путь⇒ Π не является минимальным. Пришли кпротиворечию.Пусть D = (V, X) орграф υ ∈ V — некоторая вершина υ ∈ V, V1 ⊆ V .Обозначим D(υ) = {ω ∈ V | (υ, ω) ∈ X} — образ вершины υ ;D −1 (υ) = {ω ∈ V | (ω, υ) ∈ X} — прообраз вершины υ ;D(V1 ) = D(υ) — образ множества вершин V1 ;υ∈V1D −1 (V1 ) = D −1 (υ) прообраз множества вершин V1.υ∈V1Для неориентированного графа образ и прообраз совпадают.Пусть G = (V, X) граф υ ∈ V, V1 ⊆ V .Обозначим G (υ) = {ω ∈ V | {υ, ω}∈ X} — образ вершины υ ;G (V1 ) = G (υ)υ∈V1— образ множества вершин V1.Пусть D = (V, X) орграф с n≥2 вершинами и v,w (v≠w) – заданныевершины из VАлгоритм поиска минимального пути из υ в ω в орграфе D(алгоритм фронта волны).1) Помечаем вершину υ индексом 0, затем помечаем вершины ∈образу вершины υ индексом 1.

Обозначаем их FW1 (v). Полагаем k=1.792) ЕслиFWk (υ) = ∅ или k=n-1, и одновременно ω ∉ FWk (υ ) товершина ω не достижима из υ . Работа алгоритма заканчивается.В противном случае продолжаем:3) Если ω ∉ FWk (υ) , то переходим к шагу 4.В противном случае мы нашли минимальный путь из υ в ω и егодлина =k. Последовательность вершинυω1ω2ω3 ...ωk −1ωωk −1 ∈ FWk −1 (υ ) ∩ D −1 (ω )ωk − 2 ∈ FWk − 2 (υ ) ∩ D −1 (ωk −1 )........................................ω1 ∈ FW1 (υ ) ∩ D −1 (ω2 )есть этот минимальный путь. Работа завершается.4) Помечаем индексом k+1 все непомеченные вершины, которыепринадлежат образу множества вершин c индексом k. Множество вершин синдексом k+1 обозначаем FWk +1 (υ) .

Присваиваем k:=k+1 и переходим к 2).Замечание 1Множество FWk (υ) называется фронтом волны kго уровня.Замечание 2Вершины ω1ω2ω3 ...ωk −1 могут быть выделены неоднозначно, чтосоответствует случаю, если существует несколько минимальных путей из υв ω.802.15. Минимальные пути, маршруты в нагруженныхграфах.ОпределениеНазовем орграф D=(V,X) нагруженным, если на множестве дуг Xопределена некоторая функция l : X → R , которую называют весовойфункцией24678Числа – вес дуги, (цена дуги).Для любого пути П нагруженного орграфа D обозначим через l(П)сумму длин дуг, входящих в путь П.

(Каждая дуга считается столько раз,сколько она входит в путь П).Величина l называется длиной пути. Если выбрать веса равными 1, топридем к ненагруженному графу.ОпределениеПуть в нагруженном орграфе из вершины v в верш. w, где v≠w,называется минимальным, если он имеет наименьшую длину.81ОпределениеАналогично определяется минимальный маршрут в нагруженномграфе.ЗамечаниеЗадачи поиска минимального пути имеет смысл ставить тогда, когданет отрицательных замкнутых путей (иначе можно повторять циклмногократно, уменьшая «длину»).Свойства минимальных путей в нагруженном орграфе1. Если для ∀ дуги x ∈ X l( x ) > 0 , то ∀ min путь (маршрут) являетсяпростой цепью;2.

если υ1 , υ 2 ,..., υ k min путь (маршрут) то для ∀ i,j : 1 ≤ i < j ≤ k путь(маршрут) υi υi +1...υ j−1υ j тоже является minДоказывается аналогично св-вам ненагруженного графа.3. если v... uw min путь (маршрут) среди путей (марш.) из v в w,содержащих не более k+1 дуг (ребер), то v... u min путь (маршрут) из v в uсреди путей (марш.), содержащих не более k дуг (ребер).Поиск min пути.Пусть D=(V,X) – нагр. орграф, V={v1,… vn}, n>1. Введем величины λ(ik ) ,где i=1,…,n, k=1,2,…,n-1.Для каждого фиксированного i и k величина λi(k ) равна длине min путисреди путей из v1 в vi содержащих не более k дуг.

Если путей нет, то λ(ik ) = ∞ .Положим также λ1(0 ) = 0, λ i(0 ) = ∞, i = 2,...n .82Введем матрицу длин дуг C(D)=[cij] порядка n, причемl (vi , v j ),cij =  ∞(vi , v j )∈ X ,(vi , v j )∉ X .Утверждение.При i=2,…,n, k≥0 выполняется равенствоλi(k +1) = min {λ(jk ) + c ji } (Принцип динамического программирования.1≤ j ≤ nИспользовать его позволяют свойства 2,3 min путей).Алгоритм Форда-БеллманаДля нахождения min пути в нагруженном орграфе D из v1 в vi.(i≠1).( λi(k ) записываем в виде матрицы, i- строка, k-столбец).1) Составляем табл. λ(ik ) , i=1,…,n, k=0,…,n-1.

Если λ(in−1) = ∞ , то пути изv1 в vi нет. Конец алгоритма.2) Если λi(n −1) < ∞ то это число выражает длину любого min пути из v1 вvi. Найдем min k1≥1, при котором λ(ik1 ) = λ(in−1) . По определению λ(ik ) получим,что k1- min число дуг в пути среди всех min путей из v1 в vi.3) Затем определяем номера i2,…,i k1 +1λi(2k1 −1) + ci2 , i = λi(k1 ) ,λi(3k1 − 2 ) + ci3 ,i2 = λi(2k1 −1) ,.............λi(k0 )+1 + cik +1 ,ik = λi(1k ) ,1111Пример.

v1→v683такие, что(0)(1)(2)(3)(4)(5)v1v2v3v4v5v6λiλiλiλiλiλiv1∞∞55212000000v2∞∞∞∞∞2∞∞7555v3∞2∞∞∞∞∞53333v4∞2∞∞∞∞∞54444v5∞∞12∞∞∞22222v6∞∞∞∞∞∞∞1212977Путь v1→v67=5+2 (2-ая стр.)5=3+2 (3-я стр.)3=1+2 (5-я стр.)2=0+2 (1-я стр.)Путь v1→v5→v3→v2→v6842.16. Специальные пути в орграфах (маршруты вграфах).Существует редко применяемый сейчас метод задания графа в виделатинской матрицы. В этом способе направление дуг задается порядком буквв их названии.Определение.Свойство α называется латинским, если из того, что путь π=π1  π2, гдеπ1, π2 ∈Π (множество всех путей в орграфе) обладает свойством α, следует,что пути π1, π2 также обладают свойством α.Примеры латинских свойств.1) Не проходить через данную вершину (или через множество вершин).2) Не проходить через данную дугу (или через множество дуг).3) Быть простой цепью (или простым контуром).4) Быть цепью (или контуром).5) Не проходить через каждую вершину более k раз.Определение.Матричный способ перечисления путей в орграфе, обладающихзаданнымлатинскимсвойствомα,называютметодомлатинскойкомбинации.Введем бинарную операциюα .

Пусть π1=v1v2…vk∈Πα (мн-во путей,обладающих свойством α), π2=w1w2…wL∈Πα. Положимπ  π , если vk = w1 и путь π 1  π 2 обладаетсвойством αбπ 1 π 2 =  1 2α ∅,в противном случае.85ααПоложим ∅  π=π  ∅=∅.[ ]Введем латинскую матрицу L(αk ) = lij(k ) размерности n×n такую, чтоlij(k ) — множество путей длины k из vi в vj, обладающих свойством α,( lij(k ) = ∅ , если таких путей нет).Определение.Под результатом комбинацииαC = L(αk )  L(αm )будем пониматьквадратную матрицу C=[cij] порядка n с элементамиcij =nα lir(k )  lrj(m )r =1(аналогично произведению матриц: строка настолбец).Утверждение.ααααПри любом k≥1 выполняется L(αk ) = L(αk −1)  L(α1) = L(α1)  L(α1)  L(α1)Пример.Найти все простые цепи длины 3 в орграфе D:86αL(α1)∅L(α2 ) = L(α1)  L(α1)v1v2v1v3∅∅∅v1v2v3v1v2v4v1v3v4∅∅v2v3v2v4v2v4v1∅∅v2v3v4∅∅∅v3v4v3v4v1v3v4v2∅∅v4v1v4v2∅∅∅v4v1v2v4v1v3∅v4v2v3αL(α3) = L(α2 )  L(α1)∅v1v3v4v2∅v1v2v3v4v2v3v4v1∅v2v4v1v3∅∅v3v4v1v2∅∅∅∅v4v1v2v3∅Найти простые контура длины 4 в том же орграфе (свойство α′).Для этого используем матрицу L(α3) , полученную при решенииα′предыдущей задачи L(α4′) = L(α3)  L(α1)∅v1v2v1v3∅∅∅v2v3v2v4∅∅∅v3v4v4v1v4v2∅∅α′∅v1v3v4v2∅v1v2v3v4v2v3v4v1∅v2v4v1v3∅∅v3v4v1v2∅∅∅∅v4v1v2v3∅87=v1v2v3v4v1∅∅∅∅v2v3v4v1v2∅∅∅∅v3v4v1v2v3∅∅∅∅v4v1v2v3v42.17.