== include(page="template/taskheader" task_id="g2mm") ==

Se da un graf conex si neorientat $G$, avand $N$ noduri si $M$ muchii. Distanta dintre doua noduri $x$ si $y$ ale unui graf $G$, $dist~G~(x,y)$ se defineste ca fiind numarul minim de muchii ce trebuie traversate pentru a ajunge de la un nod la celalalt. Patratul unui graf $G$ (notat cu $G^2^$) se defineste in felul urmator:

Se da un graf conex si neorientat $G$, avand $N$ noduri si $M$ muchii. Distanta dintre doua noduri $x$ si $y$ ale unui graf $G$, $dist{~G~}(x,y)$ se defineste ca fiind numarul minim de muchii ce trebuie traversate pentru a ajunge de la un nod la celalalt. Patratul unui graf $G$ (notat cu $G^2^$) se defineste in felul urmator:

* are aceleasi noduri ca si graful $G$

* are muchie intre doua noduri $x$ si $y$, numai daca $dist~G~(x,y) ≤ 2$ (distanta dintre ele este cel mult $2$, in graful $G$)

* are muchie intre doua noduri $x$ si $y$, numai daca $dist{~G~}(x,y) ≤ 2$ (distanta dintre nodurile $x$ si $y$ este cel mult $2$, in graful $G$)

Determinati, daca exista, un cuplaj perfect in $G^2^$. Un cuplaj perfect intr-un graf $H$ consta din $N/2$ muchii, astfel incat fiecare din cele $N$ noduri ale lui $H$ apare ca unul din cele $2$ capete ale exact unei singure muchii din cadrul cuplajului.

|
== include(page="template/taskfooter" task_id="g2mm") ==

3243