C-Tabara MATHTIME-Jupiter.ziua5.ex4

Avatar utilizator
Iman
Mesaje: 51
Membru din: Mar Noi 16, 2010 9:51 pm
Localitate: Constanta

C-Tabara MATHTIME-Jupiter.ziua5.ex4

Mesaj de Iman »

Intr-o tara sunt $$ 100 $$ de orase,iar cateva dintre ele sunt unite cu drumuri astfel incat din fiecare oras se poate ajunge in oricare altul .In total exista $$ 1000 $$ de drumuri.Cateva drumuri se vor inchide astfel incat din fiecare oras sa porneasca un numar par de drumuri spre celelalte orase.In cate moduri se poate indeplini acest lucru?
drytime
Mesaje: 183
Membru din: Lun Iul 19, 2010 4:56 pm

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

Mesaj de drytime »

Pentru a intelege solutia, e suficient sa cititi sectiunile de la 1.1 la 1.5 de aici.

Sunt destul de sigur ca in problema nu este vorba de 1000 de drumuri. Iata de ce: Luam o multime de 44 de puncte si punem toate muchiile (drumurile...) intre ele. Conecta si restul oraselor cu niste drumuri, astfel incat sa ne iasa la socoteala 1000 de drumuri si graful (de acum incolo voi vorbi doar de graful aferent problemei) sa fie conex. Ceea ce cautam noi e numarul de subgrafuri in care fiecare componenta conexa are ciclu eulerian. ceea ce e in restul celor 44 orase e relativ neglijabil (nu prea sunt multe drumuri intre ele), deci (intuitiv), ar trebui doar sa gasim numarul cerut pentru $K_{44}$. Aceste numere sunt foarte greu de calculat (apar in lista aceea cu siruri, dar nu prea exista o formula generala care sa furnizeze repede rezultatul). Hai sa spunem ca am reusit sa gasim numarul pentru acest graf. dar acum luam un altul, in care luam 43 de orase toate unite intre ele, iar in rest cateva drumuri astfel incat sa avem 1000 drumuri si graful sa fie conex. Sunt aproape sigur ca si aici numarul e foarte greu de calculat, dar si ca e diferit de cel din primul caz. Mai mult, gasirea multimilor valorilor posibile pare o treaba si mai imposibila... (de retinut ca argumentele prezentate sunt doar intuitive si nu prea abunda de rigurozitate... :D ).

Oricum, in cazul in care avem 100 de drumuri (iar greseala la scriere ar putea fi plauzibila) este rezolvabil:
Avem un graf conex cu 100 varfuri si la fel de multe muchii, deci graful are un ciclu (altfel ar fi arbore si ar avea 99 muchii). Sa observam ca eliminare unei muchii dintr-un ciclu nu strica faptul ca graful este conex (aceasta e adevarat pentru orice graf conex). Luam un ciclu $x_1, x_2,..., x_n$. Fie $A_i=\{x:x\in V(G)$ si exista un drum de la $x$ la $x_i$ care nu trece nici prin $x_{i-1}$, nici prin $x_{i+1}\}$. In primul rand e clar ca multimile acestea acopera tot $V(G)$, pur si simplu pentru ca graful e conex. A doua observatie e ca graful $G(A_i)$ este conex, unde graful $G(A_i)$ este graful indus de mutimea $A_i$. Pe baza acestor doua observatii ne reiese ca fiecare graf $G(A_i)$ este un arbore, dar mai mult, ca singura muchie intre $A_i$ si $A_j$, cu $i\neq j$ este muchia $\{x-i,x_j\}$, iar asta doar cand $i-j\in\{1,-1\}$ ( nu am precizat, dar indicii, deci si diferenta lor, sunt considerati $\mod n$). Acesta e doar un exercitiu simplu de numarat muchii.

Acum e nevoie de urmatoarea lema:
Lema: Pentru un arbore $T$, numarul de eliminari de muchii cu proprietatea din enuntul problemei e cea in care le eliminam pe toate.
Demonstratie: Pentru un arbore $T$, exista un varf cu gradul 1 (altfel fiecare varf are gradul cel putin 2 si numarand muchiile ne ies mai multe decat trebuie). Pentru ca acel varf sa aiba in noul subgraf gardul par, trebuie sa eliminam muchie ce pleaca din el. Acum consideram graful indus de multimea $V(T)$ fara acel varf. Acest graf e arbore (demonstrati!) si continuam inductiv procedeul de mai inainte.

Revenim la demonstratia problemei. Hai sa consideram graful $G(A_i)$, despre care stim ca e arbore. Vreau sa arat ca daca eliminam muchii din $G$ astfel incat fiecare varf are gradul par atunci eliminand muchiile aferente in $G(A_i)$, fiecare varf va avea gradul par (considerand doar muchiile din $G(A_i)$, nu si cele din exteriorul sau). Aceasta e destul de usor: pentru un varf din $V(G(A_i))$ \ $\{x_i\}$ aceasta este clar, doarece orice muchie ce pleaca din el si se afla in $G$, se afla si in $G(A_i)$. Problema (nu foarte mare) e pentru $x_i$. Dar din el pleaca exact doua muchii care se afla in $G$ si nu in $G(A_i)$, adica un numar par. Scazanad un numar par dintr-unul par ia ghiciti ce obtinem. ( :mrgreen: )

Pe baza lemei deci trebuie sa eliminam toate muchiile din $G(A_i)$. Evident argumentul merge pentru orice $i$, deci in final ramanem doar cu ciclul de la inceput. Pentru acesta, numarul de eliminari de muchii astfel incat la final sa obtinem ca fiecare varf are gradul par este 2: intr-unul din cazuri nu eliminam muchii din el (deci fiecare varf are gradul 2), iar in celalalt caz eliminam cel putin o muchie. Fie aceasta $\{x_i,x_{i+1}\}$. Atunci ca $x_{i+1}$ sa aiba gradul par trebuie sa eliminam si muchia $\{x_{i+1},x_{i+2}\}$ si tot asa, adica eliminam toate muchiile ciclului. Deci numarul cerut este 2.
Scrie răspuns