SISergiu Ilincameditații informatică
Meniu

clasa a XI-a · Grafuri · lecția 9

Grafuri neorientate (1): noțiuni de bază, grad, reprezentări

60 minmate-info

Înainte de lecția asta: X.8 Tablouri bidimensionale (matrice): declarare, parcurgere pe linii și coloane

Ce vei ști după lecție

  • Cunoști terminologia: vârf (nod), muchie, adiacență, incidență, grad, vârf izolat, vârf terminal.
  • Aplici formula sumei gradelor și numărul maxim de muchii.
  • Reprezinți un graf prin matrice de adiacență, liste de adiacență și lista muchiilor.
  • Recunoști lanțuri, cicluri, subgrafuri și grafuri parțiale.

Lecția are și o fișă de lucru, de rezolvat după ce o citești. Mergi la fișă ↓

Clasa a XI-aLecția 9 din 21 · mai sunt 12Urmează: XI.10 · Grafuri neorientate (2): conexitate, graf complet, bipartit, hamiltonian, eulerianVezi toate lecțiile
Cuprins

Fișiere PDF și de lucru

1. Ce este un graf

Un graf modelează lucruri legate între ele: orașe unite prin drumuri, elevi care sunt prieteni, calculatoare dintr-o rețea, pagini web cu legături. Nu contează cum arată desenul, ci cine cu cine este legat.

Un graf neorientat G = (V, E) are:

  • vârfuri (noduri) V = {1, 2, …, n};
  • muchii E: fiecare muchie leagă două vârfuri, [x, y]. Muchia [x, y] este aceeași cu [y, x] (drumul merge în ambele sensuri).

Exemplu: n = 5, muchiile [1,2], [1,3], [2,3], [3,4]. Vârful 5 nu e legat de nimeni.

Graful exemplu

Termen Definiție În exemplu
vârfuri adiacente legate printr-o muchie 1 și 2
muchie incidentă cu x muchie care îl conține pe x [3,4] e incidentă cu 3 și cu 4
gradul lui x, d(x) numărul de muchii incidente cu x d(3) = 3
vârf izolat grad 0 5
vârf terminal grad 1 4

Sfat

Gradul = „câți vecini are”. Pe desen: numeri liniile care pleacă din vârf.

2. Suma gradelor: formula care apare la fiecare Bac

Gradele

Suma gradelor = 2 · m. De ce: fiecare muchie are două capete, deci contribuie cu 1 la gradul fiecăruia dintre cele două vârfuri, adică 2 în total.

La BAC

  • Σ d(x) = 2m; de aici, numărul de vârfuri cu grad impar este întotdeauna par.
  • Numărul maxim de muchii: n(n − 1)/2 (fiecare pereche de vârfuri este legată: graf complet).
  • Numărul de grafuri distincte cu n vârfuri etichetate: 2^(n(n−1)/2) (fiecare pereche are muchie sau nu).

Cum se folosesc:

Întrebare Raționament Răspuns
Graf cu 7 vârfuri, gradele 1, 2, 2, 3, 3, 4, x. Ce poate fi x? 15 + x trebuie să fie par, deci x impar; x ≤ 6 1, 3 sau 5
Graf complet cu 20 de muchii? n(n−1)/2 = 20 nu are soluție întreagă (n = 6 dă 15, n = 7 dă 21) nu există
Un graf are 10 vârfuri și toate au gradul 3. Câte muchii? 10 · 3 / 2 15
Câte grafuri cu 4 vârfuri (etichetate)? 2^(4·3/2) = 2⁶ 64

3. Trei moduri de a păstra un graf în memorie

3.1 Matricea de adiacență

a[i][j] = 1 dacă [i, j] este muchie, altfel 0.

Matricea

  • este simetrică față de diagonala principală (muchia e în ambele sensuri);
  • diagonala conține doar 0 (nu există muchii de la un vârf la el însuși);
  • gradul lui i = suma liniei i; numărul de muchii = (numărul de 1) / 2.

3.2 Listele de adiacență

Pentru fiecare vârf, lista vecinilor lui.

Listele

3.3 Lista muchiilor

