1. Булеви функции. Теорема на Пост-Яблонски за пълнота. Нека J2 = { 0, 1}. Всяка функция f : J2n  J



страница3/29
Дата11.01.2018
Размер5.91 Mb.
#44141
1   2   3   4   5   6   7   8   9   ...   29

дясно-инвариантна, ако от (, )  R  (, )  R

за всяка дума   X*.


Нека A = < Q, X, q0, , F > е краен детерминиран автомат. Определяме релацията RAX* x X* по следния начин:

RA = { (, ) | (q0, ) = (q0, ) }.


Лема: RA е релация на еквивалентност и е дясно-инвариантна.

Доказателство: Тривиална проверка.


Нека X е произволна азбука и L  X* е произволен език.

Дефинираме релацията RL  X* x X* по следния начин:

RL = { (, ) | за всяка дума   X*,  и 

едновременно са в L или не са в L }.


Теорема: Релацията RL е релация на еквивалентност и е

дясно-инвариантна.

Доказателство: Тривиална проверка.
Нека A = < Q, X, q0, , F > е краен детерминиран автомат.

Състоянието q  Q наричаме достижимо, ако съществува дума

  X*, такава че (q0, ) = q. Ако за всяка дума   X* имаме

 (q0, )  q, казваме че състоянието q е недостижимо.

Ясно е, че отстраняването на недостижимите състояния не променя езика, разпознаван от автомата.

Така можем да считаме, че автоматът A има само достижими състояния. Всеки клас на еквивалентност на RA съдържа думите

от X*, които довеждат автомата до дадено негово състояние. Ще отбележим, че тъй като автоматът е навсякъде дефиниран всяка дума от X* довежда автомата до някое състояние. Tака, ако автоматът A е навсякъде дефиниран и има само достижими състояния, индексът на релацията RA е краен - точно|Q|.
Теорема: Нека L  X*. Релацията RLX* x X* има краен индекс  L е автоматен език.

Доказателство: Нека L е автоматен език. Тогава съществува краен детерминиран автомат A = < Q, X, q0, , F >, такъв че LA = L.

Лесно се вижда, че ако (, )  RA, то (, )  RL. При това положение, всеки клас на еквивалентност на RL се състои от класове на RA и тъй като RA има краен индекс, то RL също има краен индекс.

Нека индексът на RL е краен. Нека [] е класът на еквивалентност на релацията RL с представител   X*. Да означим с Q множеството от класовете на еквивалентност на RL (то е крайно).

Построяваме краен детерминиран автомат

A = < Q, X, [], , F >. Лесно се вижда, че всеки клас на еквивалентност на релацията RL съдържа думи само от L или думи не от L (от дефиницията на RL при  = ).

Така можем да дефинираме F = { [] |   L }.

Дефинираме ([], x) = [x] за всяко x  X. Тази дефиниция е коректна, т.е. не зависи от представителя на класа на еквивалентност, тъй като релацията RL е дясно-инвариантна.

Лесно се вижда, че LA = L. Така L е автоматен език.


Следствие: Автоматът A = < Q, X, [], , F > от теоремата е минимален за езика L.

Доказателство: В процеса на доказателството на теоремата показахме, че индексът на RL е по-малък от индекса на RA за всеки детерминиран автомат A, който разпознава L. От друга страна, построеният автомат има точно толкова състояния, колкото е индексът на RL, така че той е минимален.


Нека A = < Q, X, q0, , F > е краен детерминиран автомат и LA = L. Считаме, че автоматът е навсякъде дефиниран и има само достижими състояния.

Състоянията qi, qjQ наричаме еквивалентни, ако съответните им класове на еквивалентност на релацията RA попадат в един и същ клас на еквивалентност на релацията RL.

От тази дефиниция и от теоремата лесно се вижда, че минимизацията на автомата A се свежда до намиране на всички подмножества на Q от еквивалентни състояния.
Лема: Ако q1, q2Q, q1F и q2F, то q1 и q2 не са еквивалентни.
Лема (тест на едната буква): Нека q1, q2Q. Aко съществува

