Gotovi Seminarski Diplomski Maturalni Master ili Magistarski
Grafovi - Verzija za štampu

+- Gotovi Seminarski Diplomski Maturalni Master ili Magistarski (https://www.maturskiradovi.net/forum)
+-- Forum: Obrazovanje (/Forum-obrazovanje)
+--- Forum: Društvene nauke (/Forum-dru%C5%A1tvene-nauke)
+---- Forum: Matematika (/Forum-matematika)
+---- Tema: Grafovi (/Thread-grafovi)


Grafovi - Dzemala - 14-08-2011 12:19 PM

Maturski, Seminarski , Maturalni i diplomski radovi iz ekonomije: menadžment, marketing, finansija, elektronskog poslovanja, internet tehnologija, biznis planovi, makroekonomija, mikroekonomija, preduzetništvo, upravljanje ljudskim resursima, carine i porezi.




Temelje teoriji grafova udario je dobro poznati švajcarski matematičar Leon-hard Euler (1707.–1783.) koji je 1736. godine rešio problem Konigsberških mostova. Naime, stari pruski grad Konigsberg, današnji Kalinjingrad u Rusiji, smešten je na obalama reke Pregel.Deo grada nalazi se na dve ade,koje su povezane s kopnom I medusobno sa sedam mostova (vidi sliku 1.1.).

Gradani Konigsberga voleli su šetati po mostovima, no ljutilo ih je što niko nije mogao pronaći način da prošeta gradom tako da svih sedam mostova prede samo jednom i zatim se vrati kući. Za pomoć su se obratili Euleru koji je u to vreme radio u Petrogradu.Euler je vrlo brzo pokazao da je takva šetnja nemoguća.Pretpostavimo da je takva šetnja moguća.Tada ona završava u komponentama kopna A, B, C ili D, eventualno tamo gde je započela. Primetimo da svaka komponenta kopna u kojoj šetnja nije započela i nije završila mora biti spojena s parnim brojem mostova, jer za svaki most preko kojeg se dolazi na tu komponentu mora postojati i most preko kojeg se odlazi s te komponente. Zato svaka komponenta koja je spojena s neparnim brojem mostova mora biti ili početak ili kraj šetnje. No u slučaju Konigsberga svaka komponenta A, B, C i D ima neparan broj mostova s kojima je povezana, a kako najviše dve komponente mogu biti početak, odnosno kraj šetnje, zaključujemo da takva šetnja nije moguća.

Ako komponente A, B, C i D prikažemo kao tačke ili vrhove, a mostove koji ih spajaju kao spojnice, dobijamo pojednostavljenu šemu vrhova i njihovih spojnica, tj. graf.
Problem šetanja po Konigsberškim mostovima ekvivalentan je problem obilaska ovog grafa tako da krenemo iz jednog vrha i sve bridove predemo tačno jedanput...