Tipuri speciale de grafuri

Programa cere trei tipuri speciale de grafuri: graful complet, graful bipartit și graful turneu. Fiecare se recunoaște după o proprietate a mulțimii muchiilor sau arcelor, iar proprietatea se poate verifica direct în matricea de adiacență.

Noțiunile de bază folosite aici (adiacență, grad, drum, subgraf) sunt definite în subcapitolul Grafuri orientate și neorientate. Terminologie.

Graful complet

Graful neorientat complet

Proprietățile grafului Kn:

• numărul muchiilor este n(n − 1)/2, adică numărul submulțimilor cu două elemente ale unei mulțimi cu n elemente; K4 are 6 muchii;
• gradul fiecărui nod este n − 1, fiindcă nodul este adiacent cu toate celelalte;
• numărul maxim de muchii: dintre toate grafurile neorientate cu n noduri, Kn are cele mai multe muchii;
• matricea de adiacență are 0 pe diagonala principală și 1 în rest.

Din a treia proprietate rezultă, de exemplu, că nu există un graf neorientat cu 100 de noduri și 4 951 de muchii: graful K100 are 100 · 99 / 2 = 4 950 de muchii, iar niciun graf cu 100 de noduri nu are mai multe.

Subgrafurile unui graf complet. Orice subgraf al lui Kn, generat de k noduri, este graful complet Kk: oricare două dintre cele k noduri sunt adiacente și în subgraf. Prin urmare, Kn conține atâtea subgrafuri complete cu k noduri câte submulțimi cu k elemente are mulțimea nodurilor, adică C(n, k).

Graful orientat complet

Un graf orientat cu n noduri este complet dacă oricare două noduri distincte sunt adiacente, adică între ele există cel puțin un arc. Pentru o pereche de noduri x, y există trei situații posibile: arcul (x, y), arcul (y, x) sau amândouă arcele.

De aici rezultă:

• pentru n dat există mai multe grafuri orientate complete, anume 3^(n(n−1)/2); pentru n = 4 sunt 3⁶ = 729;
• un graf orientat complet are cel puțin n(n − 1)/2 arce, câte unul pentru fiecare pereche, și cel mult n(n − 1) arce, câte două pentru fiecare pereche;
• în matricea de adiacență, pentru orice i ≠ j, cel puțin unul dintre elementele a[i][j] și a[j][i] este 1.

Numărul minim de arce care trebuie adăugate unui graf orientat pentru ca el să devină complet este numărul perechilor i < j pentru care a[i][j] = a[j][i] = 0.

Graful bipartit

Definiție

Un graf G = (X, U) este bipartit dacă mulțimea nodurilor se poate împărți în două mulțimi nevide A și B, cu A ∪ B = X și A ∩ B = ∅, astfel încât fiecare muchie sau arc să aibă o extremitate în A și cealaltă în B. Între două noduri din aceeași mulțime nu există nicio muchie.

Observații:

• împărțirea nu trebuie să fie vizibilă în desen. Un graf este bipartit dacă mulțimile A și B există; desenul pe două rânduri doar face proprietatea ușor de văzut;
• nodurile izolate pot fi puse în oricare dintre cele două mulțimi, fiindcă nu au muchii;
• o muchie între două noduri din aceeași mulțime face împărțirea nepotrivită. Dacă în G3 se adaugă muchia [1,3], graful nu mai este bipartit: nodurile 1, 3 și 4 sunt adiacente două câte două, iar oricum s-ar împărți, două dintre ele ajung în aceeași mulțime.

La graful orientat, definiția este aceeași, cu arce în loc de muchii: fiecare arc are o extremitate în A și cealaltă în B, indiferent de sensul lui.

Graful bipartit complet

Graful bipartit complet nu este un graf complet, dacă cel puțin una dintre mulțimi are două sau mai multe noduri: nodurile 3 și 4 din K2,3 nu sunt adiacente.

Câte grafuri bipartite complete se pot forma cu n noduri date. Un graf bipartit complet este determinat de împărțirea nodurilor în mulțimile A și B. Mulțimea A poate fi oricare submulțime nevidă, diferită de mulțimea tuturor nodurilor, deci există 2ⁿ − 2 alegeri. Perechile (A, B) și (B, A) dau însă același graf, așa că numărul grafurilor distincte este

(2ⁿ − 2) / 2 = 2ⁿ⁻¹ − 1