x  X, така че (q1, x) не е еквивалентно на (q2, x), то q1 и q2 не са еквивалентни.


Лема: Нека Q = { Q1, Q2, …, Qs} е разбиване на Q, такова че

Q jF или Q jQ\F, j = 1, 2, …, s. Нека за всякo Q j, за всяка

буква x  X и за всеки q1, q2Q j имаме: (q1, x)  Qk,

 (q2, x)  Qk за някое k  { 1, 2, …, s}. Тогава всяко Q j се състои само от еквивалентни състояния.
Трите леми водят до следния алгоритъм:


  1. Образуваме разбиването S0 = { , }, където = F

и = Q\F, i = 0.

  1. Нека сме построили разбиването Si = { , , …, }.

Всяко разбиваме на { , , …, }, такива че елементите на всяко от тях не се държат като нееквивалентни с теста на едната буква и обединяваме получените разбивания в Si+1.

  1. Ако Si+1 = Si – край, иначе i++, премини към 2.

Нека Sr = Sr+1 = … е последното разбиване.

Ясно е, че от последната лема подмножествата в Sr се състоят само от еквивалентни състояния. Освен това лесно се вижда, че не е възможно еквивалентни състояния да са в различни подмножества на разбиването Sr.

Сега вече лесно можем да построим минималният автомат

A0 = < Q0, X, t0, 0, F0 >, Q0 = Sr. Избираме t0 = , така че q0, тъй като началното състояние на автомата е класът на еквивалентност на RL, който съдържа , а  е в класът на еквивалентност на RA, съответен на q0. Mножеството от заключителните състояния F0 определяме по следния начин:

F0 = { |F }, тъй като заключителните състояния са тези класове на еквивалентност на RL, които съдържат само думи от L и тогава тези класове са образувани точно от класовете на RA, съответни на заключителни състояния.

Функцията на преходите 0 дефинираме по следния начин:

0 (, x) = , ако за всяко q  имаме (q, x)  . Дефиницията е коректна, тъй като във всички елементи на Sr, състоянията реагират еднакво на теста на едната буква.
Нека X е азбука. Въвеждаме операции в множеството от всички езици над азбуката X:


  1. Нека L1  X*, L2  X*. Дефинираме сума на езиците L1 и L2:

L1 + L2 = L1  L2.

  1. Нека L1  X*, L2  X*. Дефинираме произведение на езиците

L1 и L2: L1.L2 = {  |   L1,   L2 }.

Дефинираме L0 = { }, L1 = L, L2 = LL, …, Ln+1 = LnL.



  1. Нека L  X*. Дефинираме итерация на езика L: .

Нека X = { x1, x2, …, xn} е крайна азбука.

Разширяваме X до = X  { , , *, +, ., (, ) }.

Без ограничение на общността можем да считаме, че добавените символи не се срещат в X. Дефинираме индуктивно понятията

регулярен израз и език, съпоставен на този регулярен израз:

(регулярният израз е дума над , съпоставените езици са над X)

База: Думите , , xi, i = 1, 2, …, n над са регулярни изрази и съответните им регулярни езици над X са

{  }, , { xi }, i = 1, 2, … , n.

Предположение: Нека ,   * са регулярни изрази и съответните им регулярни езици над X са L и L.

Стъпка: Tогава ()+(), ().(), ()*  * са регулярни изрази и съответните им регулярни езици над X са L + L, L.L, L*.


Въвеждаме приоритет на операциите в следния ред:

итерация, произведение и сума. По този начин можем съществено да ограничим употребата на скоби в регулярните изрази.


Теорема: Ако L1 и L2 са автоматни езици, то L1 + L2 е автоматен език.

Доказателство:

Нека езикът L1 се поражда от граматиката Г1 = < N1, T1, S1, P1 >.

Нека езикът L2 се поражда от граматиката Г2 = < N2, T2, S2, P2 >.

