T Чист текст | // Верзија за штампање

Страхиња Радић

Проблем калињинградских (кенигсбершких) мостова

$ \begin{figure}[!htp] \entrymodifiers={=<1mm>} \[\xymatrix{% &\ar@{}|{\smash[t]{\txt{$C$\\$\vphantom{C}$}}}@(ul,dr)[]\circ\ar@/_/_c@{-}[dl]\ar@/^/_d@{-}[dl]\\ \ar@{}|{\txt{$A\phantom{AA}$}}[]\circ\ar@{-}^e[rr] &&\ar@{}|{\txt{$\phantom{DD}D$}}[]\circ\ar@/_/@{-}_g[ul]\ar@/^/^f@{-}[dl]\\ &\ar@{}|{\smash[b]{\txt{$\vphantom{B}$\\$B$}}}@(dl,ur)[]\circ\ar@/^/^a@{-}[ul]\ar@/_/^b@{-}[ul]}\] \caption{ÐпÑÑÑаÑовани пÑиказ калиÑингÑадÑÐºÐ¸Ñ Ð¼Ð¾ÑÑова.} \end{figure} $

Задатак. Следећи проблем је решио Леонард Ојлер (1707.-1783.). Река Прегоља (Прегел) која тече око речног острва се дели на два рукавца. Преко острва и 3 обале реке: A, B, C и D је постављено 7 мостова: a, b, c, d, e, f и g. Да ли се преко свих мостова може прећи одједном, а да се ни преко једног не пређе два или више пута?

Решење. Пре свега, потребно је да шематски представимо само најбитније податке: појединачне обале, у облику чворова графа, и мостове којим су оне повезане, у облику ивица графа (сл. 1). Означимо (непразан) скуп свих чворова са V, а ивица са E. Граф не представља ништа друго до њихов уређени пар: G=V\times E. Граф је повезан уколико се састоји од тачно једног чвора или је сваки његов чвор повезан са бар једним другим чвором. Граф је затворен уколико се сваки такав његов обилазак при коме се преко сваке ивице пролази тачно једном завршава у почетном чвору.

Дефиниција 1. Степен чвора је број ивица којима је он један од крајева. Ако је степен чвора непаран, онда се тај чвор назива непарним чвором, а иначе парним чвором. Скуп свих непарних чворова ћемо означавати са V^1, а парних са V^2. Очита је једнакост V=V^1\unija V^2.

Лема 1. Збир степена свих чворова у графу је једнак двоструком броју свих ивица.

Доказ. Пошто свака ивица има два краја — чвора, она ће бити урачуната два пута, по једном за сваки чвор, па ће збир степена свих чворова бити једнак двоструком броју свих ивица \Bigl(\suml_{X\in E}\deg(X)=2\ngred{E}\Bigr).\ \Box

Лема 2. Ако граф може да се обиђе прелазећи преко сваке ивице тачно једном, онда сваки његов непарни чвор мора бити или почетни или завршни.

Доказ. Нека је степен чвора X једнак 2k+1, тј. нека је он непаран. Сведимо проблем на тривијални случај: претпоставимо да смо кроз X већ прошли 2k пута.

Ако се не налазимо у чвору X, то значи да при повратку у X нећемо моћи да наставимо пут, па је X завршни чвор.

Ако се налазимо у чвору X, претпоставимо супротно: да он није почетни. То значи да смо у њега морали да уђемо из неког другог чвора. Међутим, пошто смо прешли паран број ивица (2k), то значи да се налазимо ван чвора X (улазили смо у X, али смо увек и излазили из њега). Контрадикција. Дакле, X је почетни чвор. \Box

На овом месту бисмо већ могли да станемо и констатујемо да тражени граф садржи четири непарна чвора, па је зато немогуће испунити тражени услов (не могу сва 4 бити почетни или завршни). Међутим, општости ради, наведимо још неке чињенице.

Лема 3. Повезани граф не може да садржи непаран број непарних чворова.

Доказ. Према леми 1, имамо да је збир степенова свих чворова паран. Означимо га са 2n. Степенови парних чворова су парни, па је и њихов збир такође паран, рецимо 2p. Међутим, и разлика 2n-2p=2(n-p) је такође парна, па збир степенова непарних чворова такође мора бити паран, што је немогуће ако је њихов број непаран. \Box

Дефиниција 2. Запис пута је низ слова која представљају ознаке чворова у оном редоследу којим се обилази граф.

Лема 4. Ако са p(X) означимо број појављивања ознаке чвора X у запису пута, а са \deg(X) степен тог чвора, онда важи:

