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

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

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

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

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

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

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

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

Опис[уреди]

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

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

Даље, за сваки чвор различит од , обележимо долазећу грану најмање тежине. Означимо други крај те гране са . Грана је тако означена са , а придружена тежина са . Ако обележене гране формирају стабло најкраће путање, је то стабло. У супротном, скуп обележених грана формира бар једну петљу. Нека је једна од ових петљи (насумично одабрана). Дефинишемо усмерени граф са тежинским коефицијентима, и кореном у према следећем упутству: чворови су чворови који се не налазе у и нови чвор је означен са .

Ако је грана у где је и , онда треба укључити у грану , и дефинисати .

Ако је грана у где је и , онда треба укључити у грану , и дефинисати .

Ако је грана у где је и , онда треба укључити у грану , и дефинисати .

У се не укључује ниједна друга грана.

Корен стабла је корен стабла .

Позивом функције , налази се стабло најкраће путање за . Прво, означе се у стаблу све гране које су и у , а које су означене у стаблу најкраће путање(СНП) за . Такође, означе се у све гране из . Даље, претпоставимо да је у СНП за , (јединствена) долазећа грана у . Та грана долази из неког пара где је и . Треба обрисати и означити . Такође, за сваку означену у СНП за која потиче од гране у где је и , означити грану . Сада скуп означених грана формира СНП, што је повратна вредност .

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

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


i=0


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

goto A


B:
while i ≠ 0 {
   реконструиши  и преименуј неке гране у BE
   if  је био корен излазног стабла BE {
        and 
   }else{
        and 
   }
   i=i-1
}
Максимална тежина гране  = 

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