Evo skice koja ilustruje kako su ti mostovi izgledali:
- mostovi.png (76.85 KiB) Pogledano 2828 puta
Imate li ideju kako bi to moglo da se ostvari? I da li uopšte može?
Index stranica ‹ RAZNO ‹ ZANIMLJIVI ZADACI
Prelazak mostova
Pregled za štampanje • Pregled za štampanje svih postova u temi • 7 Posta
• Stranica 1 od 1
Prelazak mostova
od Milovan » Utorak, 10. Decembar 2013, 23:33
Nekad je u jednom evropskom gradu među stanovnicima toga mesta bio aktuelan jedan nesvakidašnji problem... Naime, stanovnici tog mesta želeli su da pređu svih [inlmath]7[/inlmath] mostova koji su tamo postojali, ali tako da ni preko jednog od mostova ne pređu dvaput...
Evo skice koja ilustruje kako su ti mostovi izgledali:
Imate li ideju kako bi to moglo da se ostvari? I da li uopšte može?
Evo skice koja ilustruje kako su ti mostovi izgledali:
Imate li ideju kako bi to moglo da se ostvari? I da li uopšte može?
Re: Prelazak mostova
od Daniel » Sreda, 11. Decembar 2013, 08:37
To mu dođe isto kao i ova poznata mozgalica, u kojoj je potrebno jednim potezom, znači, bez podizanja olovke s papira, povući takvu krivu liniju koja će kroz svaku od obeleženih linija na crtežu proći tačno jednom:
(Dao sam sebi slobodu da temu dopunim i ovim zadatkom, budući da odgovor na bilo koji od ta dva zadatka automaCki predstavlja i odgovor na onaj drugi.
)
- linije.png (315 Bajta) Pogledano 2819 puta
(Dao sam sebi slobodu da temu dopunim i ovim zadatkom, budući da odgovor na bilo koji od ta dva zadatka automaCki predstavlja i odgovor na onaj drugi.
)I do not fear death. I had been dead for billions and billions of years before I was born, and had not suffered the slightest inconvenience from it. – Mark Twain
Re: Prelazak mostova
od ubavic » Sreda, 11. Decembar 2013, 22:15
Koliko se sećam Euler je bio dugo zaokupljen ovim problemom. Inače dva mosta se i dalje nalaze u jednom ruskom gradu. Zanimljiv problem, vredi pokušati 
.
.Re: Prelazak mostova
od Daniel » Nedelja, 17. Maj 2015, 01:38
Da nastavimo ovu zanimljivu temu započetu pre godinu i po.
Problem prelazaka mostova rešio je Ojler, zbog čega se eventualni put kojim treba ići preko mostova kako bi se preko svakog prešlo tačno jedanput – naziva Ojlerov put. Ojler je raspored kopna i mostova predstavio grafički, u vidu današnjih grafova, čime je, zapravo, postavio osnove današnje teorije grafova.
Svaki deo kopna na slici numerišimo brojem od [inlmath]1[/inlmath] do [inlmath]4[/inlmath], a mostove obeležimo slovima od [inlmath]a[/inlmath] do [inlmath]g[/inlmath]:
Ojler je takvu konfiguraciju terena predstavio u vidu grafa tako što je svaki deo kopna predstavio kao jedan čvor grafa, dok je mostove predstavio kao grane (veze) između čvorova tog grafa, po sistemu – koliko mostova postoji između dva dela kopna, toliko grana postoji između odgovarajućih čvorova grafa. Primera radi – između delova kopna [inlmath]1[/inlmath] i [inlmath]2[/inlmath] postoje dva mosta ([inlmath]a[/inlmath] i [inlmath]b[/inlmath]), prema tome, čvorovi [inlmath]1[/inlmath] i [inlmath]2[/inlmath] grafa povezani su dvema granama, [inlmath]a[/inlmath] i [inlmath]b[/inlmath]; nasuprot tome, između delova kopna [inlmath]1[/inlmath] i [inlmath]3[/inlmath] ne postoji direktan most, pa tako ni između čvorova grafa [inlmath]1[/inlmath] i [inlmath]3[/inlmath] ne postoji direktna grana.
Ojler je pokazao da je potreban i dovoljan uslov za postojanje Ojlerovog puta taj, da ili svi čvorovi grafa imaju paran stepen (stepen čvora je broj grana koje se u njemu stiču), ili da tačno dva čvora imaju neparan stepen a svi ostali paran stepen. Ovo sledi iz činjenice da, koliko smo puta došli u neki čvor, toliko puta iz tog čvora moramo i otići (zbog čega broj prilaza tom čvoru mora biti paran – prilazi za dolaske i prilazi za odlaske), što, eventualno ne mora da važi za dva čvora grafa – čvor iz kojeg smo na početku krenuli i čvor u koji na kraju stižemo. Zbog toga je dopušteno da, eventualno, dva (ali, ne jedan, već tačno dva) čvora imaju neparan stepen.
Ostalo je još da uočimo stepene čvorova ovog grafa i da, samim tim, odgovorimo na pitanje da li u posmatranom slučaju Ojlerov put postoji, tj. da li je moguće ostvariti maršrutu koja se traži, a to prepuštam vama.
Takođe, ko želi, može pokušati da nacrta graf i za ovaj drugi problem, koji sam postavio u pretprošlom postu.
Inače, u pitanju je grad Kenigzberg (zbog čega je ovaj problem poznat kao problem kenigzberških mostova. Današnji naziv tog grada je Kaliningrad, a možete ga videti i na Google mapama:
Pozivam sve kojima je ova problematika zanimljiva, da mi se u utorak, 19. maja, pridruže na predavanju prof. dr Vojislava Petrovića u okviru ovogodišnjeg Maja meseca matematike: „Problem kenigzberških mostova – početak teorije grafova“ u Kolarcu, s početkom u 18 časova.
Problem prelazaka mostova rešio je Ojler, zbog čega se eventualni put kojim treba ići preko mostova kako bi se preko svakog prešlo tačno jedanput – naziva Ojlerov put. Ojler je raspored kopna i mostova predstavio grafički, u vidu današnjih grafova, čime je, zapravo, postavio osnove današnje teorije grafova.
Svaki deo kopna na slici numerišimo brojem od [inlmath]1[/inlmath] do [inlmath]4[/inlmath], a mostove obeležimo slovima od [inlmath]a[/inlmath] do [inlmath]g[/inlmath]:
- mostovi.png (3.29 KiB) Pogledano 2460 puta
Ojler je takvu konfiguraciju terena predstavio u vidu grafa tako što je svaki deo kopna predstavio kao jedan čvor grafa, dok je mostove predstavio kao grane (veze) između čvorova tog grafa, po sistemu – koliko mostova postoji između dva dela kopna, toliko grana postoji između odgovarajućih čvorova grafa. Primera radi – između delova kopna [inlmath]1[/inlmath] i [inlmath]2[/inlmath] postoje dva mosta ([inlmath]a[/inlmath] i [inlmath]b[/inlmath]), prema tome, čvorovi [inlmath]1[/inlmath] i [inlmath]2[/inlmath] grafa povezani su dvema granama, [inlmath]a[/inlmath] i [inlmath]b[/inlmath]; nasuprot tome, između delova kopna [inlmath]1[/inlmath] i [inlmath]3[/inlmath] ne postoji direktan most, pa tako ni između čvorova grafa [inlmath]1[/inlmath] i [inlmath]3[/inlmath] ne postoji direktna grana.
- graf.png (1.67 KiB) Pogledano 2460 puta
Ojler je pokazao da je potreban i dovoljan uslov za postojanje Ojlerovog puta taj, da ili svi čvorovi grafa imaju paran stepen (stepen čvora je broj grana koje se u njemu stiču), ili da tačno dva čvora imaju neparan stepen a svi ostali paran stepen. Ovo sledi iz činjenice da, koliko smo puta došli u neki čvor, toliko puta iz tog čvora moramo i otići (zbog čega broj prilaza tom čvoru mora biti paran – prilazi za dolaske i prilazi za odlaske), što, eventualno ne mora da važi za dva čvora grafa – čvor iz kojeg smo na početku krenuli i čvor u koji na kraju stižemo. Zbog toga je dopušteno da, eventualno, dva (ali, ne jedan, već tačno dva) čvora imaju neparan stepen.
Ostalo je još da uočimo stepene čvorova ovog grafa i da, samim tim, odgovorimo na pitanje da li u posmatranom slučaju Ojlerov put postoji, tj. da li je moguće ostvariti maršrutu koja se traži, a to prepuštam vama.
Takođe, ko želi, može pokušati da nacrta graf i za ovaj drugi problem, koji sam postavio u pretprošlom postu.
Inače, u pitanju je grad Kenigzberg (zbog čega je ovaj problem poznat kao problem kenigzberških mostova. Današnji naziv tog grada je Kaliningrad, a možete ga videti i na Google mapama:
Pozivam sve kojima je ova problematika zanimljiva, da mi se u utorak, 19. maja, pridruže na predavanju prof. dr Vojislava Petrovića u okviru ovogodišnjeg Maja meseca matematike: „Problem kenigzberških mostova – početak teorije grafova“ u Kolarcu, s početkom u 18 časova.
I do not fear death. I had been dead for billions and billions of years before I was born, and had not suffered the slightest inconvenience from it. – Mark Twain
Re: Prelazak mostova
od ubavic » Nedelja, 17. Maj 2015, 18:16
Kreirali smo i facebook event: Problem kenigzberških mostova – početak teorije grafova. Pozivamo sve zainteresovane da dođu. Vidimo se!
Re: Prelazak mostova
od Daniel » Sreda, 20. Maj 2015, 11:14
Evo još jednog pristupa ovom problemu, o kojem je bilo reči na pomenutom jučerašnjem (inače, izuzetno zanimljivom) predavanju.
Pošto ima [inlmath]7[/inlmath] mostova, a svaki od mostova treba preći jednom i samo jednom, jasno je i da mora biti [inlmath]7[/inlmath] prelazaka mostova. Samim tim, moramo imati za jedan više broj boravaka na svakom od delova kopna razdvojenih rekom, znači, [inlmath]8[/inlmath]. Maršrutu možemo obeležiti tako što ćemo hronološki pisati oznake delova kopna (već smo ih označili sa [inlmath]1,2,3,4[/inlmath]) na kojima smo tokom maršrute boravili. Npr. [inlmath]2-4-\cdots-1[/inlmath], s tim da ih mora u tom nizu biti tačno [inlmath]8[/inlmath]. Jasno je da u tom nizu dva susedna člana ne mogu biti isto kopno, budući da svaki most razdvaja dva različita dela kopna.
Zatim razmišljamo: pošto je deo kopna br. [inlmath]2[/inlmath] povezan sa [inlmath]5[/inlmath] mostova s ostalim delovima kopna, na kopnu br. [inlmath]2[/inlmath] moramo biti najmanje [inlmath]3[/inlmath] puta. Ako bismo bili jednom, to bi značilo prelazak najviše dva mosta koji ga spajaju s ostalim kopnima (jednom u dolasku, jednom u odlasku). Ako bismo bili dvaput, to bi značilo prelazak najviše [inlmath]4[/inlmath] mosta (dvaput u dolascima, dvaput u odlascima). Znači, moramo biti triput.
Slično, za delove kopna [inlmath]1,3,4[/inlmath] možemo zaključiti da na svakom od njih moramo biti najmanje dvaput, zbog toga što je svaki od tih delova kopna s ostatkom povezan s [inlmath]3[/inlmath] mosta. I onda saberemo:
Kopno br. [inlmath]1[/inlmath] – najmanje [inlmath]2[/inlmath] puta;
Kopno br. [inlmath]2[/inlmath] – najmanje [inlmath]3[/inlmath] puta;
Kopno br. [inlmath]3[/inlmath] – najmanje [inlmath]2[/inlmath] puta;
Kopno br. [inlmath]4[/inlmath] – najmanje [inlmath]2[/inlmath] puta;
Kad to saberemo, dolazimo do toga da u malopre pomenutom nizu koji hronološki predstavlja boravke na delovima kopna moramo imati najmanje [inlmath]2+3+2+2=9[/inlmath] članova, što je u kontradikciji s prethodnim zaključkom da u tom nizu mora biti [inlmath]8[/inlmath] članova, iz čega zaključujemo da nije moguće preko svakog mosta preći jednom i samo jednom.
I, još dva zanimljiva podatka.
Na ostrvu (obleženom sa [inlmath]2[/inlmath]) nalazi se grob Imanuela Kanta, čuvenog filozofa koji je i rođen u tom gradu i u njemu živeo.
Od [inlmath]7[/inlmath] mostova opisanih u ovom problemu danas je preostalo samo [inlmath]5[/inlmath], kao što se i vidi na Google mapama (dva mosta su uništena u savezničkom bombardovanju). S ovih sadašnjih [inlmath]5[/inlmath] mostova bilo bi moguće ostvariti traženi zadatak, budući da sada imamo takav graf u kojem dva čvora imaju neparan stepen (čvorovi [inlmath]2[/inlmath] i [inlmath]4[/inlmath] imaju stepen [inlmath]3[/inlmath]), dok preostali čvorivi ([inlmath]1[/inlmath] i [inlmath]3[/inlmath]) imaju paran stepen – stepen [inlmath]2[/inlmath]. Naravno, uslov za ostvarenje tražene rute bio bi taj, da krenemo iz nekog od čvorova s neparnim stepenom...
Pošto ima [inlmath]7[/inlmath] mostova, a svaki od mostova treba preći jednom i samo jednom, jasno je i da mora biti [inlmath]7[/inlmath] prelazaka mostova. Samim tim, moramo imati za jedan više broj boravaka na svakom od delova kopna razdvojenih rekom, znači, [inlmath]8[/inlmath]. Maršrutu možemo obeležiti tako što ćemo hronološki pisati oznake delova kopna (već smo ih označili sa [inlmath]1,2,3,4[/inlmath]) na kojima smo tokom maršrute boravili. Npr. [inlmath]2-4-\cdots-1[/inlmath], s tim da ih mora u tom nizu biti tačno [inlmath]8[/inlmath]. Jasno je da u tom nizu dva susedna člana ne mogu biti isto kopno, budući da svaki most razdvaja dva različita dela kopna.
Zatim razmišljamo: pošto je deo kopna br. [inlmath]2[/inlmath] povezan sa [inlmath]5[/inlmath] mostova s ostalim delovima kopna, na kopnu br. [inlmath]2[/inlmath] moramo biti najmanje [inlmath]3[/inlmath] puta. Ako bismo bili jednom, to bi značilo prelazak najviše dva mosta koji ga spajaju s ostalim kopnima (jednom u dolasku, jednom u odlasku). Ako bismo bili dvaput, to bi značilo prelazak najviše [inlmath]4[/inlmath] mosta (dvaput u dolascima, dvaput u odlascima). Znači, moramo biti triput.
Slično, za delove kopna [inlmath]1,3,4[/inlmath] možemo zaključiti da na svakom od njih moramo biti najmanje dvaput, zbog toga što je svaki od tih delova kopna s ostatkom povezan s [inlmath]3[/inlmath] mosta. I onda saberemo:
Kopno br. [inlmath]1[/inlmath] – najmanje [inlmath]2[/inlmath] puta;
Kopno br. [inlmath]2[/inlmath] – najmanje [inlmath]3[/inlmath] puta;
Kopno br. [inlmath]3[/inlmath] – najmanje [inlmath]2[/inlmath] puta;
Kopno br. [inlmath]4[/inlmath] – najmanje [inlmath]2[/inlmath] puta;
Kad to saberemo, dolazimo do toga da u malopre pomenutom nizu koji hronološki predstavlja boravke na delovima kopna moramo imati najmanje [inlmath]2+3+2+2=9[/inlmath] članova, što je u kontradikciji s prethodnim zaključkom da u tom nizu mora biti [inlmath]8[/inlmath] članova, iz čega zaključujemo da nije moguće preko svakog mosta preći jednom i samo jednom.
I, još dva zanimljiva podatka.
Na ostrvu (obleženom sa [inlmath]2[/inlmath]) nalazi se grob Imanuela Kanta, čuvenog filozofa koji je i rođen u tom gradu i u njemu živeo.
Od [inlmath]7[/inlmath] mostova opisanih u ovom problemu danas je preostalo samo [inlmath]5[/inlmath], kao što se i vidi na Google mapama (dva mosta su uništena u savezničkom bombardovanju). S ovih sadašnjih [inlmath]5[/inlmath] mostova bilo bi moguće ostvariti traženi zadatak, budući da sada imamo takav graf u kojem dva čvora imaju neparan stepen (čvorovi [inlmath]2[/inlmath] i [inlmath]4[/inlmath] imaju stepen [inlmath]3[/inlmath]), dok preostali čvorivi ([inlmath]1[/inlmath] i [inlmath]3[/inlmath]) imaju paran stepen – stepen [inlmath]2[/inlmath]. Naravno, uslov za ostvarenje tražene rute bio bi taj, da krenemo iz nekog od čvorova s neparnim stepenom...
I do not fear death. I had been dead for billions and billions of years before I was born, and had not suffered the slightest inconvenience from it. – Mark Twain
7 Posta
• Stranica 1 od 1
Ko je OnLine
Korisnici koji su trenutno na forumu: Nema registrovanih korisnika i 6 gostiju