From 74fb7d21563fda8f0dfecf43a4e17a776b45ba1d Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Wed, 5 Dec 2007 14:02:22 +0100 Subject: [PATCH] Drobne korektury Dinicova algoritmu; nove obrazky. --- 3-dinic/3-dinic.tex | 106 +++---- 3-dinic/dinic-cistasit.eps | 385 +++++++++++++++++++++++ 3-dinic/dinic-neprocistenasit.eps | 489 ++++++++++++++++++++++++++++++ 3-dinic/sitc.eps | 192 ------------ 4 files changed, 923 insertions(+), 249 deletions(-) create mode 100644 3-dinic/dinic-cistasit.eps create mode 100644 3-dinic/dinic-neprocistenasit.eps delete mode 100644 3-dinic/sitc.eps diff --git a/3-dinic/3-dinic.tex b/3-dinic/3-dinic.tex index 71d6552..a7a10d5 100644 --- a/3-dinic/3-dinic.tex +++ b/3-dinic/3-dinic.tex @@ -1,69 +1,58 @@ \input ../lecnotes.tex -\prednaska{3}{Dinicùv algoritmus}{(zapsali Jakub Melka, Petr Musil)} +\prednaska{3}{Dinicùv algoritmus}{(zapsali Jakub Melka, Petr Musil)\foot{\rm s~díky Bernardovi Lidickému za obrázky}} -Na minulé pøedná¹ce jsme si ukázali \s{Fordùv} algoritmus. Víme o nìm, ¾e kdy¾ se zastaví, tak vydá maximální tok. Jen¾e zastavit se nemusí (napøíklad pro sítì s reálnými kapacitami), nebo trvá pøíli¹ dlouho. +Na~minulé pøedná¹ce jsme si ukázali \s{Fordùv} algoritmus. Víme o~nìm, ¾e kdy¾ se zastaví, tak vydá maximální tok. Jen¾e zastavit se nemusí (napøíklad pro~sítì s~reálnými kapacitami), nebo trvá pøíli¹ dlouho. Uká¾eme si lep¹í algoritmus, {\I Dinicùv}, který má výraznì men¹í slo¾itost a zastaví se v¾dy. -Idea je následující: v algoritmu budeme pou¾ívat {\I sí» rezerv}, která bude obsahovat rezervy -- kolik je¹tì po dané hranì mù¾eme pustit, aby to nepøekroèilo její kapacitu. -Sí» rezerv pak budeme vyu¾ívat k vylep¹ování toku. +Idea je následující: v~algoritmu budeme pou¾ívat {\I sí» rezerv}, která bude obsahovat rezervy -- kolik je¹tì po~dané hranì mù¾eme pustit, aby to nepøekroèilo její kapacitu. +Sí» rezerv pak budeme vyu¾ívat k~vylep¹ování toku. \s{Definice:} {\I Sí» rezerv }$R$ k síti $S=(V,E,z,s,c)$ a toku $f$ v $S$ je sí» $R=(V,E\cup\overleftarrow{E}, z,s, r)$, pro $\forall e\in E : $ \itemize\ibull \:$r(e)=c(e)-f(e)$ \:$r(\overleftarrow{e})=f(e)$ \endlist -\>kde hrana $\overleftarrow{e}$ vznikne z hrany $e$ tak, ¾e se zorientuje opaèným smìrem. V pøípadì, ¾e v síti rezerv u¾ opaènì orientovaná hrana\foot{vznikne tak, ¾e v pùvodní síti jsou dvì opaènì orientované hrany mezi stejnými vrcholy} je, pak vznikne multigraf\foot{Graf, který mù¾e mít mezi dvìma vrcholy více stejnì orientovaných hran} s multiplicitou maximálnì 2. +\>kde hrana $\overleftarrow{e}$ vznikne z~hrany $e$ tak, ¾e se zorientuje opaèným smìrem. V pøípadì, ¾e v~síti rezerv u¾ opaènì orientovaná hrana\foot{vznikne tak, ¾e v pùvodní síti jsou dvì opaènì orientované hrany mezi stejnými vrcholy.} je, pak vznikne multigraf\foot{graf, který mù¾e mít mezi dvìma vrcholy více stejnì orientovaných hran.} s~multiplicitou maximálnì 2. -\>Sí» rezerv budeme pou¾ívat v algoritmu k hledání vylep¹ujících tokù. K tomu nám bude slou¾it následující vìta : +\>Sí» rezerv budeme pou¾ívat v~algoritmu k~hledání vylep¹ujících tokù. K~tomu nám bude slou¾it následující vìta: -\s{Vìta:} Je-li $f$ tok v síti $S$ a $g$ tok v pøíslu¹né síti rezerv, pak $\exists$ tok $f'$ v $S$ takový, ¾e $\vert f'\vert = \vert f\vert + \vert g\vert$, co¾ znamená $\forall e \in E : f'(e) = f(e) + g(e) - g(\overleftarrow{e})$. +\s{Vìta:} Je-li $f$ tok v~síti $S$ a $g$ tok v~pøíslu¹né síti rezerv, pak $\exists$ tok $f'$ v $S$ takový, ¾e $\vert f'\vert = \vert f\vert + \vert g\vert$, co¾ znamená $\forall e \in E : f'(e) = f(e) + g(e) - g(\overleftarrow{e})$. \proof -Rozebereme si jednotlivé pøípady pro $\forall e\in E$. +Rozebereme si jednotlivé pøípady pro~$\forall e\in E$. \numlist\nalpha -\:$g(e)=g(\overleftarrow{e})=0 \Rightarrow f'(e)=f(e) $ -\:$g(e)>0$ a zároveò $g(\overleftarrow{e})=0\Rightarrow f'(e) = f(e) + g(e)$ -\:$g(e)=0$ a zároveò $g(\overleftarrow{e})>0\Rightarrow f'(e) = f(e) - g(\overleftarrow{e})$ -\:nastává cirkulace, odeèteme tedy $\varepsilon$ od obou hran $e$ a $\overleftarrow{e}$, +\:$g(e)=g(\overleftarrow{e})=0 \Rightarrow f'(e)=f(e) $. +\:$g(e)>0$ a zároveò $g(\overleftarrow{e})=0\Rightarrow f'(e) = f(e) + g(e)$. +\:$g(e)=0$ a zároveò $g(\overleftarrow{e})>0\Rightarrow f'(e) = f(e) - g(\overleftarrow{e})$. +\:nastává cirkulace, tu snadno odstraníme: odeèteme $\varepsilon$ od obou hran $e$ a $\overleftarrow{e}$, kde $\varepsilon=\min( g(e), g(\overleftarrow{e}) )$. Pøevedeme tím tento pøípad na jeden ze tøí uvedených vý¹e. \endlist -Je v¹ak $f'$ tok? Víme, ¾e $f'$ urèitì nemù¾e klesnout pod $0$, proto¾e se odeèítá jen v pøípadì $3$), a tam je z definice vidìt, ¾e $f'$ pod $0$ klesnout nemù¾e. Kapacita také nemù¾e -být pøekroèena, pøièítá se jen v pøípadì $2$) a z definice se nepokazí, proto¾e $g(e)=c(e)-f(e)$, tedy v nejhor¹ím pøípadì $f'(e) = c(e)$. - -Dále doká¾eme, ¾e $f'$ dodr¾uje Kirchhoffùv zákon. V následujících sumách pøedpokládejme, ¾e v¹echny vrcholy jsou rozdílné od zdroje a stoku. Musí platit, ¾e - -\>$\sum\limits_{(a,b) \in E} f'(a,b) = \sum\limits_{(b,a) \in E} f'(b,a)$ +Je v¹ak $f'$ tok? Víme, ¾e $f'$ urèitì nemù¾e klesnout pod $0$, proto¾e se odeèítá jen v pøípadì c), a tam je z~definice vidìt, ¾e $f'$ pod $0$ klesnout nemù¾e. Kapacita také nemù¾e +být pøekroèena, pøièítá se jen v~pøípadì b) a z~definice se nepokazí, proto¾e $g(e)=c(e)-f(e)$, tedy v~nejhor¹ím pøípadì $f'(e) = c(e)$. +Dále doká¾eme, ¾e $f'$ dodr¾uje Kirchhoffùv zákon. V~následujících sumách pøedpokládejme, ¾e v¹echny vrcholy jsou rozdílné od~zdroje a stoku. Musí platit, ¾e: +$$\sum\limits_{ab \in E} f'(ab) = \sum\limits_{ba \in E} f'(ba).$$ Rozepí¹eme si tuto rovnici dle definice: - - -\>$\sum\limits_{(a,b) \in E} f'(a,b) - \sum\limits_{(b,a) \in E} f'(b,a) = 0$ - - -\>$\sum\limits_{(u,v)\in E}(f(u,v)+g(u,v)-g(\overleftarrow{u,v})) - \sum\limits_{(v,u)\in E}(f(v,u)+g(v,u)-g(\overleftarrow{v,u})) = 0$ - -Roztrhneme si to na ètyøi sumy a dostaneme - -\>$\underbrace{\sum\limits_{(u,v)\in E}f(u,v)-\sum\limits_{(v,u)\in E}f(v,u)}\limits_0+$ - - -\>$+\underbrace{\sum\limits_{(u,v)\in E}g(u,v)-g(\overleftarrow{u,v})-\sum\limits_{(v,u)\in E}g(v,u)-g(\overleftarrow{v,u})}\limits_0 = 0$, - -\>nebo» $f$ i $g$ jsou toky a musí splòovat Kirchhoffùv zákon. - - +$$\sum\limits_{ab \in E} f'(ab) - \sum\limits_{ba \in E} f'(ba) = 0,$$ +$$\sum\limits_{uv\in E}(f(uv)+g(uv)-g(\overleftarrow{uv})) - \sum\limits_{vu\in E}(f(vu)+g(vu)-g(\overleftarrow{vu})) = 0.$$ +Roztrhneme si to na ètyøi sumy a dostaneme: +$$\underbrace{\sum\limits_{uv\in E}f(uv)-\sum\limits_{vu\in E}f(vu)}\limits_0+$$ +$$+\underbrace{\sum\limits_{uv\in E}g(uv)-g(\overleftarrow{uv})-\sum\limits_{vu\in E}g(vu)-g(\overleftarrow{vu})}\limits_0 = 0,$$ +nebo» $f$ i $g$ jsou toky a musí splòovat Kirchhoffùv zákon. \qed -\>Tato vìta nám øíká, ¾e pokud existuje nenulový tok v síti rezerv, pak lze tok v pùvodní síti je¹tì zvìt¹it. Naopak pokud takový tok neexistuje, je tok v pùvodní síti maximální. +\>Tato vìta nám øíká, ¾e pokud existuje nenulový tok v~síti rezerv, pak lze tok v~pùvodní síti je¹tì zvìt¹it. Naopak pokud takový tok neexistuje, je tok v~pùvodní síti maximální. -\s{Definice:} $f$ je {\I blokující tok}, pokud na ka¾dé orientované cestì $P$ ze zdroje do spotøebièe $\exists e\in P : f(e)=c(e)$. +\s{Definice:} $f$ je {\I blokující tok}, pokud na~ka¾dé orientované cestì $P$ ze~zdroje do~spotøebièe $\exists e\in P : f(e)=c(e)$. -\s{Definice:} $C$ je {\I proèi¹tìná sí»}, pokus obsahuje pouze vrcholy a hrany na nejkrat¹ích $z\rightarrow s$ cestách. Proèi¹tìná sí» nemá slepé ulièky, ani hrany vedoucí ze stoku nìkam do dal¹ího vrcholu. +\s{Definice:} $C$ je {\I proèi¹tìná sí»}, pokus obsahuje pouze vrcholy a hrany na~nejkrat¹ích $z\rightarrow s$ cestách. Proèi¹tìná sí» nemá slepé ulièky, ani hrany vedoucí ze~stoku nìkam do~dal¹ího vrcholu. + +\figure{dinic-cistasit.eps}{Pøíklad proèi¹tìné sítì}{0.5\hsize} \s{Dinicùv algoritmus} @@ -73,22 +62,25 @@ Roztrhneme si to na \:$l\leftarrow$ délka nejkrat¹í cesty $z\rightarrow s$ cesty v $R$. \:Kdy¾ $l=\infty$, tak skonèíme. \:Sestrojíme proèi¹tìnou sí» $C$, a to následujícím zpùsobem:%\foot{Ponecháme vrcholy a hrany z $R$, které le¾í na nejkrat¹ích $z\rightarrow s$ cestách} -\::spustíme BFS\foot{Breadth-First Search, standardní prohledávání do ¹íøky} algoritmus ze zdroje +\::spustíme BFS\foot{Breadth-First Search, standardní prohledávání do ¹íøky.} algoritmus ze zdroje \::BFS nám rozdìlí uzly do vrstev, vyhodíme hrany za spotøebièem a slepé ulièky. \:$g\leftarrow$ blokující tok v $C$. \:Zlep¹íme tok $f$ podle $g$ a jdeme na bod 2. \endalgo -\s{Postup tvorby proèi¹tìné sítì podrobnìji :} prohledáním do ¹íøky vytvoøíme vrstvy $C_i$, zahodíme ty za spotøebièem, ponecháme -pouze hrany mezi $C_i$ a $C_{i+1}$. Je¹tì musíme odstranit slepé ulièky - cesty, které konèí v $C_m : m < l$, proto¾e ty urèitì nejsou souèástí nejkrat¹í $z\rightarrow s$ cesty. +\s{Postup tvorby proèi¹tìné sítì podrobnìji:} prohledáním do~¹íøky vytvoøíme vrstvy $C_i$, zahodíme ty za~spotøebièem, ponecháme +pouze hrany mezi $C_i$ a $C_{i+1}$. Je¹tì musíme odstranit slepé ulièky -- cesty, které konèí v~$C_m : m < l$, proto¾e ty urèitì nejsou souèástí nejkrat¹í $z\rightarrow s$ cesty. + +Proèi¹tìní zvládneme v~lineárním èase $\O(n+m)$, v~pøípadì souvislého grafu pouze $\O(m)$. -Proèi¹tìní zvládneme v lineárním èase $O(n+m)$, v pøípadì souvislého grafu pouze $O(m)$. -\figure{sitc.eps}{Pøíklad proèi¹tìné sítì}{\hsize} +\figure{dinic-neprocistenasit.eps}{Pøíklad neproèi¹tìné sítì}{0.5\hsize} + +Na obrázku neproèi¹tìné sítì vidíme, co se má smazat. Èerné hrany ponecháme, ty tam jsou správnì. Èervené hrany jsou zpìtné, ty sma¾eme. Modré hrany jsou hrany ve~stejné vrstvì, ty rovnì¾ sma¾eme. Èervené teèkované hrany nevedou vùbec do stoku, tak¾e ty rovnì¾ sma¾eme. \s{Definice:} {\I Fází} algoritmu oznaèíme jeden bìh cyklu -- kroky 3 a¾ 9. -\>Provedeme podrobnou analýzu algoritmu z hlediska slo¾itosti a uvidíme, ¾e má slo¾itost $O(n^2m)$. Nejprve analyzujeme hledání +\>Provedeme podrobnou analýzu algoritmu z~hlediska slo¾itosti a uvidíme, ¾e má slo¾itost $\O(n^2m)$. Nejprve analyzujeme hledání blokujícího toku, pak se podíváme, kolik fází maximálnì mù¾e Dinicùv algoritmus mít. @@ -101,42 +93,42 @@ blokuj \::Doèistíme sí» tím, ¾e odstraníme slepé ulièky, které mohly vzniknout smazáním hrany $e$. \endalgo -Pøi ka¾dém prùchodu se sma¾e v¾dy alespoò 1 hrana, tedy maximálnì $m$-krát provádíme $O(n)$ -- právì tolik trvá nalezení cesty $P$, proto¾e délka cesty bude krat¹í nebo rovna $n$. Èi¹tìní pak maximálnì sma¾e celý graf, jedno mazání nás stojí konstantní èas, tedy celková slo¾itost tohoto algoritmu bude $O(m n)$. +Pøi ka¾dém prùchodu se sma¾e v¾dy alespoò 1 hrana, tedy maximálnì $m$-krát provádíme $\O(n)$ -- právì tolik trvá nalezení cesty $P$, proto¾e délka cesty bude krat¹í nebo rovna $n$. Èi¹tìní pak maximálnì sma¾e celý graf, jedno mazání nás stojí konstantní èas, tedy celková slo¾itost tohoto algoritmu bude $\O(m n)$. Doká¾eme si, ¾e poèet fází je men¹í nebo roven $n$. Algoritmus se ukonèí, pokud $l>n$, proto¾e pak u¾ neexistuje nejkrat¹í $z\rightarrow s$ cesta, pro¹li jsme v¹echny vrcholy. -\s{Lemma:} Pøi ka¾dé fázi $l$ vzroste alespoò o jedna. +\s{Lemma:} Pøi ka¾dé fázi $l$ vzroste alespoò o~jedna. \proof -Uva¾me sí» $R$, rozdìlenou na vrstvy, je¹tì pøed proèi¹tìním. Po proèi¹tìní nìkteré hrany zmizí. Pøibýt\foot{Pøibudou tak, ¾e po hranì s nulovým tokem po¹leme nìjaký tok, v opaèném smìru v síti rezerv vytvoøíme z nulové hrany nenulovou} mohou jen zrcadlové +Uva¾me sí» $R$, rozdìlenou na~vrstvy, je¹tì pøed~proèi¹tìním. Po~proèi¹tìní nìkteré hrany zmizí. Pøibýt\foot{Pøibudou tak, ¾e po~hranì s~nulovým tokem po¹leme nìjaký tok, v~opaèném smìru v~síti rezerv vytvoøíme z~nulové hrany nenulovou.} mohou jen zrcadlové protìj¹ky ji¾ existujících hran. -Uva¾me cestu $P$ délky $< l$ ze $z\rightarrow s$ a $e$ novou hranu vzniklou pøi poslání toku po hranì s nulovým tokem: +Uva¾me cestu $P$ délky $< l$ ze $z\rightarrow s$ a $e$ novou hranu vzniklou pøi~poslání toku po~hranì s~nulovým tokem: \numlist\nalpha \:hrana $e \not\in P\Rightarrow$ -- zablokování, taková cesta neexistuje. \:hrana $e \in P\Rightarrow$ délka $ > l$, proto¾e hrana $e$ vede z nìjakého vrcholu ve vrstvì $C_i$ do vrcholu ve vrstvì $C_{i-1}$. +\qeditem \endlist -\qed -\s{Vìta:} Dinicùv algoritmus najde maximální tok v èase $O(m n^2)$. +\s{Vìta:} Dinicùv algoritmus najde maximální tok v~èase $\O(m n^2)$. \proof -Slo¾itost plyne pøímo z pøedchozího lemmatu a slo¾itosti algoritmu hledání blokujícího toku. +Slo¾itost plyne pøímo z~pøedchozího lemmatu a slo¾itosti algoritmu hledání blokujícího toku. -Korektnost (najde v¾dy maximální tok) doká¾eme takto: Nech» algoritmus probìhne. Skonèit mù¾e jedinì tehdy, kdy¾ nenajde ¾ádnou cestu ze zdroje do spotøebièe v síti rezerv, kterou by +Korektnost (najde v¾dy maximální tok) doká¾eme takto: Nech» algoritmus probìhne. Skonèit mù¾e jedinì tehdy, kdy¾ nenajde ¾ádnou cestu ze~zdroje do~spotøebièe v~síti rezerv, kterou by mohl být tok vylep¹en. Tedy tok musí být nutnì maximální. \qed -Takto napsaný algoritmus je je¹tì pøíli¹ pomalý, ale jde výraznì zrychlit. Napøíklad namísto pøepoèítávání tokù na rezervy a naopak mù¾eme -minimálnì vnitøní cyklus poèítat jenom v rezervách. Proèi¹tìní se dá dìlat jednou namísto dvakrát, mù¾eme prohledávat do hloubky a mazat pøi vracení se z vrcholù. Dokonce i hledání blokujícího toku lze øe¹it v rámci prohledávání do hloubky. +Takto napsaný algoritmus je je¹tì pøíli¹ pomalý, ale jde výraznì zrychlit. Napøíklad namísto pøepoèítávání tokù na~rezervy a naopak mù¾eme +minimálnì vnitøní cyklus poèítat jenom v~rezervách. Proèi¹tìní se dá dìlat jednou namísto dvakrát, mù¾eme prohledávat do~hloubky a mazat pøi vracení se z~vrcholù. Dokonce i~hledání blokujícího toku lze øe¹it v~rámci prohledávání do~hloubky. Cesta si pamatuje minimum rezerv a pøi vracení se rezerva sni¾uje. -\>Problematika tokù v sítích má velké uplatnìní v kombinatorice a teorii grafù. Zde uvedeme jeden pøíklad : +\>Problematika tokù v~sítích má velké uplatnìní v~kombinatorice a teorii grafù. Zde uvedeme jeden pøíklad : -\>\s{Hledání maximálního párování v bipartitních grafech:} Zorientujeme v¹echny hrany zleva doprava a pøidáme zdroj, z nìj -vedou hrany do 1. partity, a stok, do nìj vedou hrany z 2. partity, hrany mezi partitami mají kapacitu 1. +\>\s{Hledání maximálního párování v bipartitních grafech:} Zorientujeme v¹echny hrany zleva doprava a pøidáme zdroj, z~nìj +vedou hrany do~1.~partity, a stok, do~nìj vedou hrany z~2.~partity, hrany mezi partitami mají kapacitu 1. \bye diff --git a/3-dinic/dinic-cistasit.eps b/3-dinic/dinic-cistasit.eps new file mode 100644 index 0000000..1f89736 --- /dev/null +++ b/3-dinic/dinic-cistasit.eps @@ -0,0 +1,385 @@ +%!PS-Adobe-2.0 EPSF-2.0 +%%Title: Diagram1.dia +%%Creator: Dia v0.94 +%%CreationDate: Sun Mar 26 18:42:37 2006 +%%For: bernard +%%Orientation: Portrait +%%Magnification: 1.0000 +%%BoundingBox: 0 0 539 213 +%%BeginSetup +%%EndSetup +%%EndComments +%%BeginProlog +[ /.notdef /.notdef /.notdef /.notdef /.notdef /.notdef /.notdef /.notdef /.notdef /.notdef +/.notdef /.notdef /.notdef /.notdef /.notdef /.notdef /.notdef /.notdef /.notdef /.notdef +/.notdef /.notdef /.notdef /.notdef /.notdef /.notdef /.notdef /.notdef /.notdef /.notdef +/.notdef /.notdef /space /exclam /quotedbl /numbersign /dollar /percent /ampersand /quoteright +/parenleft /parenright /asterisk /plus /comma /hyphen /period /slash /zero /one +/two /three /four /five /six /seven /eight /nine /colon /semicolon +/less /equal /greater /question /at /A /B /C /D /E +/F /G /H /I /J /K /L /M /N /O +/P /Q /R /S /T /U /V /W /X /Y +/Z /bracketleft /backslash /bracketright /asciicircum /underscore /quoteleft /a /b /c +/d /e /f /g /h /i /j /k /l /m +/n /o /p /q /r /s /t /u /v /w +/x /y /z /braceleft /bar /braceright /asciitilde /.notdef /.notdef /.notdef +/.notdef /.notdef /.notdef /.notdef /.notdef /.notdef /.notdef /.notdef /.notdef /.notdef +/.notdef /.notdef /.notdef /.notdef /.notdef /.notdef /.notdef /.notdef /.notdef /.notdef +/.notdef /.notdef /.notdef /.notdef /.notdef /.notdef /.notdef /.notdef /.notdef /.notdef +/space /exclamdown /cent /sterling /currency /yen /brokenbar /section /dieresis /copyright +/ordfeminine /guillemotleft /logicalnot /hyphen /registered /macron /degree /plusminus /twosuperior /threesuperior +/acute /mu /paragraph /periodcentered /cedilla /onesuperior /ordmasculine /guillemotright /onequarter /onehalf +/threequarters /questiondown /Agrave /Aacute /Acircumflex /Atilde /Adieresis /Aring /AE /Ccedilla +/Egrave /Eacute /Ecircumflex /Edieresis /Igrave /Iacute /Icircumflex /Idieresis /Eth /Ntilde +/Ograve /Oacute /Ocircumflex /Otilde /Odieresis /multiply /Oslash /Ugrave /Uacute /Ucircumflex +/Udieresis /Yacute /Thorn /germandbls /agrave /aacute /acircumflex /atilde /adieresis /aring +/ae /ccedilla /egrave /eacute /ecircumflex /edieresis /igrave /iacute /icircumflex /idieresis +/eth /ntilde /ograve /oacute /ocircumflex /otilde /odieresis /divide /oslash /ugrave +/uacute /ucircumflex /udieresis /yacute /thorn /ydieresis] /isolatin1encoding exch def +/cp {closepath} bind def +/c {curveto} bind def +/f {fill} bind def +/a {arc} bind def +/ef {eofill} bind def +/ex {exch} bind def +/gr {grestore} bind def +/gs {gsave} bind def +/sa {save} bind def +/rs {restore} bind def +/l {lineto} bind def +/m {moveto} bind def +/rm {rmoveto} bind def +/n {newpath} bind def +/s {stroke} bind def +/sh {show} bind def +/slc {setlinecap} bind def +/slj {setlinejoin} bind def +/slw {setlinewidth} bind def +/srgb {setrgbcolor} bind def +/rot {rotate} bind def +/sc {scale} bind def +/sd {setdash} bind def +/ff {findfont} bind def +/sf {setfont} bind def +/scf {scalefont} bind def +/sw {stringwidth pop} bind def +/tr {translate} bind def + +/ellipsedict 8 dict def +ellipsedict /mtrx matrix put +/ellipse +{ ellipsedict begin + /endangle exch def + /startangle exch def + /yrad exch def + /xrad exch def + /y exch def + /x exch def /savematrix mtrx currentmatrix def + x y tr xrad yrad sc + 0 0 1 startangle endangle arc + savematrix setmatrix + end +} def + +/mergeprocs { +dup length +3 -1 roll +dup +length +dup +5 1 roll +3 -1 roll +add +array cvx +dup +3 -1 roll +0 exch +putinterval +dup +4 2 roll +putinterval +} bind def +/dpi_x 300 def +/dpi_y 300 def +/conicto { + /to_y exch def + /to_x exch def + /conic_cntrl_y exch def + /conic_cntrl_x exch def + currentpoint + /p0_y exch def + /p0_x exch def + /p1_x p0_x conic_cntrl_x p0_x sub 2 3 div mul add def + /p1_y p0_y conic_cntrl_y p0_y sub 2 3 div mul add def + /p2_x p1_x to_x p0_x sub 1 3 div mul add def + /p2_y p1_y to_y p0_y sub 1 3 div mul add def + p1_x p1_y p2_x p2_y to_x to_y curveto +} bind def +/start_ol { gsave 1.1 dpi_x div dup scale} bind def +/end_ol { closepath fill grestore } bind def +28.346000 -28.346000 scale +-2.500000 -9.500000 translate +%%EndProlog + + +1.000000 1.000000 1.000000 srgb +n 6.862500 5.700000 0.950000 3.650000 0 360 ellipse f +0.100000 slw +[] 0 sd +[] 0 sd +0.000000 0.000000 0.000000 srgb +n 6.862500 5.700000 0.950000 3.650000 0 360 ellipse cp s +1.000000 1.000000 1.000000 srgb +n 10.526500 5.700000 0.950000 3.650000 0 360 ellipse f +0.100000 slw +[] 0 sd +[] 0 sd +0.000000 0.000000 0.000000 srgb +n 10.526500 5.700000 0.950000 3.650000 0 360 ellipse cp s +1.000000 1.000000 1.000000 srgb +n 13.862500 5.800000 0.950000 3.650000 0 360 ellipse f +0.100000 slw +[] 0 sd +[] 0 sd +0.000000 0.000000 0.000000 srgb +n 13.862500 5.800000 0.950000 3.650000 0 360 ellipse cp s +1.000000 1.000000 1.000000 srgb +n 17.772500 5.768000 0.950000 3.650000 0 360 ellipse f +0.100000 slw +[] 0 sd +[] 0 sd +0.000000 0.000000 0.000000 srgb +n 17.772500 5.768000 0.950000 3.650000 0 360 ellipse cp s +1.000000 1.000000 1.000000 srgb +n 3.087500 5.600000 0.462500 0.450000 0 360 ellipse f +0.100000 slw +[] 0 sd +[] 0 sd +0.000000 0.000000 0.000000 srgb +n 3.087500 5.600000 0.462500 0.450000 0 360 ellipse cp s +1.000000 1.000000 1.000000 srgb +n 20.997500 5.768000 0.450000 0.450000 0 360 ellipse f +0.100000 slw +[] 0 sd +[] 0 sd +0.000000 0.000000 0.000000 srgb +n 20.997500 5.768000 0.450000 0.450000 0 360 ellipse cp s +0.100000 slw +[] 0 sd +[] 0 sd +0 slc +n 3.414537 5.281802 m 6.321672 3.628187 l s +[] 0 sd +0 slj +0 slc +n 6.647630 3.442778 m 6.336625 3.907295 l 6.321672 3.628187 l 6.089413 3.472685 l ef +n 6.647630 3.442778 m 6.336625 3.907295 l 6.321672 3.628187 l 6.089413 3.472685 l cp s +0.100000 slw +[] 0 sd +[] 0 sd +0 slc +n 3.414537 5.918198 m 6.093929 7.401701 l s +[] 0 sd +0 slj +0 slc +n 6.422000 7.583344 m 5.863476 7.559867 l 6.093929 7.401701 l 6.105667 7.122439 l ef +n 6.422000 7.583344 m 5.863476 7.559867 l 6.093929 7.401701 l 6.105667 7.122439 l cp s +0.100000 slw +[] 0 sd +[] 0 sd +0 slc +n 3.550000 5.600000 m 6.375918 5.685311 l s +[] 0 sd +0 slj +0 slc +n 6.750748 5.696626 m 6.243431 5.931425 l 6.375918 5.685311 l 6.258519 5.431653 l ef +n 6.750748 5.696626 m 6.243431 5.931425 l 6.375918 5.685311 l 6.258519 5.431653 l cp s +0.100000 slw +[] 0 sd +[] 0 sd +0 slc +n 7.534251 3.119060 m 10.172509 7.690865 l s +[] 0 sd +0 slj +0 slc +n 10.359941 8.015664 m 9.893499 7.707553 l 10.172509 7.690865 l 10.326564 7.457644 l ef +n 10.359941 8.015664 m 9.893499 7.707553 l 10.172509 7.690865 l 10.326564 7.457644 l cp s +0.100000 slw +[] 0 sd +[] 0 sd +0 slc +n 7.812500 5.700000 m 9.895478 3.630595 l s +[] 0 sd +0 slj +0 slc +n 10.161508 3.366298 m 9.982999 3.896048 l 9.895478 3.630595 l 9.630603 3.541340 l ef +n 10.161508 3.366298 m 9.982999 3.896048 l 9.895478 3.630595 l 9.630603 3.541340 l cp s +0.100000 slw +[] 0 sd +[] 0 sd +0 slc +n 7.515823 8.237500 m 10.061063 5.845852 l s +[] 0 sd +0 slj +0 slc +n 10.334346 5.589060 m 10.141163 6.113637 l 10.061063 5.845852 l 9.798775 5.749260 l ef +n 10.334346 5.589060 m 10.141163 6.113637 l 10.061063 5.845852 l 9.798775 5.749260 l cp s +0.100000 slw +[] 0 sd +[] 0 sd +0 slc +n 11.198251 3.119060 m 13.566239 5.562896 l s +[] 0 sd +0 slj +0 slc +n 13.827192 5.832207 m 13.299714 5.647094 l 13.566239 5.562896 l 13.658796 5.299157 l ef +n 13.827192 5.832207 m 13.299714 5.647094 l 13.566239 5.562896 l 13.658796 5.299157 l cp s +0.100000 slw +[] 0 sd +[] 0 sd +0 slc +n 11.198251 8.280940 m 13.310798 8.286271 l s +[] 0 sd +0 slj +0 slc +n 13.685797 8.287218 m 13.185168 8.535955 l 13.310798 8.286271 l 13.186429 8.035957 l ef +n 13.685797 8.287218 m 13.185168 8.535955 l 13.310798 8.286271 l 13.186429 8.035957 l cp s +0.100000 slw +[] 0 sd +[] 0 sd +0 slc +n 11.476500 5.700000 m 13.484600 3.705546 l s +[] 0 sd +0 slj +0 slc +n 13.750667 3.441287 m 13.572084 3.971011 l 13.484600 3.705546 l 13.219738 3.616255 l ef +n 13.750667 3.441287 m 13.572084 3.971011 l 13.484600 3.705546 l 13.219738 3.616255 l cp s +0.100000 slw +[] 0 sd +[] 0 sd +0 slc +n 14.534251 3.219060 m 17.185798 3.213518 l s +[] 0 sd +0 slj +0 slc +n 17.560797 3.212734 m 17.061321 3.463778 l 17.185798 3.213518 l 17.060275 2.963779 l ef +n 17.560797 3.212734 m 17.061321 3.463778 l 17.185798 3.213518 l 17.060275 2.963779 l cp s +0.100000 slw +[] 0 sd +[] 0 sd +0 slc +n 14.812500 5.800000 m 17.010844 5.830702 l s +[] 0 sd +0 slj +0 slc +n 17.385808 5.835939 m 16.882365 6.078932 l 17.010844 5.830702 l 16.889347 5.578981 l ef +n 17.385808 5.835939 m 16.882365 6.078932 l 17.010844 5.830702 l 16.889347 5.578981 l cp s +0.100000 slw +[] 0 sd +[] 0 sd +0 slc +n 14.534251 8.380940 m 17.385804 8.365189 l s +[] 0 sd +0 slj +0 slc +n 17.760798 8.363118 m 17.262187 8.615876 l 17.385804 8.365189 l 17.259425 8.115883 l ef +n 17.760798 8.363118 m 17.262187 8.615876 l 17.385804 8.365189 l 17.259425 8.115883 l cp s +0.100000 slw +[] 0 sd +[] 0 sd +0 slc +n 18.444251 3.187060 m 20.337206 5.103467 l s +[] 0 sd +0 slj +0 slc +n 20.600733 5.370260 m 20.071502 5.190221 l 20.337206 5.103467 l 20.427225 4.838851 l ef +n 20.600733 5.370260 m 20.071502 5.190221 l 20.337206 5.103467 l 20.427225 4.838851 l cp s +0.100000 slw +[] 0 sd +[] 0 sd +0 slc +n 18.722500 5.768000 m 20.060697 5.768000 l s +[] 0 sd +0 slj +0 slc +n 20.435697 5.768000 m 19.935697 6.018000 l 20.060697 5.768000 l 19.935697 5.518000 l ef +n 20.435697 5.768000 m 19.935697 6.018000 l 20.060697 5.768000 l 19.935697 5.518000 l cp s +0.100000 slw +[] 0 sd +[] 0 sd +0 slc +n 18.444251 8.348940 m 20.337206 6.432533 l s +[] 0 sd +0 slj +0 slc +n 20.600733 6.165740 m 20.427225 6.697149 l 20.337206 6.432533 l 20.071502 6.345779 l ef +n 20.600733 6.165740 m 20.427225 6.697149 l 20.337206 6.432533 l 20.071502 6.345779 l cp s +gsave 2.500000 7.762500 translate 0.035278 -0.035278 scale +start_ol +5729 6016 moveto +5533 5056 lineto +5124 5280 4670 5392 conicto +4216 5504 3734 5504 conicto +2921 5504 2452 5229 conicto +1984 4954 1984 4482 conicto +1984 3933 3088 3639 conicto +3172 3617 3213 3606 conicto +3548 3506 lineto +4567 3221 4907 2908 conicto +5248 2595 5248 2053 conicto +5248 1059 4456 433 conicto +3665 -192 2384 -192 conicto +1886 -192 1338 -98 conicto +790 -5 130 192 conicto +331 1280 lineto +896 997 1444 850 conicto +1992 704 2496 704 conicto +3263 704 3743 1023 conicto +4224 1343 4224 1833 conicto +4224 2361 2963 2686 conicto +2854 2714 lineto +2496 2802 lineto +1700 3010 1330 3349 conicto +960 3689 960 4217 conicto +960 5221 1716 5810 conicto +2472 6400 3771 6400 conicto +4283 6400 4769 6304 conicto +5256 6208 5729 6016 conicto +end_ol grestore +gsave 20.940000 8.027500 translate 0.035278 -0.035278 scale +start_ol +4867 6272 moveto +4711 5440 lineto +2658 5440 lineto +1992 2036 lineto +1958 1846 1941 1717 conicto +1925 1589 1925 1516 conicto +1925 1157 2140 994 conicto +2356 832 2831 832 conicto +3872 832 lineto +3698 0 lineto +2714 0 lineto +1796 0 1346 353 conicto +896 706 896 1423 conicto +896 1551 912 1702 conicto +929 1854 963 2036 conicto +1628 5440 lineto +752 5440 lineto +918 6272 lineto +1774 6272 lineto +2121 8064 lineto +3150 8064 lineto +2809 6272 lineto +4867 6272 lineto +end_ol grestore +0.100000 slw +[] 0 sd +[] 0 sd +0 slc +n 14.534251 8.380940 m 17.084091 6.455823 l s +[] 0 sd +0 slj +0 slc +n 17.383372 6.229867 m 17.134968 6.730662 l 17.084091 6.455823 l 16.833693 6.331621 l ef +n 17.383372 6.229867 m 17.134968 6.730662 l 17.084091 6.455823 l 16.833693 6.331621 l cp s +showpage diff --git a/3-dinic/dinic-neprocistenasit.eps b/3-dinic/dinic-neprocistenasit.eps new file mode 100644 index 0000000..0ef4bca --- /dev/null +++ b/3-dinic/dinic-neprocistenasit.eps @@ -0,0 +1,489 @@ +%!PS-Adobe-2.0 EPSF-2.0 +%%Title: Diagram1.dia +%%Creator: Dia v0.94 +%%CreationDate: Sun Mar 26 18:43:17 2006 +%%For: bernard +%%Orientation: Portrait +%%Magnification: 1.0000 +%%BoundingBox: 0 0 645 410 +%%BeginSetup +%%EndSetup +%%EndComments +%%BeginProlog +[ /.notdef /.notdef /.notdef /.notdef /.notdef /.notdef /.notdef /.notdef /.notdef /.notdef +/.notdef /.notdef /.notdef /.notdef /.notdef /.notdef /.notdef /.notdef /.notdef /.notdef +/.notdef /.notdef /.notdef /.notdef /.notdef /.notdef /.notdef /.notdef /.notdef /.notdef +/.notdef /.notdef /space /exclam /quotedbl /numbersign /dollar /percent /ampersand /quoteright +/parenleft /parenright /asterisk /plus /comma /hyphen /period /slash /zero /one +/two /three /four /five /six /seven /eight /nine /colon /semicolon +/less /equal /greater /question /at /A /B /C /D /E +/F /G /H /I /J /K /L /M /N /O +/P /Q /R /S /T /U /V /W /X /Y +/Z /bracketleft /backslash /bracketright /asciicircum /underscore /quoteleft /a /b /c +/d /e /f /g /h /i /j /k /l /m +/n /o /p /q /r /s /t /u /v /w +/x /y /z /braceleft /bar /braceright /asciitilde /.notdef /.notdef /.notdef +/.notdef /.notdef /.notdef /.notdef /.notdef /.notdef /.notdef /.notdef /.notdef /.notdef +/.notdef /.notdef /.notdef /.notdef /.notdef /.notdef /.notdef /.notdef /.notdef /.notdef +/.notdef /.notdef /.notdef /.notdef /.notdef /.notdef /.notdef /.notdef /.notdef /.notdef +/space /exclamdown /cent /sterling /currency /yen /brokenbar /section /dieresis /copyright +/ordfeminine /guillemotleft /logicalnot /hyphen /registered /macron /degree /plusminus /twosuperior /threesuperior +/acute /mu /paragraph /periodcentered /cedilla /onesuperior /ordmasculine /guillemotright /onequarter /onehalf +/threequarters /questiondown /Agrave /Aacute /Acircumflex /Atilde /Adieresis /Aring /AE /Ccedilla +/Egrave /Eacute /Ecircumflex /Edieresis /Igrave /Iacute /Icircumflex /Idieresis /Eth /Ntilde +/Ograve /Oacute /Ocircumflex /Otilde /Odieresis /multiply /Oslash /Ugrave /Uacute /Ucircumflex +/Udieresis /Yacute /Thorn /germandbls /agrave /aacute /acircumflex /atilde /adieresis /aring +/ae /ccedilla /egrave /eacute /ecircumflex /edieresis /igrave /iacute /icircumflex /idieresis +/eth /ntilde /ograve /oacute /ocircumflex /otilde /odieresis /divide /oslash /ugrave +/uacute /ucircumflex /udieresis /yacute /thorn /ydieresis] /isolatin1encoding exch def +/cp {closepath} bind def +/c {curveto} bind def +/f {fill} bind def +/a {arc} bind def +/ef {eofill} bind def +/ex {exch} bind def +/gr {grestore} bind def +/gs {gsave} bind def +/sa {save} bind def +/rs {restore} bind def +/l {lineto} bind def +/m {moveto} bind def +/rm {rmoveto} bind def +/n {newpath} bind def +/s {stroke} bind def +/sh {show} bind def +/slc {setlinecap} bind def +/slj {setlinejoin} bind def +/slw {setlinewidth} bind def +/srgb {setrgbcolor} bind def +/rot {rotate} bind def +/sc {scale} bind def +/sd {setdash} bind def +/ff {findfont} bind def +/sf {setfont} bind def +/scf {scalefont} bind def +/sw {stringwidth pop} bind def +/tr {translate} bind def + +/ellipsedict 8 dict def +ellipsedict /mtrx matrix put +/ellipse +{ ellipsedict begin + /endangle exch def + /startangle exch def + /yrad exch def + /xrad exch def + /y exch def + /x exch def /savematrix mtrx currentmatrix def + x y tr xrad yrad sc + 0 0 1 startangle endangle arc + savematrix setmatrix + end +} def + +/mergeprocs { +dup length +3 -1 roll +dup +length +dup +5 1 roll +3 -1 roll +add +array cvx +dup +3 -1 roll +0 exch +putinterval +dup +4 2 roll +putinterval +} bind def +/dpi_x 300 def +/dpi_y 300 def +/conicto { + /to_y exch def + /to_x exch def + /conic_cntrl_y exch def + /conic_cntrl_x exch def + currentpoint + /p0_y exch def + /p0_x exch def + /p1_x p0_x conic_cntrl_x p0_x sub 2 3 div mul add def + /p1_y p0_y conic_cntrl_y p0_y sub 2 3 div mul add def + /p2_x p1_x to_x p0_x sub 1 3 div mul add def + /p2_y p1_y to_y p0_y sub 1 3 div mul add def + p1_x p1_y p2_x p2_y to_x to_y curveto +} bind def +/start_ol { gsave 1.1 dpi_x div dup scale} bind def +/end_ol { closepath fill grestore } bind def +28.346000 -28.346000 scale +-2.500000 -16.434513 translate +%%EndProlog + + +1.000000 1.000000 1.000000 srgb +n 6.862500 7.272280 0.950000 3.650000 0 360 ellipse f +0.100000 slw +[] 0 sd +[] 0 sd +0.000000 0.000000 0.000000 srgb +n 6.862500 7.272280 0.950000 3.650000 0 360 ellipse cp s +1.000000 1.000000 1.000000 srgb +n 10.462500 7.272280 0.950000 3.650000 0 360 ellipse f +0.100000 slw +[] 0 sd +[] 0 sd +0.000000 0.000000 0.000000 srgb +n 10.462500 7.272280 0.950000 3.650000 0 360 ellipse cp s +1.000000 1.000000 1.000000 srgb +n 13.862500 7.372280 0.950000 3.650000 0 360 ellipse f +0.100000 slw +[] 0 sd +[] 0 sd +0.000000 0.000000 0.000000 srgb +n 13.862500 7.372280 0.950000 3.650000 0 360 ellipse cp s +1.000000 1.000000 1.000000 srgb +n 17.708500 7.468280 0.950000 3.650000 0 360 ellipse f +0.100000 slw +[] 0 sd +[] 0 sd +0.000000 0.000000 0.000000 srgb +n 17.708500 7.468280 0.950000 3.650000 0 360 ellipse cp s +1.000000 1.000000 1.000000 srgb +n 3.087500 7.172280 0.462500 0.450000 0 360 ellipse f +0.100000 slw +[] 0 sd +[] 0 sd +0.000000 0.000000 0.000000 srgb +n 3.087500 7.172280 0.462500 0.450000 0 360 ellipse cp s +1.000000 1.000000 1.000000 srgb +n 20.997500 7.468280 0.450000 0.450000 0 360 ellipse f +0.100000 slw +[] 0 sd +[] 0 sd +0.000000 0.000000 0.000000 srgb +n 20.997500 7.468280 0.450000 0.450000 0 360 ellipse cp s +0.100000 slw +[] 0 sd +[] 0 sd +0 slc +n 3.414537 6.854082 m 6.321672 5.200467 l s +[] 0 sd +0 slj +0 slc +n 6.647630 5.015059 m 6.336625 5.479576 l 6.321672 5.200467 l 6.089413 5.044965 l ef +n 6.647630 5.015059 m 6.336625 5.479576 l 6.321672 5.200467 l 6.089413 5.044965 l cp s +0.100000 slw +[] 0 sd +[] 0 sd +0 slc +n 3.414537 7.490478 m 6.093929 8.973981 l s +[] 0 sd +0 slj +0 slc +n 6.422000 9.155625 m 5.863476 9.132147 l 6.093929 8.973981 l 6.105667 8.694719 l ef +n 6.422000 9.155625 m 5.863476 9.132147 l 6.093929 8.973981 l 6.105667 8.694719 l cp s +0.100000 slw +[] 0 sd +[] 0 sd +0 slc +n 3.550000 7.172280 m 6.375918 7.257591 l s +[] 0 sd +0 slj +0 slc +n 6.750748 7.268907 m 6.243431 7.503705 l 6.375918 7.257591 l 6.258519 7.003933 l ef +n 6.750748 7.268907 m 6.243431 7.503705 l 6.375918 7.257591 l 6.258519 7.003933 l cp s +0.100000 slw +[] 0 sd +[] 0 sd +0 slc +n 7.534251 4.691341 m 10.172509 9.263145 l s +[] 0 sd +0 slj +0 slc +n 10.359941 9.587944 m 9.893499 9.279834 l 10.172509 9.263145 l 10.326564 9.029924 l ef +n 10.359941 9.587944 m 9.893499 9.279834 l 10.172509 9.263145 l 10.326564 9.029924 l cp s +0.100000 slw +[] 0 sd +[] 0 sd +0 slc +n 7.812500 7.272280 m 9.895478 5.202875 l s +[] 0 sd +0 slj +0 slc +n 10.161508 4.938578 m 9.982999 5.468328 l 9.895478 5.202875 l 9.630603 5.113621 l ef +n 10.161508 4.938578 m 9.982999 5.468328 l 9.895478 5.202875 l 9.630603 5.113621 l cp s +0.100000 slw +[] 0 sd +[] 0 sd +0 slc +n 7.534251 9.853220 m 10.064779 7.422042 l s +[] 0 sd +0 slj +0 slc +n 10.335199 7.162239 m 10.147841 7.688924 l 10.064779 7.422042 l 9.801436 7.328363 l ef +n 10.335199 7.162239 m 10.147841 7.688924 l 10.064779 7.422042 l 9.801436 7.328363 l cp s +0.100000 slw +[] 0 sd +[] 0 sd +0 slc +n 11.134251 4.691341 m 13.515281 7.031082 l s +[] 0 sd +0 slj +0 slc +n 13.782755 7.293918 m 13.250899 7.121786 l 13.515281 7.031082 l 13.601347 6.765154 l ef +n 13.782755 7.293918 m 13.250899 7.121786 l 13.515281 7.031082 l 13.601347 6.765154 l cp s +0.100000 slw +[] 0 sd +[] 0 sd +0 slc +n 11.134251 9.853220 m 13.310798 9.858581 l s +[] 0 sd +0 slj +0 slc +n 13.685797 9.859505 m 13.185183 10.108273 l 13.310798 9.858581 l 13.186414 9.608274 l ef +n 13.685797 9.859505 m 13.185183 10.108273 l 13.310798 9.858581 l 13.186414 9.608274 l cp s +0.100000 slw +[] 0 sd +[] 0 sd +0 slc +n 11.412500 7.272280 m 13.480030 5.273164 l s +[] 0 sd +0 slj +0 slc +n 13.749618 5.012496 m 13.563946 5.539778 l 13.480030 5.273164 l 13.216389 5.180327 l ef +n 13.749618 5.012496 m 13.563946 5.539778 l 13.480030 5.273164 l 13.216389 5.180327 l cp s +0.100000 slw +[] 0 sd +[] 0 sd +0 slc +n 14.534251 4.791341 m 17.185798 4.785798 l s +[] 0 sd +0 slj +0 slc +n 17.560797 4.785014 m 17.061321 5.036059 l 17.185798 4.785798 l 17.060275 4.536060 l ef +n 17.560797 4.785014 m 17.061321 5.036059 l 17.185798 4.785798 l 17.060275 4.536060 l cp s +0.100000 slw +[] 0 sd +[] 0 sd +0 slc +n 14.812500 7.372280 m 17.010844 7.402982 l s +[] 0 sd +0 slj +0 slc +n 17.385808 7.408219 m 16.882365 7.651212 l 17.010844 7.402982 l 16.889347 7.151261 l ef +n 17.385808 7.408219 m 16.882365 7.651212 l 17.010844 7.402982 l 16.889347 7.151261 l cp s +0.100000 slw +[] 0 sd +[] 0 sd +0 slc +n 14.534251 9.953220 m 17.385804 9.937469 l s +[] 0 sd +0 slj +0 slc +n 17.760798 9.935398 m 17.262187 10.188156 l 17.385804 9.937469 l 17.259425 9.688163 l ef +n 17.760798 9.935398 m 17.262187 10.188156 l 17.385804 9.937469 l 17.259425 9.688163 l cp s +0.100000 slw +[] 0 sd +[] 0 sd +0 slc +n 18.380251 4.887341 m 20.332351 6.808611 l s +[] 0 sd +0 slj +0 slc +n 20.599618 7.071657 m 20.067898 6.899107 l 20.332351 6.808611 l 20.418626 6.542751 l ef +n 20.599618 7.071657 m 20.067898 6.899107 l 20.332351 6.808611 l 20.418626 6.542751 l cp s +0.100000 slw +[] 0 sd +[] 0 sd +0 slc +n 18.658500 7.468280 m 20.060697 7.468280 l s +[] 0 sd +0 slj +0 slc +n 20.435697 7.468280 m 19.935697 7.718280 l 20.060697 7.468280 l 19.935697 7.218280 l ef +n 20.435697 7.468280 m 19.935697 7.718280 l 20.060697 7.468280 l 19.935697 7.218280 l cp s +0.100000 slw +[] 0 sd +[] 0 sd +0 slc +n 18.380251 10.049220 m 20.332351 8.127950 l s +[] 0 sd +0 slj +0 slc +n 20.599618 7.864904 m 20.418626 8.393810 l 20.332351 8.127950 l 20.067898 8.037454 l ef +n 20.599618 7.864904 m 20.418626 8.393810 l 20.332351 8.127950 l 20.067898 8.037454 l cp s +gsave 2.500000 9.334780 translate 0.035278 -0.035278 scale +start_ol +5729 6016 moveto +5533 5056 lineto +5124 5280 4670 5392 conicto +4216 5504 3734 5504 conicto +2921 5504 2452 5229 conicto +1984 4954 1984 4482 conicto +1984 3933 3088 3639 conicto +3172 3617 3213 3606 conicto +3548 3506 lineto +4567 3221 4907 2908 conicto +5248 2595 5248 2053 conicto +5248 1059 4456 433 conicto +3665 -192 2384 -192 conicto +1886 -192 1338 -98 conicto +790 -5 130 192 conicto +331 1280 lineto +896 997 1444 850 conicto +1992 704 2496 704 conicto +3263 704 3743 1023 conicto +4224 1343 4224 1833 conicto +4224 2361 2963 2686 conicto +2854 2714 lineto +2496 2802 lineto +1700 3010 1330 3349 conicto +960 3689 960 4217 conicto +960 5221 1716 5810 conicto +2472 6400 3771 6400 conicto +4283 6400 4769 6304 conicto +5256 6208 5729 6016 conicto +end_ol grestore +gsave 20.940000 9.599780 translate 0.035278 -0.035278 scale +start_ol +4867 6272 moveto +4711 5440 lineto +2658 5440 lineto +1992 2036 lineto +1958 1846 1941 1717 conicto +1925 1589 1925 1516 conicto +1925 1157 2140 994 conicto +2356 832 2831 832 conicto +3872 832 lineto +3698 0 lineto +2714 0 lineto +1796 0 1346 353 conicto +896 706 896 1423 conicto +896 1551 912 1702 conicto +929 1854 963 2036 conicto +1628 5440 lineto +752 5440 lineto +918 6272 lineto +1774 6272 lineto +2121 8064 lineto +3150 8064 lineto +2809 6272 lineto +4867 6272 lineto +end_ol grestore +0.100000 slw +[] 0 sd +[] 0 sd +0 slc +n 14.534251 9.953220 m 17.084091 8.028103 l s +[] 0 sd +0 slj +0 slc +n 17.383372 7.802147 m 17.134968 8.302942 l 17.084091 8.028103 l 16.833693 7.903901 l ef +n 17.383372 7.802147 m 17.134968 8.302942 l 17.084091 8.028103 l 16.833693 7.903901 l cp s +0.100000 slw +[] 0 sd +[] 0 sd +0 slc +1.000000 0.000000 0.000000 srgb +n 8.863225 5.441066 2.421913 2.421913 219.588577 311.325462 ellipse s +[] 0 sd +0 slj +0 slc +n 6.834543 4.235732 m 6.825501 3.676788 l 6.996801 3.897653 l 7.276273 3.893132 l ef +n 6.834543 4.235732 m 6.825501 3.676788 l 6.996801 3.897653 l 7.276273 3.893132 l cp s +0.100000 slw +[] 0 sd +[] 0 sd +0 slc +0.975875 0.112764 0.032090 srgb +n 14.340216 6.146671 4.094721 4.094721 208.352852 325.345101 ellipse s +[] 0 sd +0 slj +0 slc +n 10.602251 4.552157 m 10.548134 3.995765 l 10.736698 4.202087 l 11.014894 4.175028 l ef +n 10.602251 4.552157 m 10.548134 3.995765 l 10.736698 4.202087 l 11.014894 4.175028 l cp s +0.100000 slw +[] 0 sd +[] 0 sd +0 slc +n 10.592609 8.092906 4.390150 4.390150 41.855976 148.145915 ellipse s +[] 0 sd +0 slj +0 slc +n 6.705357 10.069883 m 7.143037 10.417642 l 6.863637 10.409843 l 6.689758 10.628683 l ef +n 6.705357 10.069883 m 7.143037 10.417642 l 6.863637 10.409843 l 6.689758 10.628683 l cp s +0.100000 slw +[] 0 sd +[] 0 sd +0 slc +0.000000 0.000000 1.000000 srgb +n 8.903416 7.318665 5.568561 5.568561 344.301874 23.291516 ellipse s +[] 0 sd +0 slj +0 slc +n 14.123991 5.464213 m 14.542882 5.834389 l 14.264273 5.811986 l 14.079185 6.021431 l ef +n 14.123991 5.464213 m 14.542882 5.834389 l 14.264273 5.811986 l 14.079185 6.021431 l cp s +0.100000 slw +[] 0 sd +[] 0 sd +0 slc +n 10.210327 7.033875 7.903347 7.903347 345.391335 13.883456 ellipse s +[] 0 sd +0 slj +0 slc +n 17.765218 9.286360 m 17.684576 8.733190 l 17.882784 8.930266 l 18.159369 8.889945 l ef +n 17.765218 9.286360 m 17.684576 8.733190 l 17.882784 8.930266 l 18.159369 8.889945 l cp s +0.100000 slw +[0.200000] 0 sd +[0.200000] 0 sd +0 slc +1.000000 0.000000 0.000000 srgb +n 18.098907 7.940924 5.095559 5.095559 76.123301 143.210625 ellipse s +[] 0 sd +0 slj +0 slc +n 19.673168 12.758936 m 19.289485 13.165491 l 19.320991 12.887764 l 19.117714 12.695923 l ef +n 19.673168 12.758936 m 19.289485 13.165491 l 19.320991 12.887764 l 19.117714 12.695923 l cp s +0.100000 slw +[0.200000] 0 sd +[0.200000] 0 sd +0 slc +n 20.523276 17.455177 4.647800 4.647800 262.370045 335.408063 ellipse s +[] 0 sd +0 slj +0 slc +n 24.864022 15.878065 m 24.473265 15.478304 l 24.749496 15.520981 l 24.949377 15.325603 l ef +n 24.864022 15.878065 m 24.473265 15.478304 l 24.749496 15.520981 l 24.949377 15.325603 l cp s +0.100000 slw +[0.200000] 0 sd +[0.200000] 0 sd +0 slc +n 22.877863 13.726900 3.137477 3.137477 198.708808 306.782461 ellipse s +[] 0 sd +0 slj +0 slc +n 25.013538 11.487115 m 24.488799 11.294373 l 24.756517 11.214048 l 24.852887 10.951679 l ef +n 25.013538 11.487115 m 24.488799 11.294373 l 24.756517 11.214048 l 24.852887 10.951679 l cp s +0.100000 slw +[0.200000] 0 sd +[0.200000] 0 sd +0 slc +n 20.651986 8.352373 5.405747 5.405747 237.008785 291.992378 ellipse s +[] 0 sd +0 slj +0 slc +n 23.007451 3.516038 m 22.448609 3.502032 l 22.676347 3.339982 l 22.683350 3.060561 l ef +n 23.007451 3.516038 m 22.448609 3.502032 l 22.676347 3.339982 l 22.683350 3.060561 l cp s +0.100000 slw +[0.200000] 0 sd +[0.200000] 0 sd +0 slc +n 20.212569 -19.590058 24.545884 24.545884 83.309864 94.281036 ellipse s +[] 0 sd +0 slj +0 slc +n 23.443465 4.736181 m 22.983393 5.053725 l 23.072158 4.788686 l 22.913386 4.558651 l ef +n 23.443465 4.736181 m 22.983393 5.053725 l 23.072158 4.788686 l 22.913386 4.558651 l cp s +showpage diff --git a/3-dinic/sitc.eps b/3-dinic/sitc.eps deleted file mode 100644 index d43c706..0000000 --- a/3-dinic/sitc.eps +++ /dev/null @@ -1,192 +0,0 @@ -%!PS-Adobe-3.0 EPSF-3.0 -%%BoundingBox: 0 0 475 173 -%%Pages: 0 -%%Creator: Sun Microsystems, Inc. -%%Title: none -%%CreationDate: none -%%LanguageLevel: 2 -%%EndComments -%%BeginProlog -%%BeginResource: SDRes -/b4_inc_state save def -/dict_count countdictstack def -/op_count count 1 sub def -userdict begin -0 setgray 0 setlinecap 1 setlinewidth 0 setlinejoin 10 setmiterlimit[] 0 setdash newpath -/languagelevel where {pop languagelevel 1 ne {false setstrokeadjust false setoverprint} if} if -/bdef {bind def} bind def -/c {setgray} bdef -/l {neg lineto} bdef -/rl {neg rlineto} bdef -/lc {setlinecap} bdef -/lj {setlinejoin} bdef -/lw {setlinewidth} bdef -/ml {setmiterlimit} bdef -/ld {setdash} bdef -/m {neg moveto} bdef -/ct {6 2 roll neg 6 2 roll neg 6 2 roll neg curveto} bdef -/r {rotate} bdef -/t {neg translate} bdef -/s {scale} bdef -/sw {show} bdef -/gs {gsave} bdef -/gr {grestore} bdef -/f {findfont dup length dict begin -{1 index /FID ne {def} {pop pop} ifelse} forall /Encoding ISOLatin1Encoding def -currentdict end /NFont exch definefont pop /NFont findfont} bdef -/p {closepath} bdef -/sf {scalefont setfont} bdef -/ef {eofill}bdef -/pc {closepath stroke}bdef -/ps {stroke}bdef -/pum {matrix currentmatrix}bdef -/pom {setmatrix}bdef -/bs {/aString exch def /nXOfs exch def /nWidth exch def currentpoint nXOfs 0 rmoveto pum nWidth aString stringwidth pop div 1 scale aString show pom moveto} bdef -%%EndResource -%%EndProlog -%%BeginSetup -%%EndSetup -%%Page: 1 1 -%%BeginPageSetup -%%EndPageSetup -pum -0.02833 0.02826 s -0 -6120 t -/tm matrix currentmatrix def -gs -tm setmatrix --601 -423 t -1 1 s -601 423 m 17365 423 l 17365 6542 l 601 6542 l 601 423 l eoclip newpath -gs -601 423 m 17365 423 l 17365 6542 l 601 6542 l 601 423 l eoclip newpath -601 423 m 17366 423 l 17366 6543 l 601 6543 l 601 423 l eoclip newpath -40 lw 1 lj 0.000 c 3569 5040 m 3293 5040 3069 4256 3069 3290 ct 3069 2324 3293 1540 3569 1540 ct -3845 1540 4069 2324 4069 3290 ct 4069 4256 3845 5040 3569 5040 ct pc -5603 5040 m 5327 5040 5103 4256 5103 3290 ct 5103 2324 5327 1540 5603 1540 ct -5879 1540 6103 2324 6103 3290 ct 6103 4256 5879 5040 5603 5040 ct pc -7702 5040 m 7426 5040 7202 4256 7202 3290 ct 7202 2324 7426 1540 7702 1540 ct -7978 1540 8202 2324 8202 3290 ct 8202 4256 7978 5040 7702 5040 ct pc -12162 5040 m 11886 5040 11662 4256 11662 3290 ct 11662 2324 11886 1540 12162 1540 ct -12438 1540 12662 2324 12662 3290 ct 12662 4256 12438 5040 12162 5040 ct pc -14123 5040 m 13847 5040 13623 4256 13623 3290 ct 13623 2324 13847 1540 14123 1540 ct -14399 1540 14623 2324 14623 3290 ct 14623 4256 14399 5040 14123 5040 ct pc -1751 3540 m 1613 3540 1501 3428 1501 3290 ct 1501 3152 1613 3040 1751 3040 ct -1889 3040 2001 3152 2001 3290 ct 2001 3428 1889 3540 1751 3540 ct pc -gs -gs -pum -1580 3509 t -12 0 m 12 0 12 0 12 -45 ct 12 -45 12 -45 221 -287 ct 197 -286 176 -285 158 -285 ct -158 -285 158 -285 24 -285 ct 24 -285 24 -285 24 -330 ct 24 -330 24 -330 293 -330 ct -293 -330 293 -330 293 -293 ct 293 -293 293 -293 115 -84 ct 115 -84 115 -84 81 -45 ct -106 -47 129 -48 151 -48 ct 151 -48 151 -48 303 -48 ct 303 -48 303 -48 303 0 ct -303 0 303 0 12 0 ct p ef -pom -gr -gr -15851 3540 m 15713 3540 15601 3428 15601 3290 ct 15601 3152 15713 3040 15851 3040 ct -15989 3040 16101 3152 16101 3290 ct 16101 3428 15989 3540 15851 3540 ct pc -gs -gs -pum -15682 3509 t -20 -100 m 20 -100 20 -100 75 -107 ct 78 -85 87 -68 101 -57 ct 115 -45 135 -39 161 -39 ct -187 -39 206 -44 218 -55 ct 231 -65 237 -77 237 -91 ct 237 -104 231 -114 220 -121 ct -213 -126 193 -132 163 -140 ct 122 -150 93 -159 77 -167 ct 61 -174 49 -185 41 -198 ct -33 -211 29 -226 29 -242 ct 29 -257 32 -270 39 -283 ct 46 -295 55 -306 67 -314 ct -75 -320 87 -326 102 -330 ct 117 -335 134 -337 151 -337 ct 177 -337 200 -333 219 -326 ct -239 -318 253 -308 263 -296 ct 272 -283 278 -266 282 -245 ct 282 -245 282 -245 227 -238 ct -225 -255 217 -268 205 -277 ct 193 -286 177 -291 155 -291 ct 129 -291 111 -287 100 -278 ct -89 -270 83 -260 83 -249 ct 83 -241 85 -235 90 -229 ct 94 -223 102 -218 111 -214 ct -117 -212 133 -208 161 -200 ct 201 -190 228 -181 244 -174 ct 260 -167 272 -158 281 -145 ct -290 -132 294 -116 294 -97 ct 294 -79 289 -61 278 -45 ct 267 -28 251 -15 231 -6 ct -210 3 187 7 161 7 ct 118 7 85 -2 63 -20 ct 41 -38 26 -65 20 -100 ct p ef -pom -gr -gr -3576 2273 m 3507 2273 3451 2217 3451 2148 ct 3451 2079 3507 2023 3576 2023 ct -3645 2023 3701 2079 3701 2148 ct 3701 2217 3645 2273 3576 2273 ct p ef -0 lw 3576 2273 m 3507 2273 3451 2217 3451 2148 ct 3451 2079 3507 2023 3576 2023 ct -3645 2023 3701 2079 3701 2148 ct 3701 2217 3645 2273 3576 2273 ct pc -gs -gs -pum -9809 3509 t -56 0 m 56 -64 l 120 -64 l 120 0 l 56 0 l p ef -234 0 m 234 -64 l 298 -64 l 298 0 l 234 0 l p ef -412 0 m 412 -64 l 476 -64 l 476 0 l 412 0 l p ef -pom -gr -gr -3576 3173 m 3507 3173 3451 3117 3451 3048 ct 3451 2979 3507 2923 3576 2923 ct -3645 2923 3701 2979 3701 3048 ct 3701 3117 3645 3173 3576 3173 ct p ef -3576 3173 m 3507 3173 3451 3117 3451 3048 ct 3451 2979 3507 2923 3576 2923 ct -3645 2923 3701 2979 3701 3048 ct 3701 3117 3645 3173 3576 3173 ct pc -3576 4473 m 3507 4473 3451 4417 3451 4348 ct 3451 4279 3507 4223 3576 4223 ct -3645 4223 3701 4279 3701 4348 ct 3701 4417 3645 4473 3576 4473 ct p ef -3576 4473 m 3507 4473 3451 4417 3451 4348 ct 3451 4279 3507 4223 3576 4223 ct -3645 4223 3701 4279 3701 4348 ct 3701 4417 3645 4473 3576 4473 ct pc -5576 2473 m 5507 2473 5451 2417 5451 2348 ct 5451 2279 5507 2223 5576 2223 ct -5645 2223 5701 2279 5701 2348 ct 5701 2417 5645 2473 5576 2473 ct p ef -5576 2473 m 5507 2473 5451 2417 5451 2348 ct 5451 2279 5507 2223 5576 2223 ct -5645 2223 5701 2279 5701 2348 ct 5701 2417 5645 2473 5576 2473 ct pc -5576 4273 m 5507 4273 5451 4217 5451 4148 ct 5451 4079 5507 4023 5576 4023 ct -5645 4023 5701 4079 5701 4148 ct 5701 4217 5645 4273 5576 4273 ct p ef -5576 4273 m 5507 4273 5451 4217 5451 4148 ct 5451 4079 5507 4023 5576 4023 ct -5645 4023 5701 4079 5701 4148 ct 5701 4217 5645 4273 5576 4273 ct pc -7676 2673 m 7607 2673 7551 2617 7551 2548 ct 7551 2479 7607 2423 7676 2423 ct -7745 2423 7801 2479 7801 2548 ct 7801 2617 7745 2673 7676 2673 ct p ef -7676 2673 m 7607 2673 7551 2617 7551 2548 ct 7551 2479 7607 2423 7676 2423 ct -7745 2423 7801 2479 7801 2548 ct 7801 2617 7745 2673 7676 2673 ct pc -7676 4073 m 7607 4073 7551 4017 7551 3948 ct 7551 3879 7607 3823 7676 3823 ct -7745 3823 7801 3879 7801 3948 ct 7801 4017 7745 4073 7676 4073 ct p ef -7676 4073 m 7607 4073 7551 4017 7551 3948 ct 7551 3879 7607 3823 7676 3823 ct -7745 3823 7801 3879 7801 3948 ct 7801 4017 7745 4073 7676 4073 ct pc -14076 3373 m 14007 3373 13951 3317 13951 3248 ct 13951 3179 14007 3123 14076 3123 ct -14145 3123 14201 3179 14201 3248 ct 14201 3317 14145 3373 14076 3373 ct p ef -14076 3373 m 14007 3373 13951 3317 13951 3248 ct 13951 3179 14007 3123 14076 3123 ct -14145 3123 14201 3179 14201 3248 ct 14201 3317 14145 3373 14076 3373 ct pc -12176 2473 m 12107 2473 12051 2417 12051 2348 ct 12051 2279 12107 2223 12176 2223 ct -12245 2223 12301 2279 12301 2348 ct 12301 2417 12245 2473 12176 2473 ct p ef -12176 2473 m 12107 2473 12051 2417 12051 2348 ct 12051 2279 12107 2223 12176 2223 ct -12245 2223 12301 2279 12301 2348 ct 12301 2417 12245 2473 12176 2473 ct pc -12176 4073 m 12107 4073 12051 4017 12051 3948 ct 12051 3879 12107 3823 12176 3823 ct -12245 3823 12301 3879 12301 3948 ct 12301 4017 12245 4073 12176 4073 ct p ef -12176 4073 m 12107 4073 12051 4017 12051 3948 ct 12051 3879 12107 3823 12176 3823 ct -12245 3823 12301 3879 12301 3948 ct 12301 4017 12245 4073 12176 4073 ct pc -3451 2148 m 3056 2558 l 2889 2239 l 3451 2148 l p ef -1741 3022 m 3059 2331 l 3078 2366 l 1759 3058 l 1741 3022 l p ef -3576 3173 m 3062 3452 l 2997 3088 l 3576 3173 l p ef -1924 3446 m 3135 3231 l 3142 3270 l 1930 3486 l 1924 3446 l p ef -3451 4348 m 2893 4233 l 3074 3922 l 3451 4348 l p ef -1937 3449 m 3087 4114 l 3067 4149 l 1917 3483 l 1937 3449 l p ef -5451 4148 m 4935 4388 l 4894 4030 l 5451 4148 l p ef -3699 4328 m 5020 4177 l 5024 4217 l 3703 4368 l 3699 4328 l p ef -5451 2348 m 5016 2716 l 4883 2381 l 5451 2348 l p ef -3694 3029 m 5042 2490 l 5057 2527 l 3708 3067 l 3694 3029 l p ef -7676 2673 m 7351 3140 l 7136 2852 l 7676 2673 l p ef -5689 4132 m 7318 2915 l 7342 2948 l 5713 4164 l 5689 4132 l p ef -7551 3948 m 7025 3731 l 7260 3459 l 7551 3948 l p ef -5714 2333 m 7237 3650 l 7211 3681 l 5688 2363 l 5714 2333 l p ef -7676 2423 m 7130 2582 l 7143 2223 l 7676 2423 l p ef -5702 2328 m 7245 2387 l 7244 2427 l 5700 2368 l 5702 2328 l p ef -14076 3123 m 13509 3072 l 13653 2742 l 14076 3123 l p ef -12309 2330 m 13688 2932 l 13672 2968 l 12293 2366 l 12309 2330 l p ef -13951 3248 m 13524 3625 l 13384 3293 l 13951 3248 l p ef -12293 3930 m 13545 3398 l 13561 3435 l 12309 3966 l 12293 3930 l p ef -15601 3289 m 15056 3453 l 15067 3093 l 15601 3289 l p ef -14202 3228 m 15170 3256 l 15169 3296 l 14200 3268 l 14202 3228 l p ef -5451 2348 m 4894 2466 l 4935 2108 l 5451 2348 l p ef -3703 2128 m 5024 2279 l 5020 2319 l 3699 2168 l 3703 2128 l p ef -gr -gs -601 423 m 17365 423 l 17365 6542 l 601 6542 l 601 423 l eoclip newpath -gr -gr -0 6120 t -pom -count op_count sub {pop} repeat countdictstack dict_count sub {end} repeat b4_inc_state restore -%%PageTrailer -%%Trailer -%%EOF -- 2.39.2