Едмондсов алгоритам

Из Википедије, слободне енциклопедије

Овај чланак је о алгоритму оптималног гранања. За алгоритам максималног поклапања погледајте Алгоритам максималног упаривања.

У теорији графова, грани математике, Едмондсов алгоритам или Чу-Лиу/Едмондсов алгоритам је алгоритам за проналажење максималног или минималног оптималног гранања. Овај алгоритам је сличан проблему минималног разапињућег стабла, који се тиче неусмерених графова. Ипак, када су чворови повезани усмереним гранама са тежинским коефицијентима, алгоритам минималног разапињућег стабла се не може користити.

Алгоритам оптималног гранања су предложили независно Јенг-јин Чу (Yoeng-jin Chu) и Ценг-хонг Лиу (Tseng-hong Liu) 1965. године, а затим и Едмондс 1967. године. За проналазак путање максималне дужине, узима се грана са највећим тежинским коефицијентом и повезују се одговарајућа два чвора, затим се узима следећа грана по тежини, итд. Ако одабрана грана прави петљу, уклања се и бира се наредна грана. Проналазак путање минималне дужине се врши аналогно, одабиром гране са најмањом тежином.

Сложеност алгоритма[уреди]

Сложеност овог алгоритма је реда O(EV). Постоји и бржа имплементација, коју је предложио Роберт Тарјан. Сложеност тог алгоритма је реда O(E \log V) за ретки граф, а реда O(V^2) за збијени граф. Тај алгоритам је брз колико и Примов алгоритам за минимално повезујуће стабло. 1986. године , Габов (Gabow), Галил (Galil), Спенсер (Spencer), и Тарјан (Tarjan) су направили бржу имплементацију, реда O(E + V \log V).

Алгоритам[уреди]

Опис[уреди]

Алгоритам је рекурзиван. Са f је означена функција која за дати усмерени граф са тежинским коефицијентима D и чвором r који представља корен, враћа повезујуће стабло минималне тежине, са кореном у r.

За дати усмерени граф D са тежинским коефицијентима и корен r заменимо било који скуп паралелних грана (грана између два иста чвора, у истом правцу) једном граном са тежином једнаком најмањој тежини у датом скупу грана.

Даље, за сваки чвор v различит од r, обележимо долазећу грану најмање тежине. Означимо други крај те гране са \pi(v). Грана је тако означена са (\pi(v),v), а придружена тежина са w(\pi(v),v). Ако обележене гране формирају стабло најкраће путање, f(D) је то стабло. У супротном, скуп обележених грана формира бар једну петљу. Нека је C једна од ових петљи (насумично одабрана). Дефинишемо усмерени граф са тежинским коефицијентима, D^\prime и кореном у r^\prime према следећем упутству: чворови D^\prime су чворови D који се не налазе у C и нови чвор је означен са v_C.

Ако је (u,v) грана у D где је u\notin C и v\in C, онда треба укључити у D^\prime грану e = (u, v_C), и дефинисати w(e) = w(u,v) - w(\pi(v),v).

Ако је (u,v) грана у D где је u\in C и v\notin C, онда треба укључити у D^\prime грану e = (v_C, v), и дефинисати w(e) = w(u,v) .

Ако је (u,v) грана у D где је u\notin C и v\notin C, онда треба укључити у D^\prime грану e = (u, v), и дефинисати w(e) = w(u,v) .

У D^\prime се не укључује ниједна друга грана.

Корен r^\prime стабла D^\prime је корен r стабла D.

Позивом функције f(D^\prime), налази се стабло најкраће путање за D^\prime. Прво, означе се у стаблу  D све гране које су и у  D^\prime, а које су означене у стаблу најкраће путање(СНП) за D^\prime. Такође, означе се у  D све гране из  C . Даље, претпоставимо да је у СНП за  D^\prime, (јединствена) долазећа грана у v_C (u, v_C). Та грана долази из неког пара (u,v) где је u\notin C и v\in C. Треба обрисати (\pi(v),v) и означити (u,v). Такође, за сваку означену (v_C,v) у СНП за  D^\prime која потиче од гране  (u,v) у  D где је  u\in C и  v\notin C, означити грану  (u,v). Сада скуп означених грана формира СНП, што је повратна вредност f(D).

Имплементација[уреди]

Нека је BV скуп чворова и BE скуп грана. Нека је v чвор, а e грана са највећом позитивном тежином која повезује v. Ci је петља. G0 = (V0,E0) је оригинални дијаграм. ui је заменски чвор за Ci.

BV \leftarrow BE \leftarrow \varnothing
i=0

A: if BV = V_i then goto B for неки чвор v \notin BV and v \in V_i { BV \leftarrow BV \cup \lbrace v\rbrace нађи грану  e = (x,v) тако да w(e) = max{ w(y,v)|(y,v) \in Ei} if w(e) ≤ 0 then goto A } if BE \cup \lbrace e\rbrace садржи петљу { i=i+1 конструиши G_i сажимајући C_i на u_i измени BE, BV и тежинске коефицијенте } BE \leftarrow BE \cup {e} goto A

B: while i ≠ 0 { реконструиши G_{i-1} и преименуј неке гране у BE if u_i је био корен излазног стабла BE { BE \leftarrow BE \cup \lbrace e|e \in C_i and  e \ne e_0^i\rbrace }else{ BE \leftarrow BE \cup \lbrace e|e \in C_i and e \ne \tilde{e}_i\rbrace } i=i-1 } Максимална тежина гране = \sum_{e \in BE} w(e)

Спољашње везе[уреди]