Rendszeroptimalizálás, 1. tétel

Ez az oldal a korábbi SCH wiki-ről lett áthozva. Az eredeti változata itt érhető el.

Ha úgy érzed, hogy bármilyen formázási vagy tartalmi probléma van vele, akkor kérlek javíts rajta egy rövid szerkesztéssel.

Ha nem tudod, hogyan indulj el, olvasd el a migrálási útmutatót

<style> ol { margin-top:0px; } span.formula img { margin:3px 0px; } </style>

!! Az optimális hozzárendelés problémája, Egerváry algoritmusa.

Optimális hozzárendelés (optimum assignment) problémája

1. Adott G(F∪L, E) páros gráf és w:E→R élsúlyfüggvény. Keressük M párosítást, amire Σ_e∈Mw(e) maximális.
2. Adott G(F∪L, E) páros gráf, amiben van teljes párosítás és w:E→R élsúlyfüggvény. Keressük M teljes párosítást, amire Σ_e∈Mw(e) maximális.

A két feladat nem ekvivalens, pl. a

Ezen a helyen volt linkelve a optimum_assignment_pelda.png nevű kép a régi wiki ezen oldaláról. (Kérlek hozd át ezt a képet ide, különben idővel el fog tűnni a régi wikivel együtt)

gráfban az első esetben 3 az optimum, a második esetben 2.

Az első feladat visszavezethető a másodikra, ha az F,L csúcshalmazok közül a kisebbet kiegészítjük azonos elemszámúra, a hiányzó éleket behúzzuk 0 súllyal és a negatív éleket is kinullázzuk. Elég tehát a második feladatot megoldani.

Címkézés

• Def.*: c:F∪L→R címkézés, ha ∀e=(u,v)∈E c(u)+c(v)≥w(e).
  
• Def.*: c címkézés szigorú e=(u,v) élre nézve, ha c(u)+c(v)=w(e). Az ilyen éleket a későbbiekben piros éleknek, az általuk alkotott részgráfot piros részgráfnak fogjuk nevezni.
  

• Egerváry-tétel*: teljes páros gráfban létezik M teljes párosítás és c címkézés úgy, hogy M e=(u,v) éleire c(u)+c(v)=w(e), és ilyenkor M összsúlya maximális.
  
• Biz.*: Minden párosítás éleire igaz, hogy

[math] \sum\limits_{e \in M} w(e) \le \sum\limits_{e=(u,v) \in M} \!\!\!\!\!\! c(u)+c(v) \le \sum\limits_{v \in F \cup L} \!\! c(v) [/math] (Tehát a párosításban szereplő élek összúlyánál nagyobb vagy egyenlő a párosításban szereplő pontok címkéinek összege (címkézés definiciójából), ettől pedig nagyobb vagy egyenlő az összes címke összege. Ez utóbbit tudjuk csökkenteni jobb címkeválasztással, és ez a célunk)
Ha mutatunk egy párosítást, ahol az egyenlőség is teljesül, akkor szükségképpen maximális az összsúlya. A párosítást és a címkézést az Egerváry-algoritmus segítségével keressük meg.

Egerváry-algoritmus

1. lépés: az F-beli csúcsokat címkézzük a belőle kiinduló maximális élsúllyal, az L-beli csúcsoknak 0 lesz a címkéje.
2. lépés: Keresünk egy M maximális párosítást a piros részgráfban. Ha M teljes párosítás, készen vagyunk.
3. lépés: A kékek a nem piros élek, a bordó pedig az M-ben bennelevőek
   
   Ezen a helyen volt linkelve a maxparositasabra-javitott.png nevű kép a régi wiki ezen oldaláról. (Kérlek hozd át ezt a képet ide, különben idővel el fog tűnni a régi wikivel együtt)
   • F1, L1: párosítatlan csúcsok
   • L2: F1-ből induló (piros élek alkotta) alternáló úton elérhető L-beli csúcsok
   • F2: L2 párja
   • F3, L3: maradék csúcsok

   Legyen δ = min(c(u)+c(v)-w(e) | u∈F1∪F2 és v∈L1∪L3). F1∪F2 és L1∪L3 között nincsenek piros élek, mert

   • Ha F1 és L1 között lenne piros él, hozzávehetnénk M párosításhoz → M nem lenne maximális.
   • Ha F2 és L1 között lenne piros él, lenne egy F1-L2-F2-L1 javítóút.
   • F1 és L3 között nincs piros él, különben L3 elérhető lenne egy 1 hosszú alternáló úton.
   • F2 és L3 között nincs piros él, különben L3 elérhető lenne egy F1-L2-F2-L3 alternáló úton.

   ezért δ>0. Ha F1 és F2 címkéit csökkentjük δ-val és L2 címkéit növeljük δ-val, c továbbra is címkézés marad.

4. lépés: GOTO 2

Ha az átcímkézés során keletkező piros él végpontja

• L1-beli, nő az M párosítás mérete, mivel ha a másik fele F1-ben van, akkor simán összeköthetjük, ha pedig F2-ben, akkor F1-L2-F2-L1 útom elérhető és ez hosszabb mint az eredeti.
• L3-beli, akkor F3 és L2 között megszűnik egy piros él, de az új piros élen keresztül van ugyanakkora méretű párosítás. Az új piros és L3-beli végpontja elérhető lesz alternáló úton, ezért átkerül L2-be.

L3 legfeljebb n lépés után elfogy, utána biztosan L1-beli lesz a keletkező piros él végpontja és akkor nő M mérete. Legfeljebb n² iteráció után az algoritmus megáll a teljes párosítással.

-- Peti - 2006.12.29.