(Creat de '_Cosmin_':user/Cosmin la data de _2005-07-12_ categoria _Competitii_, autor(i) _Cosmin_)
*Continut scurt:*

 ==Include(page="template/raw")==
 
Articolul contine cateva idei de solutionare a problemelor de la etapa finala a concursului Agora. Concursul s-a desfasurat la Cluj in 9 iulie pentru concurentii ce s-au calificat in finala, dar s-a desfasurat si online pentru cei care doreau sa isi incerce puterile.

 Articolul contine cateva idei de solutionare a problemelor de la etapa finala a concursului Agora. Concursul s-a desfasurat la Cluj in 9 iulie pentru concurentii ce s-au calificat in finala, dar s-a desfasurat si online pentru cei care doreau sa isi incerce puterile.

*Continut lung:*

==Include(page="template/raw")==
 

Problema 1: Drumuri
Problema cerea determinarea unei partitionari a muchiilor dintr-un graf conex in perechi disjuncte astfel ca in fiecare pereche de muchii cele doua muchii sa aiba un capat comun. Pentru orice graf conex cu numar par de muchii exista o asemenea partitionare a muchiilor. Algoritmul ce solutioneaza problema ne demonstreaza acest lucru. Putem determina pentru graful nostru un arbore partial (arbore DFS sau BFS sau care mai vreti voi). Putem lua o frunza din arborele nostru, daca ea are grad par atunci o putem elimina din arbore si toate muchiile ce aveau un capat in ea sa le imperechem doua cate doua. Daca in schimb frunza are grad impar atunci eliminam toate muchiile mai putin cea din arbore si eliminam nodul virtual din graf, dar nu si muchia asociata care devine o muchie oarecare si va putea fi eliminata cand procesam tata frunzei actuale. Singura problema ce poate aparea este cand ajungem la radacina, dar cum dintr-un graf cu numar par de muchii am eliminat la fiecare pas un numar par de muchii inseamna