Grafuri orientate și neorientate. Terminologie

Un graf este o pereche ordonată de mulțimi G = (X, U), în care X este o mulțime finită și nevidă de elemente numite noduri sau vârfuri, iar U este o mulțime de perechi de noduri distincte. Graful descrie o relație între obiecte: nodurile sunt obiectele, iar perechile din U arată care obiecte sunt în relație.

Numărul de noduri se numește ordinul grafului și se notează cu n: n = card(X). Numărul de perechi din U se notează cu m: m = card(U). Nodurile se etichetează, de regulă, cu numerele 1, 2, …, n.

Definiția grafului

Graful neorientat și graful orientat

Grafurile se clasifică după proprietatea de simetrie a mulțimii U:

• graful neorientat — perechile din U sunt neordonate: dacă nodul x este legat de nodul y, atunci și y este legat de x;
• graful orientat — perechile din U sunt ordonate: faptul că x este în relație cu y nu implică faptul că y este în relație cu x.

Tipul grafului se alege după relația pe care o descrie. Legăturile prin cablu dintre calculatoarele unei rețele se reprezintă printr-un graf neorientat: dacă un cablu conectează calculatorul x cu calculatorul y, el conectează și calculatorul y cu x. Rezultatele meciurilor dintr-un turneu se reprezintă printr-un graf orientat, în care perechea (x, y) arată că echipa x a învins echipa y; relația nu este simetrică, fiindcă din victoria lui x asupra lui y nu rezultă victoria lui y asupra lui x.

În această lecție, o pereche neordonată se scrie între paranteze drepte, [x, y], iar o pereche ordonată între paranteze rotunde, (x, y).

Graful neorientat

Terminologie

Elementele mulțimii U ale unui graf neorientat se numesc muchii. Muchia care unește nodurile x și y se notează [x, y]; [x, y] și [y, x] sunt aceeași muchie.

Noțiunile de bază, cu exemple din graful G1:

Gradul unui nod

Într-un graf neorientat, numărul muchiilor care au o extremitate în nodul x se numește gradul nodului x și se notează d(x). După grad, se deosebesc:

• nodul terminal — are gradul 1, deci este extremitatea unei singure muchii;
• nodul izolat — are gradul 0, deci nu este adiacent cu niciun alt nod.

În graful G1, gradele nodurilor sunt:

Nodul 6 este terminal, iar nodul 7 este izolat. Într-un graf cu n noduri, gradul oricărui nod este cuprins între 0 și n − 1.

Suma gradelor. Pentru orice graf neorientat cu m muchii,

d(x1) + d(x2) + … + d(xn) = 2m

Fiecare muchie [x, y] adaugă o unitate la gradul lui x și o unitate la gradul lui y, deci contribuie cu 2 la suma gradelor. În G1 suma gradelor este 2 + 2 + 4 + 2 + 3 + 1 + 0 = 14 = 2 · 7.

Din această relație rezultă că numărul nodurilor de grad impar este par: suma gradelor este pară, deci termenii impari ai sumei sunt în număr par. În G1, nodurile de grad impar sunt 5 și 6.

Graful orientat

Terminologie

Elementele mulțimii U ale unui graf orientat se numesc arce. Arcul de la nodul x la nodul y se notează (x, y); (x, y) și (y, x) sunt arce diferite. Arcul (x, y) pleacă din extremitatea inițială x și ajunge în extremitatea finală y. Pentru graful orientat se folosește și denumirea de digraf.

Gradul intern și gradul extern

Pentru un nod x al unui graf orientat se definesc:

• gradul extern d⁺(x) — numărul arcelor care ies din x, adică numărul succesorilor lui x;
• gradul intern d⁻(x) — numărul arcelor care intră în x, adică numărul predecesorilor lui x.

Un nod cu d⁺(x) + d⁻(x) = 1 este nod terminal, iar un nod cu d⁺(x) = d⁻(x) = 0 este nod izolat.

Suma gradelor. Arcul (x, y) se numără o singură dată în gradul extern al lui x și o singură dată în gradul intern al lui y. De aici:

d⁺(x1) + … + d⁺(xn) = d⁻(x1) + … + d⁻(xn) = m

În G2 ambele sume sunt egale cu 9.

Numărul grafurilor cu n noduri

Între n noduri se pot forma n(n − 1)/2 perechi neordonate de noduri distincte:

