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 ${\delta }_x(S)$ az x szerinti S-be menő beáramlást, ${\rho }_x(S)$ 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 ${\rho }_f(X)\le {\delta }_g(X)$ minden $X\subset V$ 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

A szükségességet egyszerű igazolni:

${\rho }_f(X)\le {\rho }_x(X)={\delta }_x(X)\le {\delta }_g(X)$, amiből a feltétel következik.

Az elegendőséghez vezessük be a $\gamma (x)={\delta }_g(X)-{\rho }_f(X)$ függvényt. A feltétel most ekvivalens azzal, hogy $\gamma (x)\ge 0$. Jelölje $d_x$ az x(e) értékek összegét az X\Y és az Y\X között menő élekre.

Lemma: $\gamma (X)+\gamma (Y)=\gamma (X\cap Y)+\gamma (X\cup Y)+d_{g-f}(X,Y)$

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:${\rho }_f(X)\le {\delta }_g(X)$

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 $d_{g-f}(S,T)>0$, ezért a lemma szerint $0+0=\gamma (S)+\gamma (T)>\gamma (S\cap T)+\gamma (S\cup T)\ge 0+0$, ellentmondás.

Ugyanezzel a gondolatmenettel adódik az egész értékű eset.

Lineáris program

A szükségesség igazolása egyszerű, így itt csak az elegendőségről lesz szó.

Tekintsük a $Qx\le 0$, $x\le g$, $-x\le -f$ 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

1. yA+u-v=0

és 2. ug-vf<0.

$f\le g$, 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 $ug={\delta }_g(Z)$ és $vf={\rho }_f(Z)$, azért 2. ellentmond a feltételeknek.

Források

• http://www.cs.elte.hu/~frank/jegyzet/opkut/ulin.2008.pdf