Un șir de perechi (x, y), exact forma în care se citesc datele: [1,2] [1,3] [2,3] [3,4].

De știut

Care alegi? Matricea: simplă, răspunde în O(1) la „există muchia [i, j]?”, dar ocupă n² (bună pentru n ≤ 1000). Listele: ocupă doar 2m, parcurgerea vecinilor unui vârf e rapidă (bune pentru grafuri mari cu puține muchii). La Bac cele mai frecvente sunt matricea și listele.

Citirea grafului: din muchii în matrice

Intrarea: n m, apoi m perechi x y. Programul de mai jos construiește matricea și afișează gradele.

#include <iostream>
using namespace std;

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

int main()
{
    cin >> n >> m;
    for (int k = 1; k <= m; k++)
    {
        int x, y;
        cin >> x >> y;
        a[x][y] = a[y][x] = 1;         // muchia merge în ambele sensuri
    }
    for (int i = 1; i <= n; i++)
    {
        int grad = 0;
        for (int j = 1; j <= n; j++) grad += a[i][j];
        cout << grad << ' ';
    }
    return 0;
}

De ce așa?

De ce a[x][y] = a[y][x] = 1? Muchia [x, y] este aceeași cu [y, x]. Dacă am nota doar a[x][y], matricea nu ar mai fi simetrică și gradul lui y ar ieși greșit. De ce suma pe linie? a[i][j] = 1 exact pentru vecinii j ai lui i; numărând 1-urile de pe linia i numărăm vecinii.

Trace pentru primele două muchii (1 2 și 1 3) și gradul vârfului 3:

Pas citit a[x][y] a[y][x] grad(3) după parcurgerea liniei 3
1 1 2 a[1][2] = 1 a[2][1] = 1
2 1 3 a[1][3] = 1 a[3][1] = 1
3 2 3 a[2][3] = 1 a[3][2] = 1
4 3 4 a[3][4] = 1 a[4][3] = 1 linia 3 = 1 + 1 + 0 + 1 + 0 = 3

Aceleași date, cu liste de adiacență

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

vector<int> L[101];
int n, m;

int main()
{
    cin >> n >> m;
    for (int k = 1; k <= m; k++)
    {
        int x, y;
        cin >> x >> y;
        L[x].push_back(y);
        L[y].push_back(x);
    }
    for (int i = 1; i <= n; i++)
    {
        cout << i << ":";
        for (int j = 0; j < (int)L[i].size(); j++) cout << ' ' << L[i][j];
        cout << '\n';
    }
    return 0;
}

De ce așa?

De ce L[i].size() este gradul? Lista lui i conține exact vecinii lui i. De ce push_back de două ori? Tot pentru că muchia merge în ambele sensuri: y e vecin al lui x și x e vecin al lui y.

Din matrice: câte muchii, care vârfuri sunt izolate

#include <iostream>
using namespace std;

int a[101][101], n;

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) cin >> a[i][j];

    int suma = 0;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) suma += a[i][j];
    cout << suma / 2 << '\n';                       // m = (suma gradelor) / 2

    for (int i = 1; i <= n; i++)
    {
        int grad = 0;
        for (int j = 1; j <= n; j++) grad += a[i][j];
        if (grad == 0) cout << i << ' ';            // vârf izolat
    }
    return 0;
}

De ce așa?

De ce împărțim la 2? Fiecare muchie apare de două ori în matrice (în a[i][j] și în a[j][i]). Suma tuturor valorilor este suma gradelor, deci 2m.

Intrare / ieșire

Intrare Ieșire
5 4
1 2
1 3
2 3
3 4
2 2 3 1 0 (gradele)
aceeași intrare, listele de adiacență 1: 2 3
2: 1 3
3: 1 2 4
4: 3
5:

4. Lanțuri și cicluri

  • lanț: șir de vârfuri x₁, x₂, …, xₖ în care oricare două consecutive sunt adiacente; lungimea = numărul de muchii (k − 1);
  • lanț elementar: vârfurile sunt distincte;
  • ciclu: lanț cu primul vârf = ultimul și muchii distincte; ciclu elementar: vârfurile distincte (în afară de primul = ultimul).

Lanț și ciclu

