Pagini recente » Monitorul de evaluare | Monitorul de evaluare | Monitorul de evaluare | Diferente pentru utilizator/andreea678 intre reviziile 29 si 28 | clici

Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2023-03-24 08:23:15.
Revizia anterioară Revizia următoare

Fişierul intrare/ieşire:	clici.in, clici.out	Sursă	ad-hoc
Autor	Tudor Muresan	Adăugată de	Ciprian Oprisa •cypry
Timp execuţie pe test	0.25 sec	Limită de memorie	16384 kbytes
Scorul tău	N/A	Dificultate	N/A

Clici disjuncte total interconectate prin lanțuri

Fie un graf neorientat $G=(V, E)$ format din clici disjuncte total interconectate prin lanţuri. O clică este o mulţime de vârfuri $V^{\prime} \subseteq V$ cu proprietatea că între fiecare pereche de vârfuri din $V^{\prime}$ există o muchie în $E$ . Un lanţ între nodurile $u$ şi $v$ este un drum elementar cu extremităţile $u$ şi $v$ . Toate celelalte noduri ale lanţului sunt distincte şi au gradul 2, adică au exact doi vecini. Pentru graful dat $V = V_c \cup V_2$ , unde $V_c$ este mulţimea nodurilor clicilor disjuncte (cu gradul mai mare ca 2), iar $V_2$ este mulţimea nodurilor cu gradul 2. Clicile disjuncte sunt total interconectate prin lanţuri, dacă lanţurile au extremităţile în $V_c$ şi celelalte noduri în $V_2$ , iar fiecare nod din $V_c$ este extremitatea unui singur lanţ.