Без ограничение на общността можем да смятаме, че

N1N2 = , N1T2 = , T1N2 = . Ако това не е изпълнено можем да преименуваме съответните нетерминали, което няма да измени езиците L1 и L2. Нека SN1N2T1T2.

Построяваме граматиката Г = < N1N2  { S} , T1T2, S, P >,



P = (P1P2)\{ S1 , S2  }  { S S1, S S2 }  { S , ако имаме S1  или S2  }. Получената граматика е автоматна и веднага се вижда, че = L1 + L2.

Теорема: Всеки краен език е автоматен.

Доказателство: {  } е автоматен език, тъй като се поражда от автоматната граматика Г = < { S }, { a }, S, { S } >.

Граматиката Г = < { S }, { a }, S, { S aS } > е автоматна и поражда езика . Нека L = {  },   ,  = a1a2…ak.

Тогава граматиката Г = < { S, A1, A2, …, Ak-1 }, { a1, a2, …, ak}, S,

{ S a1A1, A1 a2A2, …, Ak-2 ak-1Ak-1, Ak-1 ak } > е автоматна и очевидно LГ = L = {  }.

Нека L = { 1, …, m } е произволен краен език, m  1.

Тогава L = { 1 } + { 2 } + … + { m } и от предната теорема L е автоматен език, тъй като е крайна сума на автоматни езици.
Теорема: Ако L1 и L2 са автоматни езици, то L1.L2 е автоматен език.

Доказателство:

Нека езикът L1 се поражда от граматиката Г1 = < N1, T1, S1, P1 >.

Нека езикът L2 се поражда от граматиката Г2 = < N2, T2, S2, P2 >.

Отново без ограничение на общността можем да смятаме, че

N1N2 = , N1T2 = , T1N2 = .

Нека   L1,   L2.

Построяваме граматиката Г = < N1 N2, T1T2, S1, P >,

P = (P1P2)\{ A a| A a  P1 }  { A aS2|за всяко

A a  P1}. Очевидно Г е автоматна граматика и веднага се проверява, че LГ = L1.L2.

Нека   L1,   L2 (случаят   L1,   L2 се разглежда аналогично).

Тогава L1 = L1 + {  },   L1, и L1 също е автоматен език.

Сега L1.L2 = (L1 + {  }).L2 = L1.L2 + L2. От токущо доказаното L1.L2 е автоматен език, L2 е автоматен език и от теоремата по-горе L1.L2 е автоматен език.

Нека   L1,   L2. Тогава L1 = L1 + {  } и   L1, L2 = L2 + {  } и

  L2, L1 и L2 също са автоматни езици.

Имаме L1.L2 = (L1 + {  }).(L2 + {  }) = L1.L2 + L1 + L2 + {  }.

От доказаното по-горе L1.L2 е автоматен език, също L1 и L2 са автоматни езици и {  } е автоматен език, защото е краен 

L1.L2 е автоматен език.


Теорема: Ако L е автоматен език, то L* е автоматен език.

Доказателство:

Нека езикът L се поражда от граматиката Г = < N, T, S, P >.

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

Построяваме граматика Г = < N, T, S, P >, където

P = P\{ S }  { A aS | за всяко късо правило A a  P }.

Очевидно Г е автоматна граматика, вижда се, че = L*\{  }.

И така L*\{ } е автоматен език  L* = L*\{ }  { } е автоматен език.
Теорема (Клини): Множествата на регулярните езици и автоматните езици съвпадат.

Доказателство: С индукция по построението ще покажем,

че всеки регулярен език е автоматен.

База: Езиците {  }, , { xi} са автоматни езици, защото са крайни.

Предположение: Нека L и L са регулярни езици, съответни на регулярните изрази  и  и да допуснем, че L и L са автоматни езици.

Стъпка: Тогава L + L, L.L, L* са автоматни езици

(теоремите по-горе).

Нека L е автоматен език. Ще докажем, че L e регулярен език.