Pentru n = 3 se obțin 3 grafuri: nodul 1, nodul 2 sau nodul 3 este unit cu celelalte două noduri, care nu sunt unite între ele. Pentru n = 4 se obțin 7 grafuri.

Verificarea unui graf bipartit

Metoda cea mai directă încearcă toate împărțirile nodurilor în două mulțimi. Împărțirea se reține într-un vector x, cu x[i] = 1 dacă nodul i este în A și x[i] = 0 dacă este în B. Vectorul se generează ca un număr în baza 2, prin adunarea repetată a lui 1, de la 0…01 până la 1…10; se omit vectorul cu toate elementele 0 și cel cu toate elementele 1, în care una dintre mulțimi ar fi vidă.

Pentru fiecare împărțire se verifică toate muchiile. Graful este bipartit dacă există o împărțire în care nicio muchie nu are ambele extremități în aceeași mulțime. Dacă, în plus, graful are exact card(A) · card(B) muchii, el este bipartit complet.

Date de intrare. Pe prima linie n și m (n ≤ 15), pe fiecare dintre următoarele m linii extremitățile unei muchii.

#include <iostream>
using namespace std;

int u[200], v[200], x[16], n, m;

void citire() {
    cin >> n >> m;
    for (int k = 1; k <= m; k++)
        cin >> u[k] >> v[k];
}

/* Trece la urmatoarea impartire: aduna 1 la numarul in baza 2
   memorat in x[1..n]. Intoarce 0 cand toate cifrele erau 1. */
int urmatoarea() {
    int j = n;
    while (j > 0 && x[j] == 1) {
        x[j] = 0;
        j--;
    }
    if (j == 0)
        return 0;
    x[j] = 1;
    return 1;
}

/* Numarul nodurilor din multimea A. */
int numarA() {
    int a = 0;
    for (int i = 1; i <= n; i++)
        a = a + x[i];
    return a;
}

/* Impartirea din x este buna daca fiecare muchie are extremitatile
   in multimi diferite. */
int buna() {
    for (int k = 1; k <= m; k++)
        if (x[u[k]] == x[v[k]])
            return 0;
    return 1;
}

/* Cauta o impartire buna, cu B nevida. Intoarce 1 daca o gaseste;
   impartirea gasita ramane in x. */
int cautaImpartire() {
    while (urmatoarea())
        if (numarA() < n && buna())
            return 1;
    return 0;
}

/* Afiseaza nodurile i pentru care x[i] = e. */
void afiseazaMultimea(int e) {
    for (int i = 1; i <= n; i++)
        if (x[i] == e)
            cout << " " << i;
}

int main() {
    citire();
    if (!cautaImpartire()) {
        cout << "nu este bipartit";
        return 0;
    }
    cout << "A:";
    afiseazaMultimea(1);
    cout << "\nB:";
    afiseazaMultimea(0);
    int a = numarA();
    if (m == a * (n - a))
        cout << "\nbipartit complet";
    else
        cout << "\nbipartit, dar nu complet";
    return 0;
}

Pentru graful G3 programul afișează A: 2 4 6, B: 1 3 5 și bipartit, dar nu complet: prima împărțire găsită are mulțimile în ordinea inversă celei din text, ceea ce descrie același graf. Pentru graful K2,3 afișează bipartit complet, iar după adăugarea muchiei [1,3] la G3 afișează nu este bipartit.

Există 2ⁿ − 2 împărțiri, iar pentru fiecare se verifică cel mult m muchii, deci timpul este de ordinul O(2ⁿ · m). Metoda se folosește numai pentru grafuri cu puține noduri.

Graful turneu

Definiție

Graful turneu este un caz particular de graf orientat complet: oricare două noduri sunt adiacente, iar între ele există exact un arc, nu două.

Proprietăți

Gradele nodurilor din G4:

Într-un graf turneu este adevărată și egalitatea sumelor pătratelor: d⁺(x1)² + … + d⁺(xn)² = d⁻(x1)² + … + d⁻(xn)². În G4, ambele sume sunt 26.

Drumul care trece prin toate nodurile

În orice graf turneu există un drum elementar pe care se află toate nodurile grafului. Drumul se construiește adăugând nodurile unul câte unul, fără ca drumul format până atunci să se strice.

Fie D = (d1, d2, …, dk) un drum elementar care trece prin nodurile deja adăugate și i un nod nou. Între i și fiecare nod al drumului există un arc: