U istoriji matematike posebno interesantno mesto zauzimaju problemi iz svakodnevnog života koji su privukli paznju velikih matematičara. Rešavajući ih, oni su došli do rezultata koji su predstavljali začetke novih matematičkih disciplina. U ovom prilogu biće izložena priča koju su pokrenuli znatiželjni stanovnici Kenigsberga pre 250 godina u vezi s prelaskom preko svih mostova na reci koja protiče kroz ovaj grad. Problem je rešio jedan od najvećih matematičara svih vremena, Leonard Ojler, i to se smatra početkom teorije grafova.
Prof. dr Miodrag Petković
Preko reke Pregel što protiče kroz grad Kenigsberg (nekada u Pruskoj, danas pod imenom Kalinjingrad u Rusiji), koju dva ostrva dele na dva rukavca, sedam mostova povezuju ostrva i obale reke. Stanovnici su dugo su bili zaokupljeni sledećim pitanjem:Da li je moguće preći sve mostove ne prelazeći ni preko jednog dva ili više puta? Uprkos naporima, nijedan od znatiželjnika nije ostvario takvu šetnju, niti je pokazao da je to izvodljivo.
Sl. 1 Stari Kenigsberg i njegovih sedam mostova (skica iz 1651)
Problem je rešio čuveni švajcarski matematičar Leonard Ojler (Leonhard Euler, 1707-1783) godine 1736. Taj dokaz nepostojanja željenog puta obično se uzima kao početak nove matematičke discipline – teorije grafova. Danas je ona veoma korisna ne samo u raznim matematičkim granama, već i u drugim naučnim disciplinama kao što su kompjuterske i tehničke nauke, hemija, biologija, operaciona istraživanja, transport i logistika, društvene nauke itd.
Pre nego što prikažemo rešenje, vredi reći nekoliko reči o Leonardu Ojlerukoga s Njutnom, Gausom i Arhimedom svrstavaju u najveće matematičare svih vremena. Prema obimu objavljenih radova, on je najproduktivniji. Bibliografska lista, uključujući i posmrtno objavljene radove, sadrzi 886 jedinica što bi moglo da ispuni 80 knjiga velikog formata ili oko 80.000 stranica. U svojoj 59. Godini on je ostao skoro slep nakon neke bolesti. Zahvaljujući neverovatnoj memoriji, poslednjih 17 godina života mogao je da nastavi sa radom u optici, algebri i proučavanju lunarnog kretanja napisavši skoro polovinu svih svojih radova. Bavio se maltene svim oblastima matematike, a povremeno i problemima rekreativne matematike. Neki od tih izleta doveli su do nastanka novih metoda, čak i novih grana matematike, kao što je, na primer, teorija grafova i topologija.
Za one koji nisu slušali kurseve iz teorije grafova dajemo pregled najosnovnijih pojmova, jer se tako rešenje može lako pratiti.U teoriji grafova planarni graf se definiše kao skup tačaka u ravni od kojih su neke povezane linijama. Tačke se zovu čvorovi ili temena grafa (npr. tačke A,B,C,D,E na slici 2a), a linije se nazicajugrane, spojnice ili ivice. Za granu koja povezuje dva susedna čvora kaže se da je incidentna za oba. A za graf koji nema petlje (linije što polaze i završavaju u istom čvoru, npr. p na slici 2b) i nemaju dve ili više višestrukih grana koje povezuju isti par čvorova, kaže se da je prost graf (slika 2a), u protivnom je multigraf (slika 2b).
Stepenčvora je broj grana koje su s njim incidentne, računajući petlje i višestruke grane. Tako se stepen čvora T označava sa deg(T).Na primer, stepeni čvorova na slici 2a su deg(A) = 2, deg(B) = 4, deg(C) = 2, deg(D) = 3, deg(E) = 1. Čvor grafa koji ima neparan (paran) stepen zove se neparan (paran) čvor.
Sl. 2 Različiti tipovi grafova:
a) prost graf b) mulrigraf
Vratimo se problemu kenigsberških mostova i napomenimo da je on ekvivalentan sledećem problemu (videti sliku 4, radi ilustracije):Mreža (graf) u ravni dobijena je spajanjem datog skupa tačaka pomoću linija. Pod kojim uslovima se ova mreža može nacrtati u jednom potezu (ne podižući olovku sa papira) i ne prelazeći po već povučenim linijama?Crtanje grafa u jednom potezu obično se zove trasiranje grafa.
Sl. 3 Kenigsberški mostovi
Sl. 4 Graf kenigsberških mostova
Rešenje problema kenigsberških mostova i crtanje ravanske mreže (grafa) u „jednom potezu” (tj. bez podizanja olovke sa papira) zasnovano je na sledećem tvrđenju:Ojlerova teorema: Graf se može trasirati bez podizanja olovke, prelazeći preko svake ivice tačno jedanput, ako i samo ako graf ima dva ili nijedan čvor neparnog stepena.
Graf koji se može trasirari pod navedenim uslovima zove se Ojlerov graf, a odgovarajući put Ojlerov put. Prema tome:Ojlerov put postoji ako i samo ako postoji 0 ili 2 neparna čvora grafa. U svim ostalim slučajevima, tj. kad je broj čvorova neparnog stepena različit od 0 i 2, graf se ne može nacrtati.
Ako su svi čvorovi grafa parnog stepena (0 neparnih čvorova), on se može nacrtati i to polazeći iz bilo kojeg čvora grafa, a završavajući u istom čvoru. U slučaju da postoje dva čvora neparnog stepena, graf se može nacrtati polazeći od jednog od tih čvorova, a završavajući u drugom.
Graf (mreža) dat na slici 5 ima 8 neparnih čvorova i, prema tome, ne može se trasirati bez podizanja olovke. Slika 4 prikazuje „kenigsberški multigraf”, gde su ostrva i obale predstavljeni čvorovima, a mostovi granama. On ima 4 čvora neparnog stepena i, na osnovu Ojlerove teoreme, to nije Ojlerov graf. Prema tome, željeni put preko 7 kenigsberških mostova ne može se realizovati.
Sl. 5 Crtanje ravanske mreže
Kao dodatni zadatak u vezi s primenom Ojlerove teoreme, dajemo sledeći problem čiji je autor on sam, a koji je sličan prelazu preko kenigsberških mostova ali znatno komplikovaniji; ovde se zahteva prelazak preko 15 mostova:Četiri ostrva A, B, C i D povezana su pomoću 15 mostova sa obalama reke i između sebe, kao što je prikazano na slici 6. Da li je moguće obići sve mostove prelazeći preko svakog mosta jednom i samo jednom?
Sl. 6 Ojlerov zadatak o prelazu preko
15 mostova
Za čitaoce koji nemaju vremena (ili strpljenja) za rešavanje ovog zadatka, u nastavku dajemo rešenje. Da bismo rešili problem, predstavimo četiri ostrva A, B, C, D i obale E i F pomoću čvorova grafa, a mostove granama (označenih malim slovima), videti sliku 6. Kao što se vidi sa slike 7, graf ima dva čvora neparnog stepena (deg(D) = 3, deg(E) = 5).S obzirom na gore formulisnu Ojlerovu teoremu postoji zahtevani put preko svih 15 mostova koji polazi od čvora D i završava u čvoru E, ili obratno.
Sl. 7 Graf Ojlerovih 15 mostova
Prelaz se može izvršiti, na primer, u poretku (rešenje nije jednoznačno)
E a F b B c F d A e F f C g A h C i D k A m E n A p B q E l D
ili u obratnom poretku polazeći od tačke D i završavajući u E.
Zadatak za radoznale i vrlo uporne: Odrediti sva rešenja!