Съществува краен детерминиран автомат

A = < Q, X, q0, , F >, такъв че LA = L. Да означим

Q = { q0, q1, …, qn }, F = {} и да си мислим, че автоматът

A е представен с крайния ориентиран мултиграф G.

Означаваме с множеството от маршрутите в G от qi до qj, които не използват като вътрешни върховете qk, qk+1, …, qn. Ясно е, че всеки маршрут от qi до qj определя дума   X*,

такава че (qi, ) = qj. Така можем да отъждествим всеки маршрут със съответната му дума от входната азбука и да считаме, че е език над X, т.е.X*.
Лема: За всеки qi, qjQ е в сила:,

k = 0, 1, ..., n.

Доказателство: Маршрутите от разбиваме на две подмножества – такива които не използват qk като вътрешен връх и такива които използват qk като вътрешен връх. Очевидно маршрутите от , които не използват qk като вътрешен връх са точно маршрутите от.

Да разбием произволен маршрут от , който използва qk като вътрешен връх на части по следния начин: qi -- qk -- qk …qk -- qj.

В междинните части не се среща qk, така че маршрутът започва с

маршрут от qi до qk, който не използва qk като вътрешен връх, т.е. маршрут от , продължава с произволен брой цикли от qk до qk, които минават точно веднъж през qk, т.е. маршрут от и завършва с маршут от qk до qj, който не използва qk като вътрешен връх, т.е. маршрут от . Така маршрутите от , които използват qk като вътрешен връх са точно и окончателно .


Лема: Езикът е регулярен език за всеки i, j  { 0, 1, …, n },

k  { 0, 1, …, n+1 }.

Доказателство: Провеждаме индукция по k.

База: k = 0. Ако i = j, то са всички маршрути от qi до qi, които не минават през никой друг връх. Ако в графа G няма примки в qi, тогава = {  } и е регулярен език. Ако в графа G има примки

в qi и на тях съответстват букви , то

= { ,  } и е регулярен език, тъй като съответства на регулярния израз .

Ако i  j, то са ребрата от qi до qj. Ако в графа G няма ребро от qi до qj, то =  и е регулярен език. Ако в графа G има ребра от qi до qj и на тях съответстват букви , то



= { } и е регулярен език, тъй като съответства на регулярния израз .

Предположение: Нека за някое k езикът е регулярен език и

нека е съответният регулярен израз.

Стъпка: Тогава езикът също е регулярен, тъй като съгласно горната лема този език съответства на регулярния израз .


Продължение на доказателството на теоремата на Клини:

Имаме, че са всички маршрути от qi до qj (без ограничение) и от горната лема е регулярен език. От дефиницията за езика LA имаме, че LA = , тъй като думите, които се разпознават от автомата го довеждат от началното състояние

q0 до някое от крайните. И така LA е крайна сума на регулярни езици  L = LA е регулярен език. Така всеки автоматен език е регулярен.
3. Графи. Дървета. Обхождане на графи. Минимално покриващо дърво.
Нека V е крайно множество, V = { v1, v2, …, vn }, елементите на V наричаме върхове. Нека E е крайно множество,

E = { e1, e2, …, em }, елементите на E наричаме ребра.



Краен ориентиран мултиграф се нарича тройката G (V, E, fG) с функция fG : E  V x V (на всяко ребро се съпоставя наредена двойка върхове). fG наричаме свързваща функция.
За по нагледно представяне на графите ще използваме

диаграми – върховете означаваме като точки и всяко ребро означаваме със стрелка от един връх към друг.


