Capitolul 17 · Lecția 17.1 din 2

Grafuri orientate

Arc, grad intern și extern, drum, circuit și tare conexitate.

Capitolul 17: Grafuri orientate și arbori

Pe această pagină6 secțiuni

Ce se schimbă față de graful neorientat

Într-un graf orientat, legătura dintre noduri are sens. Se numește arc și se notează $(x, y)$ , cu $x$ extremitate inițială și $y$ extremitate finală.

$(x, y)$ și $(y, x)$ sunt arce diferite.

Terminologie

Grad extern $d^+(x)$ : numărul de arce care pleacă din $x$ .
Grad intern $d^-(x)$ : numărul de arce care intră în $x$ .
Drum: succesiune de noduri în care fiecare arc respectă sensul.
Drum elementar: drum fără noduri repetate.
Circuit: drum în care primul nod coincide cu ultimul.
Circuit elementar: circuit fără noduri repetate, în afară de primul și ultimul.
Lungime: numărul de arce.
Subgraf și graf parțial: la fel ca la neorientat (scoți noduri, respectiv doar arce).

Teorema gradelor

$\sum_{x \in V} d^+(x) = \sum_{x \in V} d^-(x) = m$

Suma gradelor externe egalează suma gradelor interne și amândouă dau numărul de arce. Fiecare arc pleacă exact dintr-un nod și intră exact în altul.

Tare conexitate

Un graf orientat e tare conex dacă între oricare două noduri $x$ și $y$ există drum de la $x$ la $y$ și drum de la $y$ la $x$ .

O componentă tare conexă e un subgraf tare conex maximal.

Matricea de adiacență

$a[i][j] = 1 \text{ dacă există arcul } (i, j)$

Nu mai e simetrică. De aceea:

gradul extern al nodului $i$ = suma de pe linia $i$ ;
gradul intern al nodului $i$ = suma de pe coloana $i$ ;
numărul de arce = suma tuturor elementelor, fără să se împartă la 2.

Reține

La graf orientat nu se împarte la 2, pentru că matricea nu mai e simetrică. E cea mai frecventă greșeală la trecerea de la neorientat la orientat.

Greșeli frecvente

Se împarte la 2 numărul de arce.
Se confundă gradul intern cu cel extern. Linie = extern (pleacă), coloană = intern (intră).
Se confundă conexitatea (pe graf neorientat) cu tare conexitatea (pe orientat).

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] = 1;
    }
    for (int i = 1; i <= n; i++) {
        int ext = 0, intern = 0;
        for (int j = 1; j <= n; j++) {
            ext += a[i][j];
            intern += a[j][i];
        }
        cout << i << ": d+=" << ext << " d-=" << intern << "\n";
    }
    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 17

Lecția în clipuri

Clipuri scurte, cu voce și subtitrări.