$ \[p(X)=\begin{cases}% \frac{\deg(X)+1}{2}\text{,}&2\bnedel\deg(X)\text{,}\\ \frac{\deg(X)}{2}+1\text{,}&2\big|{\deg(X)}\land\textup{[}X\text{ Ñе поÑеÑни ÑвоÑ\textup{]}}\text{,}\\ \frac{\deg(X)}{2}\text{,}&2\big|{\deg(X)}\land\textup{[}X\text{ ниÑе поÑеÑни ÑвоÑ\textup{]}}\text{.} \end{cases}\] $

Доказ. Нека је 2\bnedel\deg(X), тј. \deg(X)=2k+1. Тада ће се за првих 2k пролазака кроз чвор X ознака тог чвора појавити k+1 пута ако је он почетни, односно k пута ако је завршни чвор. Међутим, у првом од ова два случаја се ознака неће појављивати у последњем проласку, јер он води ван чвора, па се број појављивања неће увећати, а у другом ће се број појављивања увећати за један. У оба случаја имамо да је p(X)=k+1=\bigl(\deg(X)+1\bigr)/2.

За преостале случајеве закључивање је слично. \Box

Теорема 1. Повезани граф се може обићи прелазећи преко сваке ивице тачно једном акко је број његових непарних чворова нула или два. У првом случају је граф затворен, а у другом није.

Доказ. \potrebno Нека се граф може обићи. Уведимо функцију d(X) на следећи начин:

$ \[d(X)=\begin{cases}% \frac{\deg(X)+1}{2}\text{,}&2\bnedel{\deg(X)}\text{,}\\ \frac{\deg(X)}{2}\text{,}&2\big|{\deg(X)}\text{.} \end{cases}\] $

Очигледно је \forall X\in V\quad d(X)\les p(X), па је \suml_X d(X)\les\suml_X p(X), и:

$ \begin{align*} \suml_{X\in V}d(X)&=\biggl\{\suml_{X\in V^1}\frac{\deg(X)+1}{2}\biggr\}+\biggl\{\suml_{X\in V^2}\frac{\deg(X)}{2}\biggr\}=\frac{1}{2}\biggl\{\ngred{V^1}+\suml_{X\in V}\deg(X)\biggr\}=\\ &=\ngred{E}+\frac{\ngred{V^1}}{2}\les\suml_{X\in V}p(X)=\ngred{E}+1\text{.} \end{align*} $

Последња једнакост следи из простог закључивања: збир свих појављивања свих слова је једнак броју свих ивица увећаном за један (јер се за сваку ивицу рачуна почетни, а за завршну и завршни чвор, без обзира на то да ли је граф затворен или не). Одатле следи:

$ \[\ngred{V^1}\les 2\text{;}\quad\ngred{V^1}\in\N\unija\{0\}\sledi\ngred{V^1}\in\{0, 1, 2\}\text{.}\] $

Из услова теореме имамо да је граф повезан, па према леми 3 не може да садржи тачно један непарни чвор. Дакле, \ngred{V^1}\in\{0, 2\}.

Нека је број непарних чворова нула, тј. нека се граф састоји само од парних чворова. Тада морамо један од њих изабрати за почетни. Означимо га са X, и нека је \deg(X)=2k. Сличним закључивањем као у доказу леме 2, претпоставимо да смо већ обавили k-1 излазака из чвора X и k-1 улазака у чвор X. Пошто се налазимо у чвору X, а преостале су нам још две ивице (јер смо прошли 2k-2 ивице које су повезане са чвором X), преко једне од њих ћемо изаћи из чвора X, али ћемо једном ипак морати да се вратимо у чвор X, и то преко 2k-те ивице. Тада неће више бити ивица које су повезане са чвором X а нисмо их прешли, па је X уједно и завршни чвор.

У другом случају, када је број непарних чворова два, имамо два различита непарна чвора, од којих један према леми 2 мора бити почетни, па је према истој леми онај други завршни (јер иначе не би били различити). \Box

\dovolyno Нека је број непарних чворова нула (нека су сви чворови парни).

