bogdang

Primul
Am primit problema asta de la profu`de mate si am ajuns la concluzia ca nu se poate (e ceva cu numar impar de iesiri sau intrari),cel putin la nivel de cls. 8 nu a putut sa-mi explice...

ucigasa

problema se poate transforma intr-o problea din teoria grafurilor
Fiecare incapere inclusiv exteriorul reprezinta un nod al grafului. Fiecare usa reprezinta o linie care leaga doua puncte ale acestui graf
Problema se reduce la a demonstra daca graful contine sau nu un circuit eulerian.
Un graf pentru a putea contine un ciclu eulerian daca exista maxim un nod cu un numar impar de muchii
In cazul de fata exista mai mult de un nod cu numar impar de muchii, deci graful nu poate contine un ciclu eulerian

HAIDUCUL1

nu am scaun {vezi poza zilei}

NeeKo.

nu se poate , deoarece nr usilor depaseste q mult nr peretilor ...

ucigasa

erata
Un graf conex contine un ciclu eulerian daca si numai daca gradele tuturor varfurilor sunt numere pare

ucigasa

Din enuntul problemei nu se cauta un ciclu eulerian si se cauta un lant eulerian

asoper

haideti ca am facuto si pe asta posibila...:))

http:// imageshare . web. id/images / hh2046b70zn30qohiy3 . jpg

ucigasa

Un graf contine un lant eulerian daca toate nodurile sunt pare cu exceptia a maxim 2 noduri

ucigasa

In problema de mai sus sunt cel putin 3 noduri cu grad impar.
Deci problema nu are solutii.

dadyro

Un graf contine un drum eulerian daca si numai daca contine exact 0 sau 2 noduri cu numar impar de muchii. (Demonstratia este relativ simpla. Cu exceptia nodurilor terminale ale drumului, de fiecare data cand se ajunge intr-un nod acesta trebuie si parasit)
In figura sunt 3 incaperi care contin cate 5 usi, deci nu exisa un drum care sa treaca o singura data prin fiecare usa.