Problemčić

Započeo maxogm, 31.12.2008, 11:44

« prethodna tema - sledeća tema »
Idi dole

maxogm

31.12.2008, 11:44 Poslednja Izmena: 31.12.2008, 11:45 od maxo
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:

holodoc

Stara dobra klasična fora :>
Znam rešenje tako da ću pustiti nekog drugog junaka da se dokaže :bla:
<?php
abstract class Ignorance extends Stupidity implements Unavoidable 
    private function 
__construct(){
        
parent::__destruct();
    }; 

// EOF -> life.php

vojamax87

#2
04.01.2009, 23:39 Poslednja Izmena: 04.01.2009, 23:41 od vojamax87
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




holodoc

#3
05.01.2009, 01:27 Poslednja Izmena: 05.01.2009, 01:34 od holodoc
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

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:
<?php
abstract class Ignorance extends Stupidity implements Unavoidable 
    private function 
__construct(){
        
parent::__destruct();
    }; 

// EOF -> life.php

Siniša Ranđić

"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.Još jednom pohvale i sve čestitke Vojislavu.

bojancvijanovic

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.

daxmirkovic

Па колега је то и показао... Погледај пост поново !!! :)

Idi gore