• într-un graf neorientat, fiecare pereche este sau nu muchie, deci se pot forma 2^(n(n−1)/2) grafuri neorientate cu n noduri date;
• într-un graf orientat, pentru fiecare pereche {x, y} există patru situații: niciun arc, arcul (x, y), arcul (y, x) sau amândouă arcele; se pot forma 4^(n(n−1)/2) grafuri orientate.

Pentru n = 3 există 2³ = 8 grafuri neorientate și 4³ = 64 de grafuri orientate.

Metode de reprezentare

Pentru a fi prelucrat într-un program, graful se memorează într-o structură de date. Metodele de reprezentare se deosebesc prin memoria ocupată și prin timpul în care se obțin informațiile despre graf.

Matricea de adiacență

Matricea de adiacență a unui graf cu n noduri este matricea pătratică a, de ordinul n, cu elementele

a[i][j] = 1, dacă există muchia [i, j] (arcul (i, j))
a[i][j] = 0, altfel

Proprietățile matricei de adiacență:

• elementele de pe diagonala principală sunt 0, fiindcă o muchie unește două noduri distincte;
• la graful neorientat matricea este simetrică față de diagonala principală: a[i][j] = a[j][i];
• la graful neorientat suma elementelor este 2m, iar la graful orientat este m.

Din matricea de adiacență se citesc direct următoarele informații:

Reprezentarea ocupă n² elemente, oricâte muchii ar avea graful. Verificarea existenței unei muchii se face printr-o singură accesare, dar determinarea vecinilor unui nod cere parcurgerea întregii linii.

Matricea de incidență

Matricea de incidență a unui graf cu n noduri și m muchii are n linii, câte una pentru fiecare nod, și m coloane, câte una pentru fiecare muchie sau arc, numerotate în ordinea din mulțimea U:

graf neorientat:  a[i][k] = 1, dacă nodul i este extremitate a muchiei k
                  a[i][k] = 0, altfel

graf orientat:    a[i][k] = −1, dacă nodul i este extremitatea inițială a arcului k
                  a[i][k] =  1, dacă nodul i este extremitatea finală a arcului k
                  a[i][k] =  0, altfel

Matricea de incidență a grafului G1, cu muchiile în ordinea [1,2], [1,3], [2,3], [3,4], [3,5], [4,5], [5,6]:

Proprietățile matricei de incidență:

• la graful neorientat, fiecare coloană are exact două elemente egale cu 1, iar suma elementelor de pe linia i este gradul nodului i;
• la graful orientat, fiecare coloană are un element egal cu −1 și un element egal cu 1, deci suma tuturor elementelor este 0; pe linia i, numărul valorilor −1 este d⁺(i), iar numărul valorilor 1 este d⁻(i).

Lista muchiilor

Lista muchiilor (la graful orientat, lista arcelor) conține cele m perechi de noduri care formează muchiile. Ea se memorează într-o matrice cu m linii și 2 coloane sau într-un vector de înregistrări cu două câmpuri.

Reprezentarea ocupă 2m valori și se folosește atunci când muchiile se prelucrează una după alta, de exemplu în ordinea costurilor. La fiecare muchie se pot adăuga și alte informații, cum ar fi lungimea sau costul. Gradul unui nod este numărul aparițiilor etichetei lui în listă.

Listele de adiacență

Lista de adiacență a nodului i conține toți vecinii lui i la graful neorientat, respectiv toți succesorii lui i la graful orientat. Graful se reprezintă prin cele n liste.

Numărul total de elemente din liste este 2m la graful neorientat și m la graful orientat. La graful neorientat, lungimea listei nodului i este gradul lui; la graful orientat, este gradul extern.

Listele se pot implementa static, cu tablouri, sau dinamic, cu liste simplu înlănțuite: pentru fiecare nod se memorează adresa primului element al listei vecinilor lui.

Compararea reprezentărilor

Matricea de adiacență este potrivită pentru grafurile cu multe muchii și pentru problemele în care se verifică des existența unei muchii. Listele de adiacență sunt potrivite pentru grafurile cu multe noduri și puține muchii și pentru algoritmii care parcurg vecinii fiecărui nod, cum sunt parcurgerea în lățime și cea în adâncime.

Gradele nodurilor unui graf neorientat

