Matricea de adiacență la BAC: grade și muchii

Matricea de adiacență a unui graf neorientat arată ce perechi de vârfuri sunt unite prin muchii. La BAC, din aceeași matrice poți afla vecinii unui vârf, gradul lui și numărul total de muchii. Trebuie însă să ții cont că fiecare muchie apare de două ori în matricea unui graf neorientat.

Lecția privește grafurile de la matematică-informatică. Folosim grafuri simple: fără bucle și fără muchii multiple între aceeași pereche de vârfuri. Vârfurile sunt etichetate de la unu la n. Verifică aceste ipoteze înainte să aplici formulele într-un subiect de BAC la informatică.

Cum se construiește matricea

Pentru fiecare pereche de vârfuri, elementul matricei este unu dacă există muchia și zero dacă nu există. Într-un graf neorientat, muchia dintre unu și trei este aceeași cu muchia dintre trei și unu. De aceea, cele două poziții simetrice din matrice au aceeași valoare.

Diagonala principală conține numai zerouri, fiindcă modelul nu permite muchii de la un vârf la el însuși. Simetria și diagonala nulă sunt două verificări diferite. O matrice poate respecta una și încălca cealaltă.

Ordinea etichetelor trebuie păstrată identic pe linii și coloane. Dacă linia a treia reprezintă vârful trei, coloana a treia trebuie să reprezinte același vârf. O schimbare de etichetare se aplică ambelor dimensiuni.

Exemplu complet cu cinci vârfuri

Considerăm muchiile dintre unu și doi, unu și trei, doi și trei, trei și patru. Vârful cinci este izolat. Matricea de adiacență este:

Vârf	1	2	3	4	5
1	0	1	1	0	0
2	1	0	1	0	0
3	1	1	0	1	0
4	0	0	1	0	0
5	0	0	0	0	0

Linia vârfului trei arată că vecinii săi sunt unu, doi și patru. Nu este vecin cu cinci și nici cu el însuși. Linia de zerouri a vârfului cinci exprimă absența oricărei muchii incidente lui.

Gradul este suma unei linii

În modelul simplu neorientat, gradul unui vârf este numărul vecinilor săi. Fiecare unu de pe linia corespunzătoare indică exact un vecin. Prin urmare, suma liniei este gradul.

În exemplu, gradele sunt doi, doi, trei, unu și zero. Vârful trei are grad maxim, iar vârful cinci este izolat. Vârful patru are un singur vecin și este un vârf de grad unu.

Din simetria matricei, suma coloanei unui vârf este aceeași cu suma liniei sale. Nu aduna linia și coloana pentru a obține gradul: ai număra fiecare muchie incidentă de două ori.

De la grade la numărul muchiilor

Fiecare muchie contribuie cu unu la gradul fiecăruia dintre cele două capete. Suma tuturor gradelor este de două ori numărul muchiilor. În exemplu, suma este opt, deci graful are patru muchii.

Aceeași numărătoare se vede în matrice. Fiecare muchie produce două valori unu, simetrice față de diagonala principală. Poți număra numai valorile unu de deasupra diagonalei sau poți împărți suma întregii matrice la doi.

Relația dintre grade și muchii este prezentată și în materialul MIT despre grafuri și conectivitate. Pentru exercițiul nostru, justificarea concretă este suficientă: fiecare muchie are exact două capete distincte.

Program C++ pentru o matrice dată

Programul citește n, între unu și o sută, și o matrice despre care enunțul garantează că reprezintă un graf simplu neorientat. Afișează gradele în ordinea vârfurilor, apoi numărul muchiilor. Nu validează separat o matrice arbitrară de intrare.

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    int grade[100] = {};
    int sumaGrade = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            int a;
            cin >> a;
            grade[i] += a;
        }
        sumaGrade += grade[i];
    }
    for (int i = 0; i < n; ++i) {
        if (i > 0) cout << ' ';
        cout << grade[i];
    }
    cout << '\n' << sumaGrade / 2;
    return 0;
}

