C-Tabara MATHTIME-Jupiter.ziua5.ex5
C-Tabara MATHTIME-Jupiter.ziua5.ex5
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.
-
Laurențiu Ploscaru
- Mesaje: 1237
- Membru din: Mie Mai 04, 2011 5:42 pm
- Localitate: Călimănești
- Contact:
Re: C-Tabara MATHTIME-Jupiter.ziua5.ex5
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.
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.
Faces look ugly when you're alone.
Women seem wicked when you're unwanted,
Streets are uneven when you're down.