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)\leq \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[szerkesztés]

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

$\rho _{f}(X)\leq \rho _{x}(X)=\delta _{x}(X)\leq \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)\geq 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)\leq \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)\geq 0+0$ , ellentmondás.

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

Lineáris program[szerkesztés]

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

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

yA+u-v=0

és 2. ug-vf<0.

$f\leq 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