Graf neorientat

Ce este

Un graf nu te interesează prin „desenul" lui, ci prin cine e legat cu cine. Poziția orașelor pe hartă nu contează; contează doar perechile de orașe între care există șosea. Formal, un graf neorientat este o pereche G = (V, E), unde:

• V este mulțimea de noduri (sau vârfuri) — obiectele: orașe, oameni, pagini web, calculatoare. Notăm n numărul lor.
• E este mulțimea de muchii — legăturile dintre obiecte. O muchie este o pereche neordonată de noduri, scrisă {u, v}. Notăm m numărul lor.

Cuvântul-cheie este neordonată: muchia {u, v} și {v, u} sunt una și aceeași. De aceea spunem că graful e neorientat — muchia nu are sens, merge în ambele direcții. Asta e diferența față de graful orientat, unde un arc (u, v) merge doar dinspre u spre v.

Trei termeni pe care îi vei folosi constant:

• două noduri unite printr-o muchie sunt adiacente (sunt vecini);
• muchia este incidentă cu fiecare dintre cele două capete ale ei;
• gradul unui nod, notat d(u), este numărul de muchii incidente cu el — adică numărul lui de vecini.

Grafurile din programă sunt simple: fără muchii de la un nod la el însuși (bucle) și fără două muchii identice. Într-un graf simplu cu n noduri, fiecare dintre cele n * (n - 1) / 2 perechi de noduri poate fi unită de cel mult o muchie — deci m nu poate depăși această valoare.

Cum arată

Apasă Redă și urmărește cum graful de mai jos se construiește muchie cu muchie. La fiecare pas, fii atent la trei lucruri: apare o linie nouă, cele două capete ale ei se aprind simultan (muchia le aparține amândurora), iar linia nu are săgeată — legătura e bidirecțională. Contorul de sub desen numără muchiile dezvăluite din totalul de 7.

Graful din animație are n = 6 noduri și m = 7 muchii: {0,1}, {0,2}, {1,3}, {2,3}, {3,4}, {4,5}, {2,5}. Pe hârtie îl reprezentăm cel mai des prin lista de adiacență: pentru fiecare nod, lista vecinilor lui. Citește tabelul ca „nodul din stânga e legat de toate nodurile din dreapta":

Privește lista nodului 3, unul dintre cele mai „aglomerate" — are trei vecini, deci gradul 3:

Verifică simetria: pentru muchia {0,1}, nodul 1 apare în lista lui 0 și nodul 0 apare în lista lui 1. Aceeași muchie, scrisă din ambele capete. Suma gradelor este 2 + 2 + 3 + 3 + 2 + 2 = 14, adică exact 2 * 7 — pară, deci consistentă cu observația de mai sus.

Implementare C++

Citim numărul de noduri n și de muchii m, apoi m perechi u v. Pentru fiecare muchie facem două adăugări în lista de adiacență: pe v în lista lui u și pe u în lista lui v. Aceasta este simetria care definește graful neorientat.

#include <iostream>
#include <vector>
using namespace std;

int main() {
    // n = numar de noduri, m = numar de muchii
    int n = 6, m = 7;
    vector<int> adj[6];    // liste de vecini, noduri de la 0 la n-1

    // cele 7 muchii ale grafului din animatie
    int muchii[7][2] = { {0, 1}, {0, 2}, {1, 3}, {2, 3}, {3, 4}, {4, 5}, {2, 5} };

    for (int i = 0; i < m; i++) {
        int u = muchii[i][0];
        int v = muchii[i][1];
        adj[u].push_back(v);    // v devine vecin al lui u
        adj[v].push_back(u);    // SI u devine vecin al lui v (simetrie)
    }

    // afisam lista de adiacenta; gradul = lungimea listei
    for (int nod = 0; nod < n; nod++) {
        cout << "Nodul " << nod << " (grad " << adj[nod].size() << "): ";
        for (int vecin : adj[nod])
            cout << vecin << " ";
        cout << "\n";
    }
    return 0;
}
// Nodul 0 (grad 2): 1 2
// Nodul 1 (grad 2): 0 3
// Nodul 2 (grad 3): 0 3 5
// Nodul 3 (grad 3): 1 2 4
// Nodul 4 (grad 2): 3 5
// Nodul 5 (grad 2): 4 2

În concurs vei citi muchiile cu cin >> u >> v într-o buclă; aici le-am pus direct în cod ca să vezi rezultatul concret. Linia esențială este perechea adj[u].push_back(v) și adj[v].push_back(u) — fără a doua, ai construi din greșeală un graf orientat. Memoria ocupată este proporțională cu n + 2 * m, motiv pentru care lista de adiacență e reprezentarea implicită la limite mari.