Programul citește numărul de noduri, numărul de muchii și muchiile, construiește matricea de adiacență și afișează gradul fiecărui nod, suma gradelor, nodurile izolate și nodurile terminale.

Date de intrare. Pe prima linie n și m; pe fiecare dintre următoarele m linii, extremitățile unei muchii. Pentru graful G1:

7 7
1 2
1 3
2 3
3 4
3 5
4 5
5 6

#include <iostream>
using namespace std;

const int MAX = 101;
int a[MAX][MAX], n, m;

/* Citeste muchiile si construieste matricea de adiacenta. */
void citire() {
    int x, y;
    cin >> n >> m;
    for (int k = 1; k <= m; k++) {
        cin >> x >> y;
        a[x][y] = 1;                // muchia [x, y]
        a[y][x] = 1;                // este si muchia [y, x]
    }
}

/* Gradul nodului i: numarul valorilor 1 de pe linia i. */
int grad(int i) {
    int g = 0;
    for (int j = 1; j <= n; j++)
        g = g + a[i][j];
    return g;
}

/* Suma gradelor tuturor nodurilor. */
int sumaGradelor() {
    int s = 0;
    for (int i = 1; i <= n; i++)
        s = s + grad(i);
    return s;
}

/* Afiseaza nodurile care au gradul g. */
void afiseazaNoduri(int g) {
    for (int i = 1; i <= n; i++)
        if (grad(i) == g)
            cout << " " << i;
}

int main() {
    citire();
    for (int i = 1; i <= n; i++)
        cout << "d(" << i << ") = " << grad(i) << "\n";
    cout << "Suma gradelor: " << sumaGradelor() << " = 2 * " << m << "\n";
    cout << "Noduri izolate:";
    afiseazaNoduri(0);
    cout << "\nNoduri terminale:";
    afiseazaNoduri(1);
    return 0;
}

Pentru graful G1 programul afișează gradele din tabelul de mai sus, suma 14 = 2 * 7, nodul izolat 7 și nodul terminal 6. Construirea matricei cere m pași, iar calculul tuturor gradelor n² pași.

Gradele și vecinii într-un graf orientat

La graful orientat se memorează numai a[x][y] = 1 pentru arcul (x, y). Gradul extern se obține din linie, iar gradul intern din coloană.

#include <iostream>
using namespace std;

const int MAX = 101;
int a[MAX][MAX], n, m;

void citire() {
    int x, y;
    cin >> n >> m;
    for (int k = 1; k <= m; k++) {
        cin >> x >> y;
        a[x][y] = 1;                // numai arcul (x, y)
    }
}

/* Gradul extern al nodului i: arcele care ies din i (linia i). */
int gradExtern(int i) {
    int g = 0;
    for (int j = 1; j <= n; j++)
        g = g + a[i][j];
    return g;
}

/* Gradul intern al nodului i: arcele care intra in i (coloana i). */
int gradIntern(int i) {
    int g = 0;
    for (int j = 1; j <= n; j++)
        g = g + a[j][i];
    return g;
}

/* Succesorii lui i: nodurile j pentru care exista arcul (i, j). */
void afiseazaSuccesori(int i) {
    for (int j = 1; j <= n; j++)
        if (a[i][j] == 1)
            cout << " " << j;
}

/* Predecesorii lui i: nodurile j pentru care exista arcul (j, i). */
void afiseazaPredecesori(int i) {
    for (int j = 1; j <= n; j++)
        if (a[j][i] == 1)
            cout << " " << j;
}

int main() {
    citire();
    for (int i = 1; i <= n; i++) {
        cout << "Nodul " << i << ": d+ = " << gradExtern(i)
             << ", d- = " << gradIntern(i);
        cout << "; succesori:";
        afiseazaSuccesori(i);
        cout << "; predecesori:";
        afiseazaPredecesori(i);
        cout << "\n";
    }
    return 0;
}

Listele de adiacență implementate dinamic

Fiecare listă este o listă simplu înlănțuită. Elementul L[i] memorează adresa primului element din lista vecinilor nodului i, iar un vecin nou se adaugă la începutul listei.

#include <iostream>
using namespace std;

struct nod {
    int info;                       // eticheta vecinului
    nod *urm;                       // adresa urmatorului element
};

nod *L[101];                        // L[i] = inceputul listei nodului i
int n, m;

