Graf bipartit și turneu

Un graf neorientat este bipartit dacă vârfurile pot fi împărțite în două grupuri astfel încât fiecare muchie unește grupuri diferite. Lanțul 1–2–3 este bipartit cu grupurile $\{1,3\}$ și $\{2\}$; un triunghi nu este, deoarece are ciclu impar. Un turneu este un graf orientat obținut orientând exact o dată fiecare muchie a unui graf complet.

Un graf neorientat este bipartit dacă mulțimea vârfurilor poate fi împărțită în două submulțimi disjuncte astfel încât fiecare muchie să unească un vârf din prima cu unul din a doua; în interiorul unei submulțimi nu există muchii. Un graf este bipartit dacă și numai dacă nu are cicluri de lungime impară. Într-un graf bipartit complet $K_{p,q}$, fiecare dintre cele $p$ vârfuri din prima parte este legat de fiecare dintre cele $q$ vârfuri din a doua, deci graful are $p\cdot q$ muchii; $K_{2,3}$ are $2\cdot 3=6$ muchii. Un turneu este un graf orientat obținut dintr-un graf complet prin alegerea unui singur sens pentru fiecare muchie: între oricare două vârfuri există exact un arc.

Exemplul 1 — testul de bipartitate prin colorare. Se colorează un vârf cu culoarea 1, vecinii lui cu 2, vecinii acestora cu 1 și așa mai departe, folosind o coadă. Dacă o muchie unește două vârfuri de aceeași culoare, graful nu este bipartit:

#include <iostream>
#include <queue>
using namespace std;
int main() {
    int n, m, a[11][11] = {}, cul[11] = {};
    cin >> n >> m;
    for (int i = 0; i < m; ++i) {
        int x, y;
        cin >> x >> y;
        a[x][y] = a[y][x] = 1;
    }
    bool bip = true;
    for (int s = 1; s <= n; ++s) {
        if (cul[s]) continue;
        cul[s] = 1;
        queue<int> q;
        q.push(s);
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            for (int v = 1; v <= n; ++v)
                if (a[u][v]) {
                    if (!cul[v]) { cul[v] = 3 - cul[u]; q.push(v); }
                    else if (cul[v] == cul[u]) bip = false;
                }
        }
    }
    cout << (bip ? "bipartit" : "nu");
    if (bip) {
        cout << "\n";
        for (int i = 1; i <= n; ++i) cout << cul[i] << " ";
    }
}

Pentru 4 4 cu muchiile $[1,2]$, $[2,3]$, $[3,4]$, $[4,1]$ se afișează bipartit, apoi 1 2 1 2: culoarea 1 are vârfurile 1 și 3, iar culoarea 2 are vârfurile 2 și 4. Dacă se adaugă $[1,3]$ (4 5), muchia unește două vârfuri de culoarea 1 și apare ciclul impar 1–2–3–1, deci se afișează nu. Un triunghi (3 3) nu este bipartit, iar un lanț este mereu bipartit. Parcurgerea se repetă din fiecare vârf necolorat, pentru a acoperi toate componentele. Timpul este $O(n^2)$ cu matrice și $O(n+m)$ cu liste de adiacență.

Exemplul 2 — turneul. Pentru $n$ vârfuri, un turneu are $n(n-1)/2$ arce, iar pentru fiecare vârf grad_intern + grad_extern = n-1. Turneul cu 4 vârfuri și arcele $1\to 2$, $1\to 3$, $1\to 4$, $2\to 3$, $3\to 4$, $4\to 2$ are 6 arce. Programul verifică, pentru fiecare pereche, că există exact un sens, și afișează gradele externe:

#include <iostream>
using namespace std;
int main() {
    int n = 4, a[5][5] = {};
    a[1][2] = a[1][3] = a[1][4] = a[2][3] = a[3][4] = a[4][2] = 1;
    bool turneu = true;
    for (int i = 1; i <= n; ++i)
        for (int j = i + 1; j <= n; ++j)
            if (a[i][j] + a[j][i] != 1) turneu = false;
    cout << turneu << "\n";
    for (int i = 1; i <= n; ++i) {
        int g = 0;
        for (int j = 1; j <= n; ++j) g += a[i][j];
        cout << g << " ";
    }
}

Se afișează 1 (este turneu), apoi 3 1 1 1. Suma gradelor externe este $3+1+1+1=6=n(n-1)/2$. Circuitul $2\to 3\to 4\to 2$ arată că un turneu poate avea circuite. Turneul ciclic $1\to 2$, $2\to 3$, $3\to 1$ are, pentru fiecare vârf, un arc de intrare și unul de ieșire.

Exemplul 3 — în formatul examenului. Care este numărul maxim de muchii al unui graf bipartit simplu cu 7 vârfuri?

• a) 10
• b) 12
• c) 14
• d) 21

Răspunsul corect este b). Un graf bipartit are cele mai multe muchii când este complet între cele două părți, cu $p+q=7$ vârfuri și $p\cdot q$ muchii. Produsele posibile sunt $1\cdot 6=6$, $2\cdot 5=10$ și $3\cdot 4=12$, deci maximul este 12, pentru partea de 3 și partea de 4 vârfuri. Varianta a) corespunde părților de 2 și 5, iar c) nu corespunde niciunei împărțiri. Varianta d) este numărul muchiilor grafului complet cu 7 vârfuri, care nu este bipartit.

Greșeli frecvente

• Greșit: un triunghi este bipartit dacă punem două vârfuri în același grup.
  Corect: muchia dintre ele ar încălca definiția.
• Greșit: într-un turneu apar ambele sensuri pentru fiecare pereche.
  Corect: apare exact unul.
• Greșit: $K_{2,3}$ are cinci muchii, câte vârfuri are.
  Corect: are șase muchii.

Înainte și după