După ce știi ce sunt nodurile, muchiile și gradele, următorul pas la grafuri este să înțelegi cum „circuli” printr-un graf: lanțuri, cicluri și conexitate. La BAC Informatică, aceste noțiuni apar în grile de tipul „câte componente conexe are graful”, „câte muchii trebuie adăugate ca graful să devină conex” sau „care este numărul maxim de muchii al unui graf neconex cu n noduri”. Toate se rezolvă cu definiții clare și câteva raționamente pe care le explicăm mai jos.

Lanțul

Într-un graf neorientat, un lanț este o succesiune de noduri x₁, x₂, …, xₖ în care oricare două noduri consecutive sunt unite printr-o muchie. Lungimea lanțului este numărul de muchii parcurse, adică k − 1, nu numărul de noduri.

Orice lanț elementar este și simplu, dar nu și invers.

Ciclul

Un ciclu este un lanț simplu în care primul nod coincide cu ultimul. Ciclul este elementar dacă, în afară de primul și ultimul, nodurile sunt distincte. Un ciclu are cel puțin 3 muchii: lanțul 1, 2, 1 folosește de două ori aceeași muchie, deci nu este ciclu. Un graf care nu conține niciun ciclu se numește aciclic.

Exemplul cu care lucrăm

Fie graful cu n = 8 noduri și m = 6 muchii: [1,2], [2,3], [3,1], [4,5], [6,7], [6,8].

Conexitate și componente conexe

Un graf este conex dacă între oricare două noduri există un lanț. O componentă conexă este o „bucată” maximală conexă a grafului: un grup de noduri legate între ele, fără nicio muchie spre nodurile din afara grupului.

Graful nostru are 3 componente conexe: {1, 2, 3}, {4, 5} și {6, 7, 8}. Atenție: un nod izolat formează singur o componentă conexă. Dacă am adăuga un nod 9 fără muchii, am avea 4 componente.

Formulele care apar în grile

Numărul minim de muchii pentru un graf conex

Un graf conex cu n noduri are cel puțin n − 1 muchii. Intuitiv: pornești cu n noduri izolate (n componente), iar fiecare muchie adăugată poate reduce numărul de componente cu cel mult 1. Ca să ajungi la o singură componentă, ai nevoie de cel puțin n − 1 muchii. Un graf conex cu exact n − 1 muchii este un arbore: conex și fără cicluri.

Generalizare: un graf cu n noduri și p componente conexe are cel puțin n − p muchii.

Câte muchii trebuie adăugate

Ca un graf cu p componente conexe să devină conex, trebuie adăugate minimum p − 1 muchii, câte una între componente, „în lanț”. Pentru exemplul nostru: 2 muchii, de exemplu [3,4] și [5,6].

Câte muchii trebuie eliminate ca să nu mai fie cicluri

Un graf cu n noduri, m muchii și p componente conexe devine aciclic, păstrându-și componentele, după eliminarea a exact m − n + p muchii. În exemplul nostru: 6 − 8 + 3 = 1, adică eliminăm o muchie din ciclul 1, 2, 3. Pentru un graf conex, formula devine m − n + 1.

Numărul maxim de muchii cu p componente

Ca să ai cât mai multe muchii, faci o componentă cât mai mare și completă, iar celelalte p − 1 componente le lași ca noduri izolate. Componenta mare are n − p + 1 noduri, deci:

maxim = (n − p + 1)(n − p) / 2 muchii.

Pentru n = 8 și p = 3: componenta mare are 6 noduri, deci 6·5/2 = 15 muchii, plus 2 noduri izolate.

Numărul maxim de muchii al unui graf neconex

Este cazul particular p = 2: un graf complet cu n − 1 noduri și un nod izolat, adică (n − 1)(n − 2)/2 muchii. Pentru n = 8, asta înseamnă 21. Consecință utilă: orice graf cu 8 noduri și cel puțin 22 de muchii este sigur conex.

La BAC: la întrebările cu „minim” și „maxim”, desenează cazul extrem. Pentru minim de muchii ca graful să fie conex, gândește-te la un lanț; pentru maxim de muchii cu p componente, la un graf complet plus noduri izolate. Un desen de 10 secunde te scapă de formule încurcate.

Graful complet, eulerian și hamiltonian

Ușor de reținut: eulerian ↔ muchii, hamiltonian ↔ noduri (vârfuri).

Numărarea componentelor conexe în C++

Ideea: pornești dintr-un nod nevizitat și marchezi tot ce poți atinge din el printr-o parcurgere în adâncime (DFS). Fiecare nou punct de plecare înseamnă o nouă componentă.

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

int n, a[101][101], viz[101];

void dfs(int x)
{
    viz[x] = 1;
    for (int y = 1; y <= n; y++)
        if (a[x][y] == 1 && viz[y] == 0)
            dfs(y);
}

int main()
{
    ifstream fin("graf.in");
    int m, x, y, comp = 0;
    fin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        fin >> x >> y;
        a[x][y] = a[y][x] = 1;
    }
    for (int i = 1; i <= n; i++)
        if (viz[i] == 0)
        {
            comp++;
            dfs(i);
        }
    cout << comp;
    fin.close();
    return 0;
}

Pentru graful din exemplu, programul afișează 3: DFS pornește din 1 și marchează 1, 2, 3; apoi din 4 marchează 4, 5; apoi din 6 marchează 6, 7, 8. Graful este conex exact atunci când rezultatul este 1.

De reținut