/* Adauga nodul y la inceputul listei care porneste din prim. */
void adauga(nod *&prim, int y) {
    nod *p = new nod;
    p->info = y;
    p->urm = prim;
    prim = p;
}

/* Citeste muchiile si construieste listele de adiacenta. */
void citire() {
    int x, y;
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        L[i] = NULL;
    for (int k = 1; k <= m; k++) {
        cin >> x >> y;
        adauga(L[x], y);            // y devine vecin al lui x
        adauga(L[y], x);            // x devine vecin al lui y
    }
}

/* Gradul nodului i: numarul elementelor din lista lui. */
int grad(int i) {
    int g = 0;
    for (nod *p = L[i]; p != NULL; p = p->urm)
        g++;
    return g;
}

int main() {
    citire();
    for (int i = 1; i <= n; i++) {
        cout << "Vecinii nodului " << i << ":";
        for (nod *p = L[i]; p != NULL; p = p->urm)
            cout << " " << p->info;
        cout << " (grad " << grad(i) << ")\n";
    }
    return 0;
}

La graful orientat se adaugă numai y în lista lui x. Fiecare vecin nou se așază la începutul listei, deci vecinii se afișează în ordinea inversă citirii: pentru nodul 3 al grafului G1 se afișează 5 4 2 1.

Lanțul

Un lanț este o succesiune de noduri L = (x1, x2, …, xk) în care oricare două noduri consecutive sunt adiacente: [x1,x2], [x2,x3], …, [xk−1,xk] ∈ U.

• nodurile x1 și xk sunt extremitățile lanțului;
• lungimea lanțului este numărul de muchii parcurse, adică k − 1; o muchie parcursă de mai multe ori se numără de fiecare dată;
• dacă există un lanț de la x la y, se spune că nodul y este accesibil din nodul x.

Lanțul se definește și în graful orientat: acolo nu se ține seama de sensul arcelor, ci doar de faptul că două noduri consecutive sunt legate printr-un arc.

După noduri și după muchii, lanțurile se clasifică astfel:

Exemple în graful G1:

• (1, 3, 5, 6) este lanț elementar, de lungime 3;
• (2, 3, 4, 5, 3, 1) este lanț simplu, fiindcă muchiile [2,3], [3,4], [4,5], [5,3] și [3,1] sunt distincte, dar neelementar, fiindcă nodul 3 apare de două ori;
• (1, 2, 3, 1, 2) este lanț compus, fiindcă muchia [1,2] se parcurge de două ori;
• (1, 4, 5) nu este lanț, fiindcă nodurile 1 și 4 nu sunt adiacente.

Între tipurile de lanțuri există următoarele legături:

• orice lanț elementar este simplu. Dacă o muchie [x, y] s-ar parcurge de două ori, nodurile x și y ar apărea de două ori în lanț;
• dacă un graf conține un lanț de la x la y, atunci conține și un lanț elementar de la x la y. Dacă un nod z se repetă, porțiunea de lanț dintre două apariții ale lui z se elimină, iar operația se repetă până nu mai rămâne niciun nod repetat.

Ciclul

Un ciclu este un lanț simplu ale cărui extremități coincid: C = (x1, x2, …, xk), cu muchiile distincte două câte două și x1 = xk.

Un ciclu elementar este un ciclu (x1, x2, …, xk) în care nodurile x1, …, xk−1 sunt distincte două câte două; singura repetare este xk = x1. Un graf care nu conține niciun ciclu se numește graf aciclic.

Exemple în graful G1:

• (3, 4, 5, 3) este ciclu elementar, de lungime 3;
• (1, 2, 3, 4, 5, 3, 1) este ciclu neelementar: muchiile sunt distincte, dar nodul 3 apare în interiorul ciclului;
• (1, 2, 1) nu este ciclu: extremitățile coincid, dar muchia [1,2] se parcurge de două ori.

Într-un graf neorientat, un ciclu are lungimea cel puțin 3: un lanț închis de lungime 2, de forma (x, y, x), parcurge de două ori muchia [x, y].

Drumul

Într-un graf orientat, un drum este o succesiune de noduri D = (x1, x2, …, xk) în care oricare două noduri consecutive sunt legate printr-un arc orientat de la primul la al doilea: (xi, xi+1) ∈ U, pentru i = 1, …, k − 1. Drumul este, așadar, un lanț parcurs în sensul arcelor.

