Graful complet

Un graf simplu neorientat este complet dacă fiecare pereche de vârfuri distincte este legată printr-o muchie. Graful complet cu 3 vârfuri este triunghiul și are 3 muchii: 1–2, 1–3 și 2–3.

Un graf simplu neorientat cu $n$ vârfuri este complet dacă oricare două vârfuri distincte sunt adiacente. Se notează $K_n$. Numărul muchiilor este $C_n^2=n(n-1)/2$, fiindcă fiecare dintre cele $n$ vârfuri are $n-1$ vecini, suma gradelor este $n(n-1)$, iar fiecare muchie este numărată de două ori în această sumă.

Exemplul 1 — numărul de muchii. Pentru $n=4$ formula dă $4\cdot 3/2=6$:

#include <iostream>
using namespace std;
int main() {
    int n = 4, muchii = n * (n - 1) / 2;
    cout << muchii;
}

Se afișează 6. Numără perechile fără să le repeți: [1,2], [1,3], [1,4], [2,3], [2,4], [3,4]. Sunt șase, deci rezultatul programului corespunde definiției. Dacă elimini [2,4], rămân cinci muchii, iar gradele lui 2 și 4 scad de la 3 la 2; graful nu mai este complet, chiar dacă este încă conex. Programul care calculează doar numărul face $O(1)$ operații aritmetice, iar înmulțirea $n(n-1)$ încape într-un int pentru $n$ de ordinul miilor.

Exemplul 2 — construirea matricei lui $K_5$. Pentru $n=5$, formula dă $5\cdot 4/2=10$ muchii și grad 4 pentru fiecare vârf. Programul construiește efectiv matricea de adiacență, numără muchiile și calculează gradul vârfului 3:

#include <iostream>
using namespace std;
int main() {
    int n = 5, a[6][6] = {}, m = 0, g = 0;
    for (int i = 1; i <= n; ++i)
        for (int j = i + 1; j <= n; ++j) {
            a[i][j] = a[j][i] = 1;
            ++m;
        }
    for (int j = 1; j <= n; ++j) g += a[3][j];
    cout << m << " " << g;
}

Se afișează 10 4. Diagonala principală rămâne cu zerouri, deoarece un vârf nu este adiacent cu el însuși, iar fiecare pereche $(i,j)$ cu $i<j$ este parcursă o singură dată. Cele două cicluri for execută $4+3+2+1=10$ iterații interioare, adică exact numărul muchiilor. Construirea matricei examinează $O(n^2)$ perechi și folosește $O(n^2)$ memorie, spre deosebire de calcularea formulei.

Graful complementar. Complementarul unui graf cu $n$ vârfuri și $m$ muchii are aceleași vârfuri și toate muchiile care lipsesc, deci $n(n-1)/2-m$ muchii. Un graf cu 6 vârfuri și 9 muchii are $15-9=6$ perechi neadiacente; adăugarea lor îl face complet.

Verificarea unui graf dat prin matrice. Un graf este complet dacă și numai dacă toate elementele din afara diagonalei principale sunt 1, adică a[i][j] = 1 pentru orice $i\ne j$. Condiția este echivalentă cu faptul că fiecare linie are suma $n-1$ sau cu faptul că numărul muchiilor este $n(n-1)/2$. Un singur 0 în afara diagonalei este de ajuns ca graful să nu fie complet. Orice $k$ vârfuri ale unui graf complet formează tot un graf complet $K_k$, cu $k(k-1)/2$ muchii; de exemplu, în $K_5$ orice trei vârfuri formează un triunghi, iar numărul triunghiurilor este $C_5^3=10$.

Exemplul 3 — testarea unui graf dat prin matrice. Funcția verifică doar perechile $i<j$, pentru că matricea este simetrică, și se oprește la prima pereche neadiacentă:

bool complet(int n, int a[][11]) {
    for (int i = 1; i <= n; ++i)
        for (int j = i + 1; j <= n; ++j)
            if (a[i][j] == 0) return false;
    return true;
}

Fie $n=4$ și un graf cu muchiile 1–2, 1–3, 1–4, 2–3 și 3–4, deci cu a[2][4] = a[4][2] = 0. Se verifică pe rând perechile (1,2), (1,3), (1,4), (2,3) și (2,4): primele patru au valoarea 1, iar la a cincea se găsește 0 și funcția întoarce false. Graful are 5 muchii, față de $4\cdot 3/2=6$ cât ar avea $K_4$, iar lipsa lui 2–4 este exact muchia care face diferența. În cel mai rău caz se fac $n(n-1)/2$ verificări, deci timpul este de ordinul $n^2$.

Dacă un graf simplu cu $n$ vârfuri are exact $n(n-1)/2$ muchii, este complet; nu există alte perechi disponibile. Pentru $n=1$, graful complet are zero muchii și singurul vârf are gradul zero. Ca să afli numărul de vârfuri din numărul de muchii, rezolvă $n(n-1)=2m$ și păstrează rădăcina pozitivă. Dacă ți se dă numărul de muchii al unui graf cu $n$ vârfuri, numărul muchiilor care lipsesc pentru a fi complet este $n(n-1)/2-m$. Orice graf simplu cu $n$ vârfuri are cel mult $n(n-1)/2$ muchii, iar un graf cu mai multe muchii nu este simplu. Numărul triunghiurilor din $K_n$ este $C_n^3$: 4 pentru $K_4$ și 10 pentru $K_5$. Graful complet este conex și, pentru $n\ge 3$, are cicluri; este eulerian dacă și numai dacă $n$ este impar, fiindcă gradele $n-1$ trebuie să fie pare. Dacă într-o problemă apare „toate perechile de vârfuri sunt adiacente”, aceasta este chiar definiția grafului complet.

Exemplu în formatul examenului. Un graf complet are 45 de muchii. Câte vârfuri are?

• a) 8
• b) 9
• c) 10
• d) 11

Răspunsul corect este c). Din $n(n-1)/2=45$ rezultă $n(n-1)=90=10\cdot 9$, deci $n=10$. Verificare: un graf complet cu 10 vârfuri are $10\cdot 9/2=45$ muchii. Varianta b) ar da $9\cdot 8/2=36$ muchii, varianta a) ar da 28, iar varianta d) ar da $11\cdot 10/2=55$. Varianta b) apare dacă se confundă $n$ cu gradul fiecărui vârf, adică $n-1=9$.

Greșeli frecvente

• Greșit: un graf complet cu 4 vârfuri are 12 muchii.
  Corect: 12 este suma gradelor, iar muchiile sunt 6.
• Greșit: un graf complet poate avea două vârfuri fără muchie între ele.
  Corect: fiecare pereche este adiacentă.
• Greșit: formula numără și bucle.
  Corect: numără perechi de vârfuri distincte.

Înainte și după