Atenție — greșeli frecvente

Un ciclu are cel puțin 3 vârfuri distincte: 1, 2, 1 nu e ciclu (folosește aceeași muchie de două ori).

5. Subgraf și graf parțial

Parțial și subgraf

  • graf parțial: aceleași vârfuri, se elimină unele muchii;
  • subgraf: se elimină unele vârfuri, iar odată cu ele dispar toate muchiile incidente.

Sfat

Reține: „parțial” = păstrez toate nodurile (scot doar muchii). „subgraf” = scot noduri. Un graf cu m muchii are 2ᵐ grafuri parțiale (fiecare muchie rămâne sau nu), inclusiv el însuși și graful fără muchii.

6. Greșeli frecvente

Greșeala Efect Corect
a[x][y] = 1; fără a[y][x] = 1; matrice nesimetrică, grade greșite ambele
int a[100][100] cu n = 100 indici 1..100, depășire a[101][101]
gradul = numărul de 1 din toată matricea număr de 2m, nu d(i) suma liniei i
m = suma gradelor de două ori prea mult m = suma / 2
confuzia parțial / subgraf răspuns greșit la grilă parțial = scot muchii
ciclu 1, 2, 1 nu e ciclu cel puțin 3 vârfuri

7. La BAC

La BAC

La Subiectul I apar mai ales: „care este gradul maxim / minim”, „câte muchii are graful dat prin matrice/liste”, „care vârfuri sunt izolate / terminale”, „care dintre șirurile următoare poate fi șirul gradelor” (suma pară, fiecare grad ≤ n − 1), „câte grafuri parțiale / distincte există”. Se rezolvă cu formulele din secțiunea 2: scrii gradele, aplici suma = 2m, verifici.

8. Exersează pe hârtie

Răspunsurile sunt la finalul paginii: încearcă întâi singur.

1. Un graf are 6 vârfuri cu gradele 3, 3, 2, 2, 1, x. Câte valori poate lua x (0 ≤ x ≤ 5)? Care?

2. Care este numărul maxim de muchii ale unui graf cu 9 vârfuri? Dar dacă vârful 1 este izolat?

3. Un graf cu 8 vârfuri este regulat de grad 3. Câte muchii are?

4. Câte grafuri parțiale are un graf cu 5 muchii?

5. Desenează graful dat prin matricea de adiacență:

0 1 0 1
1 0 1 0
0 1 0 0
1 0 0 0

Câte muchii are? Care sunt vârfurile terminale?

6. Scrie listele de adiacență pentru graful cu n = 4 și muchiile [1,2], [1,3], [1,4], [3,4].

7. (BAC) Poate fi șirul 4, 3, 3, 2, 2 secvența gradelor unui graf cu 5 vârfuri? Dar 4, 4, 4, 1, 1?

8. Câte grafuri neorientate distincte (cu vârfurile etichetate 1..n) există pentru n = 5?

9. Un graf are 8 vârfuri și 14 muchii, iar fiecare vârf are gradul 3 sau 4. Câte vârfuri au gradul 4?

10. Scrie un program care citește n, m și muchiile și afișează vârfurile de grad maxim.

9. Mai departe (pentru cine vrea mai mult)

Teorema „strângerilor de mână”. Numărul de persoane care au dat mâna cu un număr impar de persoane este par: este exact faptul că numărul de vârfuri de grad impar este par.

Secvența gradelor: testul lui Havel-Hakimi. Un șir de grade (sortat descrescător) d₁ ≥ d₂ ≥ … este valid dacă, scăzând 1 din următoarele d₁ valori și eliminând d₁, șirul rămas este valid. Exemplu: 3, 3, 2, 2, 2 → scoți 3, scazi 1 din următoarele 3: 2, 1, 1, 2 → sortezi 2, 2, 1, 1 → scoți 2: 1, 0, 1 → sortezi 1, 1, 0 → scoți 1: 0, 0 → valid.

Grafuri mari. Pentru n = 100 000 matricea nu încape în memorie (10¹⁰ elemente); se folosesc doar listele de adiacență.

