Rendszeroptimalizálás, 6. 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

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

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

1. egy sorát vagy oszlopát -1-gyel szorozzuk
2. egy sorát vagy oszlopát ismételten hozzávesszük
3. hozzáveszünk egy egységvektort
4. 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 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 (A^T; -A^T; 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 ⇒ 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ó.

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 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 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).

-- Peti - 2006.12.30.