From ff2e9f230b92a649ab9915886c912d83fe68a438 Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Thu, 29 Nov 2007 16:27:55 +0100 Subject: [PATCH] Korektury Dinicova algoritmu. --- 3-dinic/3-dinic.tex | 123 ++++++++++++++++++++++++++------------------ 3-dinic/sitc.eps | 52 +++++++++---------- 2 files changed, 99 insertions(+), 76 deletions(-) diff --git a/3-dinic/3-dinic.tex b/3-dinic/3-dinic.tex index 181b24d..71d6552 100644 --- a/3-dinic/3-dinic.tex +++ b/3-dinic/3-dinic.tex @@ -1,25 +1,25 @@ \input ../lecnotes.tex -\prednaska{3}{Toky v sítích (2. èást)}{(zapsali Jakub Melka, Petr Musil)} +\prednaska{3}{Dinicùv algoritmus}{(zapsali Jakub Melka, Petr Musil)} -Na minulé pøedná¹ce jsme si ukázali \s{Ford-Fulkersonùv} algoritmus. O nìm víme, ¾e kdy¾ se zastaví, tak \uv{vydá} maximální tok. Jen¾e on se zastavit 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 \uv{rezervy} - kolik je¹tì po dané hranì mù¾eme pustit, aby to nepøekroèilo její kapacitu. -Sí» rezerv pak budeme urèitým zpùsobem 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 tam u¾ opaènì orientovaná hrana 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. -\>Musíme ale zjistit, zda vùbec jde vylep¹ovat tok pomocí sítì rezerv. 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 f'$ v $S$ takový, ¾e $\vert f'\vert = \vert f\vert + \vert g\vert$. +\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$. @@ -28,92 +28,115 @@ Rozebereme si jednotliv \:$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}$, -kde $\varepsilon=\min(\lbrace g(e), g(\overleftarrow{e}) \rbrace )$. Pøevedeme tím tento pøípad na jeden ze tøí uvedených vý¹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? Tok $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 to 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 \uv{nepokazí}, proto¾e $g(e)=c(e)-f(e)$ - tedy v nejhor¹ím pøípadì $f'(e) = c(e)$. +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)$ + +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. + \qed -\>Tato vìta nám øíká, ¾e pokud existuje je¹tì tok v síti rezerv, pak jde tok v standardní síti je¹tì zvý¹it o tento tok v síti rezerv. Pokud bude tok v standardní síti maximální, tak tok v síti rezerv bude nulový. +\>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:} $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{Dinicùv algoritmus} \algo \:$f\leftarrow$ nulový tok -\:sestrojíme sí» rezerv $R$ -\:$l$ je délka nejkrat¹í cesty $z\rightarrow s$ cesty v $R$ -\:kdy¾ $l=\infty$, tak skonèi -\: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} +\:Sestrojíme sí» rezerv $R$, vynecháme hrany s nulovou rezervou. +\:$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 -\::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$ takto : -\::$g\leftarrow$ nulový tok -\::Dokud existuje cesta od zdroje ke spotøebièi -\:::Nasytíme cestu - po¹leme po ní tolik, aby obsahovala nasycenou hranu -\:::Sma¾eme nasycené hrany a doèistíme sí» (sí» nyní mù¾e obsahovat slepé ulièky díky smazání nasycených hran) -\:zlep¹íme tok $f$ podle $g$ a jdeme na bod 2 +\::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 -\>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. +\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)$. \figure{sitc.eps}{Pøíklad proèi¹tìné sítì}{\hsize} -\s{Postup tvorby proèi¹tìné sítì podrobnìji :} prohledáním do ¹íøky vytvoøíme vrstvy, 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{Definice:} {\I Fází} algoritmu oznaèíme jeden bìh cyklu -- kroky 3 a¾ 9. -Proèi¹tìní zvládneme v lineárním èase $O(n+m)$, v pøípadì souvislého grafu pouze $O(m)$. +\>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. -\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{Algoritmus hledání blokujícího toku} \algo \:$g\leftarrow$ nulový tok -\:Dokud $\exists z\rightarrow s$ cesta $P$ v síti $C$ : -\::$\varepsilon = \min\limits_{e\in P}\lbrace c(e)-f(e) \rbrace$ -\::$\forall e \in P :g(e)=g(e)+\varepsilon$, pokud $g(e)=r(e)$ tak sma¾eme hranu $e$ - proèistíme sí». +\:Dokud $\exists z\rightarrow s$ cesta $P$ v proèi¹tìné síti $C$: +\::$\varepsilon \leftarrow \min\limits_{e\in P} (c(e)-f(e)) $ +\::$\forall e \in P :g(e)\leftarrow g(e)+\varepsilon$, pokud $g(e)$ vzroste na $r(e)$, tak sma¾eme hranu $e$, +\::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)$. È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\cdot 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 mohou jen zrcadlové -protìj¹ky ji¾ existujících hran (døíve tam byl tok $O$, zvý¹ením vznikne zrcadlová hrana). +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 $\leq l$ ze $z\rightarrow s$ : +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 -\:$\not\in P\Rightarrow$ zablokování -\:$\in P\Rightarrow$ délka $ > l$ +\: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}$. \endlist \qed -\s{Vìta: } Dinicùv algoritmus najde maximální tok v èase $O(m\cdot n^2)$. +\s{Vìta:} Dinicùv algoritmus najde maximální tok v èase $O(m n^2)$. \proof -Plyne pøímo z pøedchozího lemmatu a slo¾itosti algoritmu hledání blokujícího toku. -\qed +Slo¾itost plyne pøímo z pøedchozího lemmatu a slo¾itosti algoritmu hledání blokujícího toku. -\s{Vìta: } Dinicùv algoritmus najde v¾dy maximální tok. - -\proof -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 pro implementaci pøíli¹ pracný. 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 $2\times$. Napøíklad 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 pak hned rezervu sni¾uje. + +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 : -\>\s{Hledání maximálního párování v bipartitních grafech :} Zorientujeme v¹echny hrany zleva do prava 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/sitc.eps b/3-dinic/sitc.eps index ef69b1f..d43c706 100644 --- a/3-dinic/sitc.eps +++ b/3-dinic/sitc.eps @@ -61,7 +61,7 @@ tm setmatrix 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 -0 lw 1 lj 0.000 c 3569 5040 m 3293 5040 3069 4256 3069 3290 ct 3069 2324 3293 1540 3569 1540 ct +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 @@ -107,7 +107,7 @@ 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 -3576 2273 m 3507 2273 3451 2217 3451 2148 ct 3451 2079 3507 2023 3576 2023 ct +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 @@ -155,30 +155,30 @@ gr 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 3122 2490 l 2983 2224 l 3451 2148 l p ef -1 lw 0 lj 1750 3040 m 3132 2315 l ps -3576 3173 m 3159 3399 l 3107 3104 l 3576 3173 l p ef -1927 3466 m 3222 3236 l ps -3451 4348 m 2986 4252 l 3137 3993 l 3451 4348 l p ef -1927 3466 m 3139 4168 l ps -5451 4148 m 5050 4402 l 4978 4110 l 5451 4148 l p ef -3922 4526 m 5102 4234 l ps -5451 2348 m 5089 2654 l 4977 2376 l 5451 2348 l p ef -3701 3048 m 5117 2482 l ps -7676 2673 m 7405 3062 l 7226 2822 l 7676 2673 l p ef -5701 4148 m 7388 2888 l ps -7551 3948 m 7113 3767 l 7309 3540 l 7551 3948 l p ef -5701 2348 m 7279 3713 l ps -7676 2423 m 7221 2556 l 7232 2256 l 7676 2423 l p ef -5701 2348 m 7316 2409 l ps -14076 3123 m 13604 3080 l 13724 2805 l 14076 3123 l p ef -12301 2348 m 13746 2979 l ps -13951 3248 m 13595 3562 l 13478 3286 l 13951 3248 l p ef -12301 3948 m 13620 3389 l ps -15601 3289 m 15147 3426 l 15156 3126 l 15601 3289 l p ef -14201 3248 m 15241 3278 l ps -5451 2348 m 4987 2446 l 5021 2148 l 5451 2348 l p ef -3701 2148 m 5093 2307 l ps +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 -- 2.39.5