Unknown user: Új oldal, tartalma: „{{GlobalTemplate|Infoszak|RopiTetel6}} ==!! Egészértékű programozás totálisan unimoduláris együtthatómátrixszal. Alkalmazás páros gráfokra.== TOC …”

2012-10-22T09:44:36Z

Új oldal, tartalma: „{{GlobalTemplate|Infoszak|RopiTetel6}} ==!! Egészértékű programozás totálisan unimoduláris együtthatómátrixszal. Alkalmazás páros gráfokra.== __TOC__ …”

Új lap

{{GlobalTemplate|Infoszak|RopiTetel6}}

==!! Egészértékű programozás totálisan unimoduláris együtthatómátrixszal. Alkalmazás páros gráfokra.==

__TOC__

===Totális unimodularitás===

*Def.*: A mátrix TU, ha ∀M négyzetes részmátrixára det(M)∈{-1,0,1}.

A totális unimodularitás tulajdonságai: A TU marad, ha
# egy sorát vagy oszlopát -1-gyel szorozzuk
# egy sorát vagy oszlopát ismételten hozzávesszük
# hozzáveszünk egy egységvektort
# transzponáljuk

*Tétel*: A TU mátrix és b egész, akkor max{cx:Ax≤b, x egész} = max{cx:Ax≤b}. A [[RopiTetel5#Caratheodory|Caratheodory-tétel]] 3. következményeként adódik. 
*Tétel*: A TU mátrix és c egész, akkor min{yb:yA=c, y≥0, y egész} = min{yb:yA=c, y≥0}. 
*Biz.*: A duális feladatot LP feladatként felírva a kapott A mátrix (AT; -AT; E) totálisan unimoduláris, tehát az előző tétel értelmében min(DLP) = min(DIP).

===Páros gráfok illeszkedési mátrixa===

*Tétel*: minden irányított gráf illeszkedési mátrixa totálisan unimoduláris. 
*Biz.*: k×k méretű részmátrixokra teljes indukcióval.
* k=1-re trivális
* M legyen egy k×k-s részmátrix
** Ha M-ben van olyan oszlop, ami legfeljebb 1 db nem 0 elemet tartalmaz, az oszlopot elhagyva a maradék mátrix TU (indukciós feltételből), és egy egységvektort vagy egységvektor negáltat hozzávéve is TU marad.
** Ha M minden oszlopa pontosan 1 db 1-est és 1 db -1-est tartalmaz, M sorainak összege 0 <big>⇒</big> det(M)=0.

*Tétel*: minden irányítatlan páros gráf illeszkedési mátrixa totálisan unimoduláris 
*Biz.*: legyen G(L∪F, E) irányítatlan páros gráf. Irányítsunk minden élt L→F irányba. Ettől az illeszkedési mátrixban az F-hez tartozó sorok negálódnak, de a sorok negálása nem változtat a TU tulajdonságon. Mivel a kapott irányított gráf illeszkedési mátrixa az előző tétel értelmében TU, az eredeti páros gráfé is az.

===Maximális összsúlyú párosítás lefordítása LP feladatra===

Legyen x:E→{0,1} az indikátora annak, hogy egy él benne van-e a párosításban. w:E→R az élsúly függvény.
* A Bx≤(1;...;1) a 0≤x≤1, x∈Z|E feltételekkel együtt azt jelenti, hogy az egy csúcsból kiinduló élek közül legfeljebb 1-et választunk, azaz a kapott élhalmaz párosítás.
* Az x≤1 feltétel elhagyható, mert a párosítás többi feltételéből következik
* A max{wx: Bx≤(1;...;1), x≥0} feladat mátrixa TU mátrix és b vektor is egész, ezért a feladat IP-ről átfogalmazható LP-re, és polinom időben megoldható.

'''[[RopiTetel1#Egervary|Egerváry-tétel]]''' (a maximális összsúlyú párosítás és a minimális összsúlyú címkézés súlya megegyezik) bizonyítása: a [[RopiTetel3#dualitas|dualitás tételből]] következik, hogy max{wx: Bx≤(1;...;1), x≥0} = min{y(1;...;1): yB≥w, y≥0}. Minden e=uv élre y(u)+y(v)≥w(e), azaz y egy [[RopiTetel1#cimkezes|címkézés]]. A címkézés összsúlya megegyezik max{wx}-szel, a párosítás összsúlyával.

'''König-tétel''' (páros gráfban ν(G)=τ(G)) bizonyítása: w súlyfüggvényt válasszuk azonosan 1-nek. Mivel w egész, a duális feladat y megoldása is választható egésznek. 0≤y≤1 miatt y éppen a lefogó ponthalmaz indikátora lesz. ν(G) = max(wx) = min(y(1;...;1)) = τ(G).

-- [[PallosPeter|Peti]] - 2006.12.30.

[[Category:Infoszak]]

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

Unknown user: Új oldal, tartalma: „{{GlobalTemplate|Infoszak|RopiTetel6}} ==!! Egészértékű programozás totálisan unimoduláris együtthatómátrixszal. Alkalmazás páros gráfokra.== __TOC__ …”

Unknown user: Új oldal, tartalma: „{{GlobalTemplate|Infoszak|RopiTetel6}} ==!! Egészértékű programozás totálisan unimoduláris együtthatómátrixszal. Alkalmazás páros gráfokra.== TOC …”