Unknown user: Új oldal, tartalma: „{{GlobalTemplate|Infoszak|RopiTetel1}} ==!! Az optimális hozzárendelés problémája, E…”

2012-10-22T09:43:53Z

Új oldal, tartalma: „{{GlobalTemplate|Infoszak|RopiTetel1}} <style> ol { margin-top:0px; } span.formula img { margin:3px 0px; } </style> ==!! Az optimális hozzárendelés problémája, E…”

Új lap

{{GlobalTemplate|Infoszak|RopiTetel1}}

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

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

__TOC__

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

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

A két feladat nem ekvivalens, pl. a
{{InLineImageLink|Infoszak|RopiTetel1|optimum_assignment_pelda.png}}
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.

<div id="cimkezes"></div>
===Címkézés===

*Def.*: c:F∪L→<b>R</b> címkézés, ha ∀e=(u,v)∈E c(u)+c(v)≥w(e). <br>
*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. <br>

<div id="Egervary"></div>
*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. <br>
*Biz.*: Minden párosítás éleire igaz, hogy
<span class="formula"> <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> </span>
(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)<br>
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===

<ol>
<li> 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.
<li> 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.
<li> lépés: A kékek a nem piros élek, a bordó pedig az M-ben bennelevőek<br>
{{InLineImageLink|Infoszak|RopiTetel1|maxparositasabra-javitott.png}}
* 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 <big>→</big> 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.
<li> lépés: GOTO 2
</ol>

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<sup>2</sup> iteráció után az algoritmus megáll a teljes párosítással.

-- [[PallosPeter|Peti]] - 2006.12.29.

[[Category:Infoszak]]

Rendszeroptimalizálás, 1. tétel - Laptörténet

Unknown user: Új oldal, tartalma: „{{GlobalTemplate|Infoszak|RopiTetel1}} ol { margin-top:0px; } span.formula img { margin:3px 0px; } ==!! Az optimális hozzárendelés problémája, E…”

Unknown user: Új oldal, tartalma: „{{GlobalTemplate|Infoszak|RopiTetel1}} ==!! Az optimális hozzárendelés problémája, E…”