Пре свега, докажимо да је од свих могућих путева (низова ивица) кроз задани граф најдужи пут затворен. Означимо најдужи пут са e_1e_2\dotsc e_k, а чвор у коме он почиње са X. Нека се пут завршава у чвору G који је различит од X. Ако смо већ прошли кроз G, рецимо n пута, то значи да смо прошли 2n ивица. Пошто је G паран, онда ћемо морати да, улазећи у њега преко e_k, пронађемо још једну ивицу, e_{k+1}, различиту од свих претходних, којом ћемо изаћи из G. Међутим, пут e_1e_2\dotsc e_ke_{k+1} је дужи од e_1e_2\dotsc e_k, што је контрадикција. Дакле, најдужи пут e_1e_2\dotsc e_k је затворен.

Докажимо да најдужи пут прелази преко сваке ивице. Претпоставимо супротно, да он не прелази преко ивице f. Пошто је граф повезан, ивица f се може тако изабрати да води у неки од чворова кроз које пролази пут e_1e_2\dotsc e_k, рецимо X. Нека је чвор X повезан још и са ивицама e_1 и e_2 (у супротном је степен X једнак два, па бисмо имали повезан пут који улази кроз X, а не излази из њега, што је контрадикција). Тада је пут fe_2e_3\dotsc e_ke_1 дужи од најдужег пута e_1e_2e_3\dotsc e_k, што је контрадикција. Дакле, тај пут прелази преко свих ивица, и граф се може обићи.

За случај два непарна чвора повезивањем та два чвора замишљеном ивицом f добијамо случај нула непарних чворова, тј. такав граф се може обићи путем e_1e_2\dotsc e_kf. Сада уклањањем ивице f добијамо пут e_1e_2\dotsc e_k, којим се пролази кроз граф почевши од једног непарног чвора и завршавајући са другим непарним чвором. \Box

Последња теорема пружа још строжији услов који повезани граф мора да испуни да би могао да се обиђе прелазећи преко сваке ивице тачно једном: он мора да има тачно нула или две непарне тачне. Пошто граф проблема калињинградских мостова има 4 непарне тачке, њега није могуће обићи на такав начин. \blacksquare

Пример 1. Могу ли следећи графови да се обиђу прелазећи преко сваке ивице тачно једном? У случају да је то могуће, одредити да ли је граф затворен. (Савет: поред сваког чвора запишите његов степен и примените теорему 1.)

$ \begin{figure}[!htp] \entrymodifiers={=<1mm>} \[\begin{array}{ccc} \xymatrix{% \circ\ar@(u,u)@{-}[rr]\ar@{-}[dd]\ar@{-}[rr]\ar@{-}'[dr][ddrr] &&\circ\ar@{-}[dd]\ar@{-}'[dl][ddll]\ar@(r,r)@{-}[dd] \\ &\circ\\ \circ\ar@(l,l)@{-}[uu]\ar@{-}[rr] &&\circ\ar@(d,d)@{-}[ll] }&\text{\hspace{2cm}}&\xymatrix{% \circ\ar@(u,u)@{-}[rr]\ar@{-}'[d][dd]\ar@{-}'[r][rr] &\circ\ar@{-}'[dr]'[dd]'[dl][] &\circ\ar@{-}'[d][dd]\ar@(r,r)@{-}[dd] \\ \circ&&\circ \\ \circ\ar@(l,l)@{-}[uu]\ar@{-}'[r][rr] &\circ &\circ\ar@(d,d)@{-}[ll]} \end{array}\] \vskip2cm \[\begin{array}{ccc} \xymatrix{% \ar@{-}'[rr]'[rrrr]'[rrrrdd]'[rrrrdddd]'[rrdddd]'[dddd]'[dd][] \circ&&\ar@{-}'[dr]'[ddrr]'[dddr]'[dddd]'[dddl]'[ddll]'[dl][]\circ&&\circ\\ &\ar@{-}[ddrr]\ar@{-}[dd]\circ\ar@{-}[rr]&&\circ\ar@{-}[dd]\\ \circ&&&&\circ\\ &\ar@{-}[rr]\circ&&\circ\\ \circ&&\circ&&\circ }&\text{\hspace{2cm}}&\xymatrix{% & &\ar@(l,u)@{-}[ddll]\circ\ar@{-}'[d]'[dd]'[ddd][dddd]\ar@(r,u)@{-}[ddrr]& & \\ & &\ar@/_/@{-}[dl]\circ\ar@/^/@{-}[dr]& & \\ \circ\ar@{-}'[r]'[rr]'[rrr][rrrr]&\circ&\circ&\circ&\circ\\ & &\ar@/_/@{-}[ur]\circ\ar@/^/@{-}[ul]& & \\ & &\ar@(l,d)@{-}[uull]\circ\ar@(r,d)@{-}[uurr]& & \\ } \end{array}\] \end{figure} $