petak, 21. prosinca 2012.

Pripreme za algoritme(12)

Uvod u grafove

Poznati matematičar Leonhard Euler se odlučio zabaviti poznatim problemom “Sedam mostova Köningsberga”. Köningsberg, danas poznat pod nazivom Kaliningrad je ruska enklava na Baltiku smještena između Poljske i Litve (adminsirativni je dio Rusije, ali zemljopisno je smješten između Poljske i Litve). Sam grad je u prošlosti imao sedam mostova koji su povezivali dva otoka unutar grada s ostatkom grada. Postavljeno je pitanje – Je li moguće prijeći preko svakog od mostova samo jednom i vratiti se na početnu točku?
Kao što vidimo, četiri dijela grada (sjeverni, južni i dva otoka) bila su međusobno povezana putem sedam mostova. Manji otok s po dva je mosta povezan sa sjevernim i s južnim dijelom grada. Veći otok s po jednim je mostom povezan sa sjevernim s južnim dijelom grada, a postojao je i jedan most koji je povezivao dva otoka.

Euler je, naravno, dao konačan odgovor na ovo pitanje. Dok je proučavao problem, Euler je došao na genijalnu ideju da različite dijelove grada označi vrhovima, a mostove među njima bridovima. Na taj je način konstruirao graf s četiri vrha i sedam bridova koji je odgovarao stvarnom problemu.

Na taj način Euler je začetnik teorije grafova koja se danas proučava u okvirima kombinatorike, a koristi se za modeliranje mnogih problema. Put koji prolazi kroz svaku spojnicu (brid) samo jednom zove se Eulerova šetnja.
I da, naravno, Euler je riješio problem. Zaključio je da takav put ne postoji. Danas znamo da se zatvorena Eulerova šetnja može naći samo u grafovima u kojima je stupanj svakog vrha paran (stupanj nekog čvora je jednak broju linija koje taj čvor dotiču). Prema tome se grafovi u kojima su svi vrhovi parnog stupnja nazivaju Eulerovim.

Osnovna terminologija

Graf je skup čvorova koji su povezani skupom bridova.
Put je bilo koji niz čvorova u kojem između svaka dva uzastopna čvora postoji veza.
Ciklus je put u kojem se prvi i posljednji čvor poklapaju.
Obilazak grafa je prolaz kroz sve točke grafa bez ponovnog posjećivanja prethodno posjećenih točaka.
U usmjerenom grafu svakom je bridu dodijeljen smjer.
Graf s n čvorova ima najmanje n-1 brid.


Toliko za uvod, a u sljedećoj lekciji krećemo na malo kompilicranije.


Nema komentara:

Objavi komentar