• lungimea drumului este numărul arcelor care îl compun; dacă arcele au asociate lungimi sau costuri, lungimea drumului este suma acestora;
• drumul elementar are nodurile distincte două câte două;
• drumul simplu are arcele distincte două câte două;
• dacă există un drum de la x la y, nodul y este accesibil din x.

Exemple în graful G2:

• (1, 4, 5, 6) este drum elementar, de lungime 3;
• (2, 3, 4, 5, 3, 1) este drum simplu, fiindcă arcele (2,3), (3,4), (4,5), (5,3) și (3,1) sunt distincte, dar neelementar, fiindcă nodul 3 se repetă;
• (5, 6, 5, 6) nu este drum simplu, fiindcă arcul (5,6) se parcurge de două ori;
• (1, 3) nu este drum, fiindcă arcul are sensul (3,1); este însă lanț.

Ca la lanțuri, orice drum elementar este simplu, iar dacă există un drum de la x la y, există și un drum elementar de la x la y.

Circuitul

Un circuit este un drum simplu ale cărui extremități coincid: C = (x1, x2, …, xk), cu arcele distincte două câte două și x1 = xk.

Un circuit elementar este un circuit în care nu se repetă niciun nod, în afară de nodul de plecare, care este și nodul de sosire.

Exemple în graful G2:

• (1, 2, 3, 1) este circuit elementar, de lungime 3;
• (5, 6, 5) este circuit elementar, de lungime 2: arcele (5,6) și (6,5) sunt distincte;
• (1, 2, 3, 4, 5, 3, 1) este circuit neelementar: arcele sunt distincte, dar nodul 3 se repetă;
• (5, 6, 5, 6, 5) nu este circuit, fiindcă arcele (5,6) și (6,5) se parcurg de câte două ori.

Spre deosebire de ciclul unui graf neorientat, un circuit poate avea lungimea 2, dacă între două noduri există arce în ambele sensuri.

Lanț, ciclu, drum, circuit

Noțiunile se construiesc una din alta, după două criterii: dacă se ține seama de sensul arcelor și dacă extremitățile coincid.

Pentru fiecare dintre ele, varianta elementară cere noduri distincte, iar la ciclu și la circuit excepția este nodul de la capete.

Verificarea unui șir de noduri

Programul citește un graf neorientat și un șir de k noduri (k ≥ 2) și stabilește ce reprezintă șirul: nu este lanț, lanț elementar, lanț simplu neelementar, lanț compus, ciclu elementar sau ciclu neelementar.

Verificarea se face în trei pași:

1. este lanț — pentru fiecare două noduri consecutive se verifică a[v[i]][v[i+1]] = 1;
2. este simplu — fiecare muchie parcursă se marchează în matricea folosit; dacă se ajunge la o muchie deja marcată, lanțul nu este simplu;
3. este elementar — se compară nodurile două câte două; la un lanț închis, ultimul nod nu intră în comparație, fiindcă el coincide cu primul.

Date de intrare. Graful, în forma de la programul pentru grade, apoi k și cele k noduri ale șirului.

#include <iostream>
using namespace std;

const int MAX = 101;
int a[MAX][MAX], folosit[MAX][MAX], v[MAX], n, m, k;

void citire() {
    int x, y;
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        cin >> x >> y;
        a[x][y] = a[y][x] = 1;
    }
    cin >> k;
    for (int i = 1; i <= k; i++)
        cin >> v[i];
}

/* 1. Oricare doua noduri consecutive trebuie sa fie adiacente. */
int esteLant() {
    for (int i = 1; i < k; i++)
        if (a[v[i]][v[i + 1]] == 0)
            return 0;
    return 1;
}

/* 2. Nicio muchie nu se parcurge de doua ori; muchiile parcurse
   se marcheaza in matricea folosit. */
int esteSimplu() {
    for (int i = 1; i < k; i++) {
        if (folosit[v[i]][v[i + 1]] == 1)
            return 0;
        folosit[v[i]][v[i + 1]] = 1;
        folosit[v[i + 1]][v[i]] = 1;    // aceeasi muchie, in sens invers
    }
    return 1;
}

/* 3. Niciun nod nu se repeta; la lantul inchis, ultimul nod nu se
   compara, fiindca el coincide cu primul. */
