Note de curs, probleme algoritmică, 4 noiembrie 2013
În acest curs am discutat despre problema 1320 - Graph Decomposition.
Cerința
Pentru un graf dat, se cere să se determine dacă muchiile acestuia pot fi grupate două câte două, astfel încât fiecare pereche de muchii să aibă un nod comun.
Soluția
Se poate demonstra că muchiile pot fi grupate conform cerinței dacă fiecare componentă conexă a grefului conține un număr par de muchii.
Demonstrație
Deoarece oricare două muchii din două componente conexe distincte nu au niciun vârf comun, muchiile dintr-o pereche trebuie să aparțină aceleiași componente conexe. Așadar, problema partiționării trebuie rezolvată pentru fiecare componentă coonexă în parte.
Necesitatea de a avea un număr par de muchii pentru a admite o soluție este evidentă. Această condiție este și suficientă deoarece:
- dându-se o componentă conexă cu un număr par de muchii alegem la întâmplare o muchie și o ștergem;
- dacă muchia este critică, vom obține două componente conexe, una cu un număr par de muchii și una cu un număr impar de muchii - împerechem muchia ștearsă cu o muchie din componenta conexă cu număr impar de muchii;
- dacă muchia nu este critică - împerechem muchia ștearsă cu o altă muchie necritică (care sigur există).
Mod de implementare
Soluția se implementează prin identificarea componentelor conexe prin parcurgeri (în adâncime sau lățime) succesive și contorizarea muchiilor din fiecare componentă conexă.
Muchiile grafului trebuie memorate, parcurse și numărate în ambele sensuri. De aceea, pentru orice componentă conexă vom obține un număr par de muchii orientate. Acest număr trebuie împărțit la 2 pentru a obține numărul de muchii neorientate, iar acesta din urmă trebuie testat dacă este par.
