Capitolul 16 · Lecția 16.1 din 3

Grafuri neorientate: terminologie

Nod, muchie, adiacență, incidență, grad, lanț, ciclu, subgraf și graf parțial.

Capitolul 16: Grafuri neorientate

Pe această pagină4 secțiuni

Ce este un graf neorientat

Un graf neorientat $G = (V, E)$ are o mulțime de noduri (vârfuri) $V$ și o mulțime de muchii $E$ . O muchie leagă două noduri și nu are sens: $[x, y]$ și $[y, x]$ sunt aceeași muchie.

Terminologia cerută de programă

Nod (vârf): element al mulțimii $V$ .
Muchie: pereche neordonată de noduri distincte.
Adiacență: două noduri sunt adiacente dacă între ele există muchie.
Incidență: o muchie este incidentă cu nodurile pe care le unește.
Grad ( $d(x)$ ): numărul de muchii incidente cu nodul $x$ . Un nod cu gradul 0 se numește izolat, cu gradul 1 terminal.
Lanț: succesiune de noduri în care oricare două consecutive sunt adiacente.
Lanț elementar: lanț în care niciun nod nu se repetă.
Ciclu: lanț în care primul nod coincide cu ultimul, cu cel puțin 3 muchii distincte.
Ciclu elementar: ciclu în care nu se repetă niciun nod, în afară de primul și ultimul.
Lungime: numărul de muchii din lanț sau ciclu, nu numărul de noduri.
Subgraf: se obține eliminând noduri și toate muchiile incidente cu ele.
Graf parțial: se obține eliminând doar muchii; nodurile rămân toate.

Teorema gradelor

$\sum_{x \in V} d(x) = 2 \cdot m$

Suma gradelor tuturor nodurilor este dublul numărului de muchii, pentru că fiecare muchie contribuie cu 1 la gradul fiecăruia dintre cele două capete.

Consecință: suma gradelor e întotdeauna pară, iar numărul nodurilor de grad impar e par.

Reține

Diferența subgraf / graf parțial se cere aproape la fiecare examen. Subgraf: scoți noduri. Graf parțial: scoți doar muchii.

Greșeli frecvente

Se numără lungimea în noduri. Se numără în muchii: un lanț cu 4 noduri are lungimea 3.
Se confundă subgraful cu graful parțial.
Se uită că într-un graf neorientat muchia nu are sens, deci matricea de adiacență e simetrică.

Exemplul, în 4 limbaje

Alege limbajul în care dai examenul. Poți edita codul și îl poți rula direct aici. Programa oficiala de BAC (proba E.d) cere Pascal sau C/C++, la alegere. Python apare in manualele noi si e pus aici pentru inteles, nu ca limbaj de examen.

#include <iostream>
using namespace std;

int main() {
    int n, m, a[101][101] = {0};
    cin >> n >> m;
    for (int k = 0; k < m; k++) {
        int x, y;
        cin >> x >> y;
        a[x][y] = a[y][x] = 1;
    }

    int suma = 0, izolate = 0, terminale = 0;
    for (int i = 1; i <= n; i++) {
        int g = 0;
        for (int j = 1; j <= n; j++) g += a[i][j];
        suma += g;
        if (g == 0) izolate++;
        if (g == 1) terminale++;
    }

    cout << "suma gradelor=" << suma << " muchii=" << suma / 2;
    cout << " izolate=" << izolate << " terminale=" << terminale;
    return 0;
}

Date de intrarese trimit programului la citire

Instrumente pentru lecția asta

Laborator de grafuri

Construiește graful apăsând pe noduri și vezi pe loc matricea de adiacență, listele, gradele și parcurgerile.

Numărul de noduri

Apasă un nod, apoi altul, ca să adaugi sau să scoți muchia dintre ele.

Noduri: 6
Muchii: 5
Suma gradelor: 10
Componente conexe: 2
Conex: nu
Complet: nu

Suma gradelor e 10, adică dublul celor 5 muchii. Nu e o coincidență: fiecare muchie adaugă câte 1 la gradul ambelor capete.

	0	1	2	3	4	5
0	0	1	0	1	0	0
1	1	0	1	0	0	0
2	0	1	0	1	0	0
3	1	0	1	0	0	0
4	0	0	0	0	0	1
5	0	0	0	0	1	0

Explorează interactiv

Se încarcă instrumentul…

Bifează când ai terminat, ca s-o vezi citită pe toate dispozitivele.

Testează-te pe capitolul 16

Lecția în clipuri

Clipuri scurte, cu voce și subtitrări.