int esteElementar() {
    int ultim = k;
    if (v[1] == v[k])
        ultim = k - 1;
    for (int i = 1; i < ultim; i++)
        for (int j = i + 1; j <= ultim; j++)
            if (v[i] == v[j])
                return 0;
    return 1;
}

int main() {
    citire();
    if (!esteLant())
        cout << "nu este lant";
    else if (v[1] == v[k]) {            // lant inchis
        if (!esteSimplu())
            cout << "lant inchis, dar nu este ciclu";
        else if (esteElementar())
            cout << "ciclu elementar";
        else
            cout << "ciclu neelementar";
    } else {
        if (esteElementar())
            cout << "lant elementar";
        else if (esteSimplu())
            cout << "lant simplu, neelementar";
        else
            cout << "lant compus";
    }
    return 0;
}

Pentru graful G1, programul dă următoarele rezultate:

Pentru un graf orientat, același program verifică drumurile și circuitele, cu două modificări: matricea a se construiește numai cu a[x][y] = 1, iar la marcarea arcului parcurs se șterge atribuirea pentru sensul invers, fiindcă (x, y) și (y, x) sunt arce diferite.

Graful parțial

Un graf parțial al grafului G = (X, U) este un graf Gp = (X, V) cu V ⊆ U: are aceleași noduri ca G și numai o parte dintre muchiile lui. Se obține din G prin eliminarea unor muchii sau arce.

Pentru fiecare dintre cele m muchii se alege dacă rămâne sau nu în graful parțial, deci un graf cu m muchii are 2^m grafuri parțiale, printre care și graful însuși (V = U) și graful fără muchii (V = ∅). Graful G1 are 2⁷ = 128 de grafuri parțiale.

În matricea de adiacență, graful parțial se obține punând 0 în locul valorilor 1 care corespund muchiilor eliminate: a[3][4] = a[4][3] = 0 și a[5][6] = a[6][5] = 0.

Subgraful

Fie graful G = (X, U) și o mulțime nevidă de noduri Y ⊆ X. Graful Gs = (Y, V), în care V conține toate muchiile din U care au ambele extremități în Y, se numește subgraf al grafului G. Se spune că subgraful este generat de mulțimea de noduri Y. El se obține din G prin eliminarea unor noduri și a tuturor muchiilor incidente cu acestea.

Un subgraf este determinat de mulțimea lui de noduri. Un graf cu n noduri are 2ⁿ − 1 submulțimi nevide de noduri, deci 2ⁿ − 1 subgrafuri. Graful G1 are 2⁷ − 1 = 127 de subgrafuri.

Graful ({1, 2, 3}, {[1,2], [1,3]}) nu este subgraf al lui G1: nodurile 2 și 3 sunt în mulțime, dar muchia [2,3] dintre ele lipsește.

Graful parțial și subgraful

Graful parțial se obține eliminând muchii, iar subgraful se obține eliminând noduri, împreună cu muchiile lor.

Graful transpus

Fie graful orientat G = (X, U). Graful transpus al lui G este graful Gᵗ = (X, Uᵗ), în care Uᵗ = {(y, x) | (x, y) ∈ U}. El are aceleași noduri ca G, iar fiecare arc are sensul inversat.

Proprietățile grafului transpus:

• matricea de adiacență a lui Gᵗ este transpusa matricei de adiacență a lui G: aᵗ[i][j] = a[j][i];
• succesorii unui nod în Gᵗ sunt predecesorii lui în G, deci gradul extern și gradul intern își schimbă rolurile;
• există drum de la x la y în Gᵗ dacă și numai dacă există drum de la y la x în G.

Ultima proprietate se folosește la determinarea componentelor tare conexe: un nod y este în aceeași componentă cu x dacă este accesibil din x atât în G, cât și în Gᵗ.

Terminologia grafurilor la examen

În programa de concurs

Noțiunile sunt trecute anume în programele de examen, și la Definitivat, și la Titularizare, la capitolul Teoria grafurilor:

grafuri orientate și neorientate: definiție, metode de reprezentare, terminologie (grad, adiacență, incidență, lanț, lanț elementar, lanț simplu, drum, drum elementar, drum simplu, ciclu, ciclu elementar, circuit, circuit elementar, graf parțial, subgraf, graf transpus)

Ce s-a dat până acum

