C-Tabara MATHTIME-Jupiter.ziua5.ex5

C-Tabara MATHTIME-Jupiter.ziua5.ex5

Mesajde Iman » Sâm Sep 03, 2011 7:03 pm

Intr-o tara sunt $ 2000 $ de orase.Unele perechi de orase sunt unite printr-un drum astfel incat din orice oras se poate ajunge in oricare altul.Aratati ca tara poate fi impartita in cateva republici(chiar si $1$ singura) astfel incat in oricare republica,din fiecare oras se poate ajunge in oricare altul (in mod unic) fara a iesi in afara republicii.
Avatar utilizator
Iman
 
Mesaje: 51
Membru din: Mar Noi 16, 2010 9:51 pm
Localitate: Constanta

Re: C-Tabara MATHTIME-Jupiter.ziua5.ex5

Mesajde Laurențiu Ploscaru » Lun Sep 05, 2011 8:46 pm

O soluție interesantă:

Considerăm graful aferent problemei. Fiecare oraș reprezintă un punct. Dacă între 2 orașe avem drum, atunci avem o muchie între 2 puncte. Totul se reduce la binecunoscuta teoremă care spune că orice graf poate fi partiționat în mod unic în componente conexe.
Un graf este conex dacă și numai dacă între oricare 2 puncte există un drum format din una sau mai multe muchii.
People are strange when you're a stranger,
Faces look ugly when you're alone.
Women seem wicked when you're unwanted,
Streets are uneven when you're down.
Avatar utilizator
Laurențiu Ploscaru
 
Mesaje: 1237
Membru din: Mie Mai 04, 2011 5:42 pm
Localitate: Călimănești


Înapoi la Combinatorica

Cine este conectat

Utilizatorii ce navighează pe acest forum: Niciun utilizator înregistrat şi 1 vizitator

cron