Sedam mostova Kenigsberga

Jedan od prvih problema koji je (negativno) rešen primenom teorije grafova je čuveni „Sedam mostova Kenigsberga“ (eng. The Seven Bridges of Königsberg).

Problem je analizirao švajcarski matematičar Leonhard Euler u 18. veku, i zaključci do kojih je došao predstavljaju osnovu i začetak teorije grafova. Kroz grad Königsberg protiče reka Pregel koja deli grad na četiri celine međusobno povezane sa sedam mostova. Problem se sastoji u tome kako pronaći putanju kroz grad tako da se prođe preko svakog mosta jednom i samo jednom. Slikovito opisano, to bilo kao kada biste srušili most za sobom nakon što ga pređete.

Na slikama je prikazana mapa grada sa lokacijama mostova i Eulerova interpretacija tog problema. Euler je posmatrao ovaj problem na drugačiji način. Pošto je njegov zadatak bio da pronađe putanje, svaki deo grada je posmatrao kao celinu, odnosno kao čvor, dok je mostove posmatrao kao veze između čvorova. Na taj način je predstavio problem u vidu graf strukture. Zatim je analizirao sve moguće putanje između čvorova tako da se poseti svaki čvor a da se pri tome pređe preko svakog mosta samo jednom. Odgovor je da tako nešto nije moguće, evo i objašnjenja.

Hajde da se upoznamo sa još jednim pojmom vezanim za grafove, a to je stepen čvora. Stepen čvora predstavlja broj veza koje taj čvor formira sa svim susednim. Analizom svih mogućih putanja Euler je zaključio da čvor koji nije polazana ili završna tačka putanje mora imati stepen koji je paran broj. Sledeći to pravilo u zavisnosti od odabira početne i krajnje tačke možemo zaključiti koja je veza „suvišna“ da bi problem bio rešiv.

Izvor: datascience.rs