Terminologia a fost cerută ca temă o singură dată în variantele din arhivă, la Definitivat 2026. Mult mai des, ea apare ca noțiuni preliminare la prezentarea unui algoritm pe grafuri, la Subiectul I:

Variantele din arhivă sunt, de regulă, câte una pe an; celelalte variante ale acelorași ani pot să difere.

Ce punctează baremul

La Definitivat 2026, cele 15 puncte se împart astfel:

La subiectele în care noțiunile sunt preliminare, fiecare definiție valorează de obicei 1 punct: „definiții preliminare, conform cerinței 3 × 1p = 3p” la Titularizare 2016, „noțiuni preliminarii, conform cerinței 3 × 1p = 3p” la Titularizare 2024. Punctele acestea se pierd des, fiindcă definițiile se scriu în grabă, înaintea algoritmului.

Rezolvarea completă a subiectului de la Definitivat 2026 este în pagina Grafuri orientate.

Greșeli frecvente

1. Se definește ciclul ca „lanț cu extremitățile egale”, fără condiția ca muchiile să fie distincte. Cu această definiție, (1, 2, 1) ar fi ciclu.
2. Se definește circuitul fără condiția de drum simplu, deși baremul de la Definitivat 2026 o cere explicit.
3. Se confundă lanțul elementar cu lanțul simplu: elementar se referă la noduri, simplu se referă la muchii.
4. Se afirmă că orice lanț simplu este elementar. Implicația este inversă: orice lanț elementar este simplu.
5. La ciclul elementar se cere ca toate nodurile să fie distincte, uitând excepția primului și a ultimului nod, care coincid.
6. Se confundă graful parțial cu subgraful. Graful parțial păstrează toate nodurile; subgraful păstrează toate muchiile dintre nodurile rămase.
7. La subgraf se elimină un nod, dar rămâne o muchie incidentă cu el, sau se elimină o muchie dintre două noduri păstrate.
8. La graful neorientat se completează numai a[x][y] = 1, fără a[y][x] = 1, iar matricea nu mai este simetrică.
9. La graful orientat se calculează gradul intern pe linie în loc de coloană.
10. Se afirmă că suma elementelor matricei de adiacență a unui graf neorientat este m. Ea este 2m, fiindcă fiecare muchie apare de două ori.
11. Se folosește matricea de incidență a grafului neorientat pentru un graf orientat, fără valorile −1, iar sensul arcelor se pierde.

Verificare rapidă

Folosește întrebările următoare înainte să consideri rezolvarea terminată:

• Am precizat dacă graful este neorientat sau orientat și am folosit „muchie”, respectiv „arc”?
• Definiția ciclului și a circuitului conține condiția ca muchiile, respectiv arcele, să fie distincte?
• La noțiunile elementare am precizat excepția extremităților care coincid?
• Fiecare definiție are un exemplu verificat pe un graf dat explicit?
• Exemplul pentru „drum simplu” este neelementar, ca să se vadă deosebirea față de drumul elementar?
• La graful parțial și la subgraf am spus ce se elimină: muchii, respectiv noduri împreună cu muchiile lor?

Exerciții de fixare

1. Scrie matricea de adiacență, matricea de incidență și listele de adiacență pentru graful neorientat cu nodurile 1, 2, 3, 4, 5 și muchiile [1,2], [1,4], [2,3], [2,4], [3,5], [4,5].
2. Pentru graful de la exercițiul 1, dă câte un exemplu de lanț elementar de lungime 4, lanț simplu neelementar, ciclu elementar de lungime 3 și ciclu elementar de lungime 5.
3. Scrie un program care citește o matrice pătratică și verifică dacă este binară, are zero pe diagonala principală și este simetrică, adică dacă reprezintă un graf neorientat.
4. Scrie un program care citește lista arcelor unui graf orientat și afișează lista arcelor grafului transpus și nodurile care au gradul intern egal cu gradul extern.
5. Scrie un program care citește matricea de adiacență a unui graf neorientat și o mulțime de noduri Y, apoi afișează muchiile subgrafului generat de Y.
6. Modifică programul de verificare a unui șir de noduri astfel încât să lucreze pe un graf orientat și să afișeze: nu este drum, drum elementar, drum simplu neelementar, drum compus, circuit elementar sau circuit neelementar.
7. Câte grafuri parțiale și câte subgrafuri are un graf neorientat cu 5 noduri și 6 muchii? Justifică fiecare număr.