Ребрата e  E, такива че fG (e) = (v, v), v  V наричаме примки.
Нека G (V, E, fG) е краен ориентиран мултиграф и fG е инекция. Тогава G се нарича краен ориентиран граф. Ясно е, че в такъв случай множеството E може да бъде определено като подмножество на V x V. И така при задаване на краен ориентиран граф G свързваща функция не е необходима – графът се означава с G (V, E) и се задава с множество от върхове V и множество от ребра E  V x V.
Нека G (V, E) е краен ориентиран мултиграф и релацията E  V x V е рефлексивна и симетрична. В такъв случай G се нарича краен неориентиран граф или просто граф. При изобразяване на крайни неориентирани графи не рисуваме примките и стрелките между два върха заменяме с една отсечка.
Ако в краен неориентиран граф допуснем многократни ребра, то отново ще е необходима свързваща функция и в този случай графът наричаме краен неориентиран мултиграф.
Нека G (V, E) е граф. Върховете vi, vj наричаме съседи,

ако (vi, vj)  E. Ако графът G е ориентиран, казваме че vi е баща на vj или, че vj е син на vi. Още казваме, че vi и vj са краища на реброто (vi, vj).


Нека G (V, E) е краен неориентиран граф и v  V. Дефинираме степен на върха v - d (v) = броят на ребрата, на които v е край.

Нека G (V, E) е краен ориентиран граф и v  V. Дефинираме полустепен на изхода на върха v – d (v) = броят на ребрата, излизащи от v и полустепен на входа на върха v – d+ (v) = броят на ребрата, завършващи във v.


Нека G (V, E, fG) е краен ориентиран мултиграф. Редицата

, L  0, такава че за всяко j  { 0, 1, …, L-1 } съществува

e  E, такова че fG (e) = (, ), наричаме маршрут до в графа G с дължина L. При = , маршрутът наричаме контур.


Нека G (V, E) е краен неориентиран граф.

Редицата , L  0, такава че за всяко j  { 0, 1, …, L-1 }, (, )  Е и за всяко j  { 1, …, L-1}, , наричаме път до в графа G с дължина L. При = и L  3, маршрутът наричаме цикъл. Ясно е, че по тази дефиниция считаме, че има тривиален път с дължина 0 от всеки връх vi до vi. Ще отбележим, че с дефинирането на тривиален път отчитаме примките в неориентирания граф, но им даваме тежест нула при образуване на дължината на пътищата.


Графът G (V, E) се нарича свързан, ако за всеки vi, vj  V съществува път от vi до vj. Дефиницията е приложима и за ориентирания случай, както и за случая с мултиграф, със замяната на понятието път с понятието маршрут, но тъй като изискването е прекалено силно, ще въведем алтернативно понятие. Ориентираният граф G (V, E) наричаме слабо свързан, ако за всеки vi, vj  V съществува път от vi до vj или от vj до vi.
Казваме, че графът D (V, E) е дърво, ако D е свързан граф без цикли.
Ще направим индуктивна дефиниция на кореново дърво

(с корен r):



  1. База – графът D ({ r }, ) е кореново дърво с корен r и

единствен лист r.

  1. Предположение – нека D (V, E) е кореново дърво с корен r и листа l1, l2, …, lk.

  2. Стъпка – нека u  V, w  V. Тогава D (V, E) =

D (V  { w }, E  { (u, w)} ) е също дърво с корен r. Ако u = li за i  { 1, 2, …, k }, то неговите листа са l1, …, li-1, w, li+1, …, lk,

в противен случай, те са l1, …, lk, w.


Oперацията в индукционната стъпка наричаме присъединяване на връх.
Теорема: Всяко кореново дърво е дърво.

Доказателство: Индукция по построението.



  1. База – кореновото дърво D ({ r },  ) е свързан граф, тъй като съществува тривиален път от r до r и няма цикли, тъй като няма ребра, така че D ({ r},  ) е дърво.

  2. Предположение – нека кореновото дърво D (V, E) е дърво.

  3. Стъпка – нека u  V, w  V. Ще покажем, че кореновото дърво D (V, E) = D (V  { w }, E  { (u, w)} ) е дърво.

Нека vi, vj  D. Ако vi, vj  D, то по индукционното предположение има път от vi до vj. Ако vi = vj = w, то съществува тривиален път от vi до vj. Ако vj = w, vi  w, то от индукционното предположение съществува път от vi до u и като добавим реброто (u, w) получаваме път от vi до w – не е възможно w да съвпада с върха преди u, тъй като w  V.