Programul poate calcula sumele în timpul citirii, fără să memoreze întreaga matrice. Dacă ar trebui ulterior să răspundă la întrebări despre existența unor muchii, ar fi necesară păstrarea unei reprezentări potrivite.

Cum verifici o matrice suspectă

Pentru un graf simplu neorientat, fiecare element trebuie să fie zero sau unu, diagonala trebuie să fie nulă și matricea trebuie să fie simetrică. Aceste condiții sunt suficiente pentru ca matricea să descrie un asemenea graf pe etichetele date.

Dacă poziția dintre unu și trei este unu, iar poziția dintre trei și unu este zero, matricea nu respectă modelul neorientat. Nu corecta automat una dintre valori fără să verifici enunțul: poate fi vorba despre un graf orientat sau despre date eronate.

O valoare unu pe diagonală ar indica o buclă, exclusă aici. Dacă problema permite alt model, definițiile gradelor și regulile de numărare trebuie adaptate. Ipotezele nu sunt un detaliu care poate fi omis.

Ce nu poți deduce numai dintr-un grad

Gradul spune câți vecini are un vârf, nu care sunt ei. Două vârfuri cu același grad pot avea vecini diferiți. Pentru a afla etichetele vecinilor, citești pozițiile valorilor unu, nu doar suma liniei.

Nici lista gradelor nu determină întotdeauna unic graful. Pot exista grafuri diferite cu aceleași grade. În această lecție matricea este dată, deci legăturile sunt cunoscute; nu încercăm să construim un graf pornind numai de la o listă de grade.

De asemenea, absența vârfurilor izolate nu garantează conexitatea. Două triunghiuri separate au toate gradele egale cu doi, dar nu există legături între cele două grupuri. Conexitatea cere analiza accesibilității între vârfuri.

Modificarea unei muchii

Dacă adaugi o muchie inexistentă între două vârfuri distincte, schimbi două zerouri simetrice în valori unu. Gradele celor două capete cresc fiecare cu unu, iar numărul muchiilor crește cu unu.

Dacă elimini o muchie existentă, cele două valori unu devin zero. Gradele capetelor scad fiecare cu unu. Celelalte grade rămân neschimbate, chiar dacă proprietăți globale precum conexitatea se pot modifica.

Acest bilanț local este o verificare utilă pentru calcule. El leagă reprezentarea de semnificația ei și susține învățarea prin înțelegere, în locul aplicării mecanice a unei formule.

Exerciții cu răspunsuri

Matricea are șase valori unu în total. În ipotezele lecției, graful are trei muchii. Fiecare muchie este reprezentată de două ori.

O linie are numai zerouri. Vârful corespunzător este izolat și are gradul zero. Pentru un graf cu mai multe vârfuri, acest lucru exclude conexitatea întregului graf.

Adaugi în exemplul inițial muchia dintre patru și cinci. Gradele devin doi, doi, trei, doi și unu. Numărul muchiilor devine cinci, iar vârful cinci nu mai este izolat.

Graful are un singur vârf și nicio muchie. Matricea conține un singur zero, gradul este zero și numărul muchiilor este zero.

Întrebări frecvente

Număr valorile unu și sub diagonală, și deasupra ei?

Poți, dar atunci împarți totalul la doi. Dacă numeri numai deasupra diagonalei, fiecare muchie apare deja o singură dată și nu mai împarți.

O sumă pară a gradelor garantează orice listă posibilă?

Nu. Este o condiție necesară, dar realizarea unei liste de grade impune și alte constrângeri. Aici pornim de la o matrice validă, nu de la o listă arbitrară.

Cum verific o confuzie între vârf și indice?

Scrie etichetele pe liniile și coloanele tabelului, apoi marchează o muchie în ambele poziții simetrice. Pentru o explicație pe un exemplu propriu, poți consulta un profesor de informatică.