Hoffman-tétel
A Hoffman-tétel azt mondja ki, hogy mikor van adott kapacitásokra egy irányított gráfban megengedett áram.
Jelölje az x szerinti S-be menő beáramlást, az S-ből való kiáramlást. A D=(V,A) irányított gráfban akkor és csak akkor van megengedett áram, ha minden halmazra.
Ha emellett a korlátok még egész értékűek is, akkor van egész értékű megengedett áram.
Bizonyítás
szerkesztésA szükségességet egyszerű igazolni:
, amiből a feltétel következik.
Az elegendőséghez vezessük be a függvényt. A feltétel most ekvivalens azzal, hogy . Jelölje az x(e) értékek összegét az X\Y és az Y\X között menő élekre.
Lemma:
Lemma bizonyítása: minden lehetséges élre le kell ellenőrizni, hogy valóban mindkét oldalhoz ugyanannyival járul hozzá.
Visszatérve a tételhez legyen egy e él pontos, ha f(e)=g(e), és Z pontos halmaz, ha γ(Z)=0.
Tegyük fel indirekt, hogy a Hoffman-feltétel nem szükséges. Ekkor vannak ellenpéldák valamely D irányított gráfon. Most rögzítsük D-t. Tekintsünk egy olyan ellenpéldát D-n, amiben a pontos élek és halmazok együttes száma maximális az ellenpéldák között.
Ha minden él pontos lenne, akkor a feltétel szerint f és g közös értéke megengedett áram lenne. Legyen a egy nem pontos él, így f(a)<g(a). Állítjuk, két pontos halmazt köt össze.
Ha ugyanis nem lépne be egy pontos T halmazba, akkor f(a)-t meg lehetne növelni egészen addig, amíg vagy a válna pontossá, vagy egy halmaz, amibe belép, és továbbra is teljesül:
Ez már nem ellenpélda, ezért van rajta megengedett áram, ami az eredetin is megengedett.
Hasonlóan bizonyítható, hogy kilép egy pontos S halmazból.
a létezése miatt , ezért a lemma szerint , ellentmondás.
Ugyanezzel a gondolatmenettel adódik az egész értékű eset.
Lineáris program
szerkesztésA szükségesség igazolása egyszerű, így itt csak az elegendőségről lesz szó.
Tekintsük a , , rendszert. Ez éppen a megengedett áramokat írja le.
Ha nincs megengedett áram, akkor a Farkas-lemma miatt van egy (y,u,v) 0 és 1 értékű vektor, amelyre
- yA+u-v=0
és 2. ug-vf<0.
, ezért minden élre feltehető, hogy u(e) és v(e) valamelyike nulla. Legyen Z azon pontok halmaza, ahol y(Z)=1. Ekkor 1. miatt minden élre, ami Z-ben, vagy V\Z-ben van, u(e)=v(e)=0, továbbá minden Z-be lépő e élre v(e)=1 u(e)=0, és minden Z-ből kilépő e élre v(e)=0 u(e)=1
Mivel és , azért 2. ellentmond a feltételeknek.