И така D е свързан граф. Да допуснем, че в D има цикли. Тъй като по индукционното предположение в D няма цикли, то реброто (u, w) със сигурност участва в цикъл, което е противоречие, тъй като w е край единствено на реброто

(u, w) и следователно, съгласно дефиницията на път, w не може да участва в цикъл. Така D е свързан граф без цикли, т.е. D е дърво.
Ще отбележим, че всяко дърво можем да предефинираме като кореново, ако изберем произволен негов връх за корен.
Теорема: Нека D (V, E) е дърво с корен r. Тогава |V| = |E| + 1.

Доказателство: Индукция по построението.



  1. База – за кореновото дърво D ({ r },  ) имаме |V| = 1,

|E| = 0 и тогава |V| = |E| + 1.

  1. Предположение – нека за кореновото дърво D (V, E) имаме

|V| = |E| + 1.

  1. Стъпка – нека u  V, w  V. Тогава за кореновото дърво

D (V, E) = D (V  { w }, E  { (u, w)} ) имаме |V| = |V| + 1,

|E| = |E| + 1 = |V| + 2  |V| = |E| + 1.


Теорема: Нека D (V, E) е дърво и vi, vj  V. Тогава съществува единствен път между vi и vj.

Доказателство: Поне един път между vi и vj има, тъй като

D е свързан граф. Да допуснем, че съществуват два различни пътя

, = vi, = vj и , = vi, = vj.

Нека s е най-малкото число, такова че (такова s има, тъй като двата пътя са различни), s ≥ 1. Tогава е цикъл, което е противоречие.


Теорема: Нека D (V, E) е дърво и (vi, vj)  E. Тогава в графа

D (V, E), E = E  { (vi, vj) } има точно един цикъл.

Доказателство: Тъй като (vi, vj)  E, то съществува единствен път и то с дължина поне 2 от vi до vj в D. Тогава при добавяне на реброто

(vi, vj) наистина се образува цикъл vi, V1, vj, vi (V1 е непразна редица от върхове). Да допуснем, че при добавяне на реброто (vi, vj) се образува втори цикъл. Естествено, той съдържа реброто (vi, vj), тъй като D е дърво и няма цикли и има вида vi, V2, vj, vi (V1  V2).

Без ограничение можем да смятаме, че реброто (vi, vj) се използва само накрая и в двата цикъла. Тогава vi, V1, vj и vi, V2, vj са два различни пътя между vi и vj в D, което е противоречие с предишната теорема.
Нека G (V, E) е граф, а D (V, E), E  E е дърво. Тогава D се нарича покриващо дърво на графа G.
Теорема: Графът G (V, E) притежава покриващо дърво тогава и само тогава, когато G е свързан.

Доказателство: Ясно е, че ако G притежава покриващо дърво D,

то G е свързан, тъй като в D, а тогава и в G (E  E) има път от всеки връх до всеки друг.

Нека G е свързан граф. Ще опишем алгоритъм, който построява покриващо дърво на G:



  1. H = G.

  2. докато в H има цикли

H = H – ребро от цикъла.

Твърдим, че след изпълнение на алгоритъма H е покриващо дърво на G. Действително, алгоритъмът винаги завършва, тъй като в G има краен брой ребра, а съществуването на цикъл предполага наличието на поне три ребра. Ясно е, че H е граф с върхове V и ребра E  E. От самия алгоритъм се вижда, че H няма цикли.

Ще покажем, че на всяка стъпка H остава свързан граф.

Да допуснем, че на някоя стъпка премахването на реброто (vi, vj) води до несвързан граф. Нека vk, vl са върхове между които няма път. Тъй като на предната стъпка графът е бил свързан, то съществува път между vk и vl, който минава през реброто (vi, vj), но в такъв случай можем да използваме остатъка от цикъла (или подходяща негова част) и да получим път между vk и vl в новия граф, което е противоречие. И така H (V, E) е свързан граф без цикли, т.е. покриващо дърво на G.