Multigrafuri și bucle. Dacă două vârfuri au mai multe muchii sau o muchie se întoarce în același vârf, nu mai avem graf „simplu”; matricea ar conține numere > 1 sau valori pe diagonală.

Rezumat

  • Graf = vârfuri + muchii; gradul = numărul de vecini; izolat = grad 0; terminal = grad 1.
  • Σ grade = 2m; m maxim = n(n−1)/2; grafuri distincte cu n vârfuri: 2^(n(n−1)/2).
  • Matricea: simetrică, diagonala 0, gradul = suma liniei. Listele: L[x].push_back(y) și L[y].push_back(x).
  • Graf parțial = scot muchii; subgraf = scot vârfuri.

Fișa de lucru

Ai citit lecția? Printează fișa sau deschide-o pe ecran și rezolvă exercițiile în ordine.

Fișă de lucru · 6 pagini · 100 min

Grafuri neorientate

  • Citești un graf din matrice sau din lista de muchii și afli rapid grade, muchii, componente.
  • Rezolvi itemii de BAC cu formule: muchii de adăugat/eliminat, grafuri parțiale, subgrafuri, șiruri de grade.
  • Recunoști și testezi în cod grafurile conexe, bipartite, euleriene și hamiltoniene.

Fișa acoperă și: XI.10

Te-ai blocat la un exercițiu?

Probleme de lucru

Începe cu acestea, în ordine. Problemele se deschid pe pbinfo.ro, unde trimiți soluția și primești punctajul.

  • adiacenta#412

    ușoară
  • listavecini#414

    ușoară
  • grade#416

    ușoară

Temă

Rezolvă-le singur și bifează ce ai terminat. Bifele rămân salvate în acest browser.

  • adiacenta1#413

    ușoară
  • gradmax#417

    ușoară
  • izolate#430

    ușoară
  • subgraf#418

    ușoară
  • graf-partial#420

    ușoară
  • veriflant#474

    ușoară
  • matad#2707

    ușoară

Pentru cei care vor mai mult

  • gradek#4068

    ușoară

Grile din subiectele de BAC

Exerciții de tip grilă din variantele de Bacalaureat. Se rezolvă pe pbinfo.ro, care îți verifică imediat răspunsul.

Citește și exersează în plus

Te-ai blocat la lecția asta?

Scrie-mi ce nu iese și vedem împreună de unde se blochează.

Răspunsuri

Exersează pe hârtie

1. Suma 3+3+2+2+1+x = 11 + x trebuie să fie pară, deci x impar: x ∈ {1, 3, 5} (3 valori).

2. Maxim 9·8/2 = 36. Cu vârful 1 izolat: 8·7/2 = 28.

3. Suma gradelor 8·3 = 24, deci m = 24/2 = 12.

4. 2⁵ = 32 grafuri parțiale.

5. Muchii: [1,2], [1,4], [2,3] → 3 muchii (numărul de 1 este 6). Gradele: 2, 2, 1, 1. Vârfuri terminale: 3 și 4.

6. L[1]: 2 3 4, L[2]: 1, L[3]: 1 4, L[4]: 1 3.

7. 4, 3, 3, 2, 2: suma 14 (pară), ținând cont că vârful de grad 4 e legat de toate celelalte, restul rămâne 2, 2, 1, 1 → valid, deci da. 4, 4, 4, 1, 1: trei vârfuri de grad 4 sunt legate de toate, deci fiecare din celelalte două are gradul cel puțin 3: nu.

8. 2^(5·4/2) = 2¹⁰ = 1024.

9. Suma gradelor = 2 · 14 = 28. Dacă toate cele 8 vârfuri ar avea gradul 3, suma ar fi 24; fiecare vârf de grad 4 adaugă 1, deci sunt 28 − 24 = 4 vârfuri de grad 4 (și 4 de grad 3).

10. Calculezi gradele, găsești maximul, apoi afișezi toate vârfurile cu acel grad:

int gr[101], mx = 0;
// calculează gr[i] ca suma liniei i (sau L[i].size())
for (int i = 1; i <= n; i++) if (gr[i] > mx) mx = gr[i];
for (int i = 1; i <= n; i++) if (gr[i] == mx) cout << i << ' ';