Evo jednog problemčića za rešavanje
Potrebno je provući jednu liniju koja će da preseče sve linije obeležene crticama. Svaka linija mora biti presečena tačno jedan put :banghead:
Stara dobra klasična fora :>
Znam rešenje tako da ću pustiti nekog drugog junaka da se dokaže :bla:
Cilj zadatka je crtanje zatvorene mreze u ravni u jednom potezu (ne podizuci olovku sa hartije), ne prelazeci po vec povucenoj liniji.Takva jedna zatvorena mreza, koja se sastoji od tacaka (cvorova) i linija koje spajaju neke od ovih tacaka (spojnica), a ne presecaju se medjusobno, moze se predstaviti pomocu tzv. ravanskog grafa.Dva cvora grafa zovu se susedna ako su spojena spojnicom. Broj susednih cvorova nekog cvora zove se stepen tog cvora( na slici broj n). Za grafove koji se mogu nacrtati na pomenuti nacin (u jednom potezu, bez ponavljanja) kaze se da poseduju Ojlerov put.Teorema koja daje uslove za postojanje Ojlerovog puta (i potice od Ojlera) glasi:
"Graf poseduje Ojlerov put ako i samo ako ima dva ili nijedan cvor neparnog reda."
Na osnovu ove teoreme, ako su svi cvorovi parnog stepena tada se mreza moze nacrtati i to polazeci iz bilo koje tacke mreze, a zavrsavajuci u istoj tacki.U slucaju da postoje dva cvora neparnog stepena, mreza se moze nacrtati polazeci od jednog od tih cvorova, a zavrsavajuci u drugom.U svim ostalim slucajevima, tj. Kad je broj cvorova neparnog stepena razlicit od 0 i 2, zadatak se ne moze resiti.
Ovo je bilo malo teorije a sad zadatak.
Podelicemo sliku na oblasti A,B,C,D,E,F a linije cemo obeleziti brojevima od 1 do 16. (prilog slika)
Oblasti nam predstavljaju cvorove grafa a linije nam predstavljaju grane grafa. (prilog slika 2)
Na osnovu grafa vidimo da su cvorovi A,B,D,F neparnog reda pa prema gore navedenoj teoremi ne mozemo povuci trazenu liniju. Moguce da sam negde pogresio ... Prelistao sam brdo nekih teorema iz teorije grafova i topologije tako da sad jedva vidim sta pisem :D
Bravo :-?
Očekivao sam da bar neko nešto napiše ali ovako detaljno sigurno ne <:-P Svaka čast još jednom :-?
Elem ovaj problem ćete naći u skoro svakoj knjizi o teoriji grafova a ima ga i u zbirkama matematičkih problema za razibrigu. Ko još uvek ima drugo izdanje "Moje matematike" iz osnovne škole može da pronađe ovaj problem na 27. stranici sa donekle pojednostavljenim grafovima.
Poenta je da je rešenje zadatka da nema rešenja. Zbog toga što sam ja odbio da tako prokomentarišem zadatake bez rešenja par puta sam dobijao kečeve ko vrata ali sam zbog takve jedne konstatacije recimo položio i elektrotehniku ;) Dobro...Lažem... Nije samo zbog nje ali dosta pomogne kada prokomentarišete na profesorovo iznenađenje da vam je postavio nemoguć zadatak :dzavo:
A evo odakle je sve ovo počelo... Seven Bridges of Königsberg (http://en.wikipedia.org/wiki/Seven_Bridges_of_Königsberg)
Negde imam knjigu koja se bavi algoritmima i koja na nekoliko mesta koristi upravo ovu foru sa Ojlerovom putanjom a kada je nađem okačiću je negde da možete da pogledate o čemu se radi.
Još jednom svaka čast na ovako detaljnom objašnjenju :bravo:
"Pa posle kažu kako naši studenti ne ..."
Svako ko je malo dublje začeprkao po matematici bio je u prlici da se sretne sa Ojlerom i njegovim problemom "Sedam keninsberških mostova". Moj nastavnik matematike i nekadašnji razredni starešina Boriša Borišić bio je opčinjen Ojlerom. Zato je pomen Ojlera na Forumu i prilika da pomenem svog učitelja matematike, koji je presudno uticao da ovu nauku volim do današnjih dana, ...
Evo nekoliko linkova na pomenuti problem i njegovo rešenje, ali i neke druge probleme.
- http://mathforum.org/isaac/problems/bridges1.html
- http://www.jimloy.com/puzz/konigs.htm
- http://www.jimloy.com/puzz/puzz.htm
- http://mathworld.wolfram.com/KoenigsbergBridgeProblem.html
- ...
Još jednom pohvale i sve čestitke Vojislavu.
Ovaj problem je nerjesiv. Ne znam na koji nacin ste ga rijesili.Posaljite sliku da vidim kako su presjecene linije.Ovaj problem je i dokazan da je nerjesiv.
Па колега је то и показао... Погледај пост поново !!! :)