Под обхождане на граф ще разбираме процедура, която по определени правила “посещава” всички върхове на графа.
Даден е краен неориентиран граф G (V, E). В резултат на обхождането в ширина V се разбива на нива на обхождане

L0, L1, …, Lk по следния начин:



  1. избираме начален връх на обхождането r  V. “Обхождаме” r. Нека L0 = { r }, i = 0.

  2. Образуваме нивото Li+1 = { v | v  V, v – необходен, съществува w  Li, така че (w, v)  E }. “Обхождаме” всички върхове в Li+1.

  3. Ако Li+1  , тогава i++, премини към 2. Иначе край.

Ще отбележим, че обхождането ще посети всички върхове точно тогава, когато графът е свързан.

Ще приложим тази алгоритмична схема, за да построим покриващо дърво на свързания граф G (V, E):



  1. Избираме начален връх на обхождането r  V.

Образуваме D = (VD, ED), VD = { r }, ED = .

Нека L0 = { r }, i = 0.



  1. Образуваме нивото Li+1 = { v | v  V, v  VD, съществува

w  Li, такъв че (w, v)  E }. ED = ED  { (w, v) | w  Li, v  Li+1}, като за всяко v  Li+1 се добавя точно едно (w, v), такова че

w  Li, VD = VD  Li+1.



  1. Ако Li+1  , тогава i++, премини към 2. Иначе край.

След края на изпълнението VD = V, тъй като G е свързан и

получаваме кореново дърво D (V, ED), ED  E, което е покриващо дърво на графа G.
Даден е краен неориентиран граф G (V, E). При схемата обхождане в дълбочина основни понятия са текущ връх t и баща на върха t – p (t).


  1. Избираме начален връх r  V. “Обхождаме” r.

Обявяваме t = r, p (t) е неопределен.

  1. Търсим необходен съсед v на текущия връх t.

Ако има такъв v, тогава p (v) = t, t = v, “обхождаме” v, премини към 2.

Ако няма такъв v и t  r, t = p (t), премини към 2.

Ако няма такъв v и t = r, край.
И в тази схема ще се обходят всички върхове точно тогава, когато графът е свързан. Ще приложим алгоритмичната схема за решаване на задачата за построяване на покриващо дърво на свързания граф G (V, E):


  1. Избираме начален връх r  V, образуваме D (VD, ED), VD = { r },

ED = , t = r, p (t) – неопределен.

  1. Търсим необходен съсед v на текущия връх t.

Ако има такъв v, тогава p (v) = t, t = v, VD = VD  { v},

ED = ED  { (t, v)}, премини към 2.

Ако няма такъв v и t  r, t = p (t), премини към 2.

Ако няма такъв v и t = r, край.


След края на изпълнението VD = V, тъй като G е свързан и

получаваме кореново дърво D (V, ED), ED  E, което е покриващо дърво на графа G.


И двата алгоритъма (в ширина и в дълбочина) строят коренови дървета и тогава те могат да бъдат използвани за превръщане на произволни дървета в коренови.
Нека G (V, E) е краен неориентиран свързан граф.

Казваме, че един път в G е Ойлеров път, ако той минава през всяко ребро точно по веднъж. Ако началото и края на Ойлеровия път съвпадат, казваме че той е Ойлеров цикъл.

Граф, в който има Ойлеров цикъл, наричаме Ойлеров граф.
Теорема (Ойлер): G (V, E) е Ойлеров граф  за всеки връх v  V,

d (v) е четно число.


