Capitolul 16 · Lecția 16.2 din 3

Proprietăți: conex, complet, hamiltonian, eulerian

Componente conexe, graf complet, cicluri hamiltoniene și euleriene.

Capitolul 16: Grafuri neorientate

Pe această pagină5 secțiuni

Graf conex

Un graf e conex dacă între oricare două noduri există un lanț.

O componentă conexă e un subgraf conex maximal: nu mai poți adăuga niciun nod fără să pierzi conexitatea. Un graf neconex are cel puțin două componente.

Graf complet

Un graf complet $K_n$ are muchie între oricare două noduri distincte.

$m = \frac{n(n-1)}{2}$

Fiecare nod are gradul $n - 1$ .

Graf hamiltonian

Are un ciclu hamiltonian: un ciclu elementar care trece prin toate nodurile, fiecare exact o dată.

Condiție suficientă (Dirac): dacă $n \geq 3$ și fiecare nod are $d(x) \geq n/2$ , graful e hamiltonian. Atenție: e suficientă, nu necesară.

Graf eulerian

Are un ciclu eulerian: un ciclu care parcurge toate muchiile, fiecare exact o dată.

Teoremă (condiție necesară și suficientă): un graf conex e eulerian dacă și numai dacă toate nodurile au grad par.

Dacă exact două noduri au grad impar, graful nu e eulerian, dar admite un lanț eulerian între acele două noduri.

Reține

Confuzia clasică: hamiltonian trece prin toate NODURILE, eulerian trece prin toate MUCHIILE. Criteriul eulerian e simplu și se verifică imediat (toate gradele pare); cel hamiltonian nu are criteriu simplu.

Greșeli frecvente

Se inversează hamiltonian cu eulerian.
Se aplică teorema lui Euler pe un graf neconex. Condiția cere graful conex.
Se crede că teorema lui Dirac e și necesară. Un graf poate fi hamiltonian fără s-o respecte.

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 n, m, a[101][101];
bool vizitat[101];

void dfs(int x) {
    vizitat[x] = true;
    for (int y = 1; y <= n; y++)
        if (a[x][y] && !vizitat[y]) dfs(y);
}

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

    int componente = 0;
    for (int i = 1; i <= n; i++)
        if (!vizitat[i]) { componente++; dfs(i); }

    int impare = 0;
    for (int i = 1; i <= n; i++) {
        int g = 0;
        for (int j = 1; j <= n; j++) g += a[i][j];
        if (g % 2 == 1) impare++;
    }

    cout << "componente=" << componente << " ";
    cout << (componente == 1 ? "conex" : "neconex") << " ";
    cout << ((componente == 1 && impare == 0) ? "eulerian" : "neeulerian");
    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.