i
i
“Arnus-O-treh-hisah” — 2010/6/1 — 9:17 — page 1 — #1 i
i
i
i
i
i
List za mlade matematike, fizike, astronome in računalnikarje
ISSN 0351-6652
Letnik 15 (1987/1988)
Številka 4
Strani 242–243
Olga Arnuš:
O TREH HIŠAH IN TREH VODNJAKIH
Ključne besede: matematika, diskretna matemtika, graf.
Elektronska verzija: http://www.presek.si/15/902-Arnus.pdf
c© 1988 Društvo matematikov, fizikov in astronomov Slovenije
c© 2010 DMFA – založništvo
Vse pravice pridržane. Razmnoževanje ali reproduciranje celote ali
posameznih delov brez poprejšnjega dovoljenja založnika ni dovo-
ljeno.
ITI"-'-/",,-'1/",,-,1CI" I"", -
o TREH HISAH IN TREH VODNJAKIH
Prebivalci treh hiš so imeli na voljo tr i vodnjake . Ker so bili le-ti z vodo razli-
čno osk rbovani , so se lastniki hiš odločili, da bodo od vsake hiše speljali pot k
vsakemu vodnjaku. To bi rad i naredili tako, da se poti ne b i k rižale. Ali je to
mogoče?
Matematični model za predstavitev te naloge je graf. Preprosto povedano:
graf je določen, če poznamo neko množico (nje ne elemente bomo ime nova li
kar točke) in če so nekateri pari teh točk v določenem od no su (takemu odno-
su pravimo povezava) . Graf lahko ponazorimo tako , da točke kak orkoli nariše-
mo v ravnini, povezavo pa ponazarja kar črta med točkama (ni nujno dalj ica) .
ln še to: tu nas bodo zanimali le graf i, pri katerih ni usmerjen ih povezav (ni
važno, katera točka je začetna in katera končna) . Graf bo mo imenovali
povezan, če je mogoče iz poljubne točke prit i po povezavah v katerokoli
drugo točko.
Našemu uvodnemu problemu ust reza naslednji graf : H, a..----_" V,
Narišemo ga lahko tudi takole : H, H2 V2
V, V2
H3 V3
H2 H3
V3
V obeh primerih vidimo, da se nekatere povezave sekalo . Zanima nas, ali je ta
graf mogoče narisati tudi tako, da se povezave ne bi sekale , kar bi bila rešitev
našega začetnega problema . To lahko na primer naredimo pri naslednjem
grafu:
242
Grafom, ki jih lahko narišemo v ravnini tako, da se noben par povezav ne seka,
pravimo ravninski ali planarni grafi. Oglejmo si neko lastnost teh grafov.
Planarni graf razdeli ravnino na p polj. Iz enega polja lahko pridemo v dru-
go le, če sekamo povezavo ali gremo skozi točko grafa. Naj ima planarni graf
n točk in r povezav. Nekaj zgledov:
a) b)
~n 0 3 L n=3
n=4
r =3 r=2 r=6
p=2 p=1 p=4
Eden najstarejših izrekov iz teorije grafov je Eulerjev izrek za planarne
grafe. Tole pravi:
Če ima povezan planarni graf n točk, r povezav in p polj, potem je
n +p = r + 2.
Zgornji primeri izrek potrjujejo. Dokaz pa zahteva več znanja iz teorije
grafov, zato ga bomo opustili. Bralci ga lahko najdejo v knjigi D. Cvetkoviča
Teorija grafova i njene primene, nekaj predznanja pa bodo dobili v knjižici
Najnujnejše o grafih, ki sta jo napisala D. Bajc in T. Pisanski in je izšla v Pre-
sekovi knjižnici leta 1985.
Vrnimo se k našemu uvodnemu grafu, kjer smo povezovali hišice z
vodnjaki, in si ga oglejmo. Tu je n = 6 in r = 9. Iz obeh slik se da ugotoviti,
da nobena trojica točk ni povezana tako, da bi oblikovala trikotnik. Če bi
lahko ta graf narisali tako, da se povezave ne bi sekale, bi bilo vsako polje ome-
jeno z najmanj štirimi povezavami, vsaka povezava pa meji na dve polji. Zato
je r;;;" 4pl2 ali p :o:;;; 912. Eulerjev izrek pa nam za p da vrednost p = r + 2 - n =
= 5. Ker je naš graf povezan, nam protislovje pove, da graf ni planaren. Pre-
bivalci treh hišic se ne bodo mogli izogniti križanju poti, zato bodo morali
paziti na dobre medsosedske odnose.
S planarnimi grafi se v teoriji grafov večkrat srečamo. Uporaba pa sega
tudi na druga področja. Srečujejo jih pri projektiranju cestnih omrežij. če
izključujemo možnost nadvozov, v tehniki integriranih vezij, pri izvedbi ne-
katerih mehanizmov v strojništvu in še kje.
ln še naloga za bralce. Na podoben način kot zgoraj je mogoče dokazati,
da graf na sliki ni planaren.
Olga Arnuš
243