Следствие: В крайния неориентиран свързан граф G (V, E) има Ойлеров път  в G има точно два върха с нечетна степен.
Ясно е, че теоремата и следствието са в сила и за крайни неориентирани мултиграфи.
Дефиницията за Ойлеров път и Ойлеров цикъл се пренася лесно за крайни ориентирани мултиграфи. В сила са следните
Теорема: Крайният свързан ориентиран мултиграф G (V, E, fG) е Ойлеров  за всеки връх v  V, d+ (v) = d- (v).
Следствие: В крайния свързан ориентиран мултиграф G (V, E, fG) има Ойлеров път  съществуват w, w  V, такива че

d+ (w) = d- (w)+1, d+ (w)+1 = d- (w) и

за всяко v  V\{ w, w}, d+ (v) = d- (v).
Даден е краен неориентиран свързан граф G (V, E).

Също така е дадена функция c : E  . Стойността c (e), e  E наричаме цена (тегло) на реброто e. Нека D (V, E) е покриващо дърво на графа G. Цена на дървото наричаме сумата

c (D) = . Покриващото дърво D (V, E) наричаме минимално покриващо дърво, ако за всяко покриващо дърво D (V, E) имаме c (D)  c (D).
Ясно е, че всеки граф притежава минимално покриващо дърво, тъй като графът притежава краен брой покриващи дървета, а всяко крайно множество от реални числа има най-малък елемент.
Теорема (МПД – свойство): Нека G (V, E) е свързан граф с ценова функция по ребрата c : E   и   U  V. Нека e = (vi, vj)  E е такова, че vi  U, vj  V\U и e има минимално тегло от всички такива ребра. Tогава съществува минимално покриващо дърво

D (V, E) на G, такова че e  Е.

Доказателство: Да допуснем противното, т.е. не съществува минимално покриващо дърво на G, което съдържа реброто e.

Нека D (V, E) е произволно минимално покриващо дърво на G. Образуваме графа G (V, E  { e }). Тогава от една теорема по-горе в G има единствен цикъл, в който участва реброто e. Този цикъл съдържа друго ребро e (u1, u2), e  e, за което u1  U, u2  V\U – ако допуснем противното, т.е. всички останали ребра в цикъла съдържат краища само от U или само от V\U, ще се окаже, че те не могат да образуват цикъл. Сега построяваме дървото

D (V, E  { e } \ { e } ). Имаме c (D) = c (D) + c (e) – c (e)  c (D), тъй като c (e)  c (e). Тъй като D е минимално покриващо дърво,

то c (D) = c (D) и тогава D също е минимално покриващо дърво, което съдържа e – противоречие.


Ще използваме полученото свойство за да опишем два алгоритъма, които строят минимално покриващо дърво.
Алгоритъмът на Прим строи кореново дърво със зададен корен r.

  1. Избираме произволен връх r  V, построяваме D (VD, ED),

VD = { r }, ED = .

  1. Ако VD = V – край.

Ако VD  V, търсим ребро e (vi, vj) с минимално тегло, такова че vi  VD, vj  V\VD. VD = VD  { vj}, ED = ED  { e }.

Премини към стъпка 2.


Алгоритъмът на Прим директно прилага МПД-свойството – на всяка стъпка избира най-доброто ребро и е сигурен, че в крайна сметка ще получи минимално покриващо дърво.
Алгоритъмът на Крускал построява дърво без корен.

  1. Сортираме ребрата на G в нарастващ ред на теглата им

e1, e2, …, em.

  1. От всеки връх v  V образуваме тривиално дърво Dv ({ v}, ).

  2. За всяко ребро ei = (u, v), i = 1, 2, ..., m по реда на сортирането правим следното: ако u и v са в различни дървета D (V, E), D (V, E), свързваме u и v с ребро и по този начин обединяваме двете дървета в едно.

Изборът на най-лекото възможно ребро на всяка стъпка се гарантира от предварителното сортиране на ребрата. Ако достигнем до ребро e = (u, v), такова че u и v са в едно и също дърво, то e не се включва в дървото, тъй като свързаността на u и v е постигната с по-леки ребра.






Сподели с приятели:
1   2   3   4   5   6   7   8   9   ...   29




©obuch.info 2024
отнасят до администрацията

    Начална страница