Grafuri

Graf = orice mulțime finită $V$ prevăzută cu o relație binară internă $E$. Notăm graful cu $G=(V,E)$ Noțiunile de vârf și nod sunt echivalente (dar cele de arc și muchie nu sunt).

Tipuri de grafuri

Grafuri orientate Grafuri neorientate Arbori

Terminologie comună

Un lanț, drum, ciclu sau circuit:

• are lungimea egală cu numărul de muchii sau arce
• este simplu dacă nu repetă muchii sau arce
• este compus dacă repetă muchii sau arce (dacă nu este simplu, este compus)
• este elementar dacă nu repetă noduri sau vârfuri și implicit nu repetă muchii sau arce (în cazul ciclurilor și circuitelor se repetă evident primul și ultimul nod)
• dacă este elementar, este implicit și simplu, dar nu și invers

Graf parțial

Dacă dintr-un graf $G=(V,E)$ se elimină cel puțin o muchie/arc atunci noul graf $G^{\prime }=(V,E^{\prime }),E^{\prime }\subset E$ se numește graf parțial al lui $G$. Deci putem elimina și toate muchiile și vom obține graful $G^{\prime }=(V,\varnothing )$ (numit și graf nul), care este și el un graf parțial al lui $G$. Graful inițial este și el graf parțial al lui însuși deoarece $E\subset E$ Fie $m$ numărul de muchii/arce al unui graf, numărul total de grafuri parțiale este suma numărului de grafuri cu $0,1,2,...,m$ muchii/arce eliminate. Deci formula este aceasta: $C_m^0+C_m^1+...+C_m^m=2^m$ (vezi calculul numărului de submulțimi). Precizare: nu este relevant numărul de noduri/vârfuri

Subgraf

Dacă dintr-un graf $G=(V,E)$ se elimină noduri/vârfuri (se pot elimina și 0 noduri) împreună cu muchiile/arcele incidente lui, atunci noul graf $G^{\prime }=(V^{\prime },E^{\prime }),E^{\prime }\subseteq E,V^{\prime }\subseteq V$ se numește subgraf al lui $G$.

• fix this when clear (inclus sau egal, sau inclus și inegal) ATENȚIE: Graful vid Fie un graf cu $n$ noduri/vârfuri, numărul total de subgrafuri este suma numărului de subgrafuri cu $0,1,2,3,...,n-1$ noduri/vârfuri eliminate. Deci formula este aceasta: $C_n^0+C_n^1+C_n^2+...+C_n^{n-1}=2^n-1$ (vezi calculul numărului de submulțimi). Precizare: nu este relevant numărul de muchii/arce.

Graf conex

Graful conex este un graf $G=(V,E)$ în care pentru orice pereche de noduri $(v,w),v,w\in V$ există un lanț/drum care le unește

Graf complet

Graful $G$ se numește graf complet dacă oricare două noduri/vârfuri distincte ale sale sunt adiacente (în cazul grafului orientat complet vom folosi definiția de pe pbinfo pentru adiacență) Numărul muchii într-un graf complet neorientat cu $n$ noduri este $\frac{n(n-1)}{2}$. În cazul grafului orientat complet nu putem ști numărul de arce.

Graf nul

$G=(V,\varnothing )$ Graful nul este graful în care nu există muchii/arce, sau în care mulțimea muchiilor este vidă $E=\varnothing$. A nu fi confundat cu cu graful vid. Graful complementar al grafului nul este graful complet.

Graf complementar

Fie $G=(V,E)$ un graf. Se numește graf complementar al grafului $G$, graful $G^{\prime }=(V,E^{\prime })$ cu proprietatea că două noduri $i$ și $j$ sunt adiacente în $G^{\prime }$ dacă și numai dacă nu sunt adiacente în $G$. Cu alte cuvinte, dacă am considera graful complet $G=(V,E^{\prime \prime })$ , $E^{\prime }\cap E=\varnothing \text{și}{E}^{\prime }\cup E=E^{\prime \prime }$ Atenție: acest concept nu prea se aplică grafurilor orientate.

Componenta conexă

Componenta conexă este un subgraf al grafului de referință, maximal în raport cu proprietatea de conexitate (între oricare 2 vârfuri există un lanț). Sunt considerate componente conexe și nodurile izolate. Practic este o componentă conexă când nu mai putem alege încă un nod/vârf care să fie legat de celelalte. Putem spune că sunt “insulele” din graful de referința Graful de mai jos are 3 componente conexe

Hamiltonian

• Lanțul sau drumul elementar care conține toate nodurile/vârfurile se numește hamiltonian.
• Ciclul sau circuitul elementar care conține toate nodurile/vârfurile se numește hamiltonian.
• Graful care conține un ciclu sau circuit hamiltonian se numește hamiltonian.

Condiție de suficiență

Dacă $G$ este un graf cu $n\ge 3$ noduri/vârfuri astfel încât gradul oricărui nod/vârf verifică inegalitatea $gr(x)\ge \frac{n}{2}$ rezultă că $G$ este graf hamiltonian. Este foarte rar folosită, nu se întâmplă des ca un graf hamiltonian să îndeplinească această condiție (este suficientă, nu necesară)

Eulerian

• Lanțul sau drumul simplu care conține toate muchiile/arcele se numește eulerian.
• Ciclul sau circuitul simplu care conține toate muchiile/arcele se numește eulerian.
• Graful care conține un ciclu sau circuit eulerian se numește eulerian.

Condiție necesară și suficientă

Pentru graf neorientat

Un graf neorientat este eulerian dacă și numai dacă:

• Este conex
• Oricare nod al său are gradul par

Pentru graf orientat

Un graf orientat este eulerian dacă și numai dacă:

• Este conex

• Oricare vârf are gradul interior egal cu gradul exterior

• 📅 2024-02-11 de completat cu noțiuni de pe pbinfo

• ⏫ De clarificat situația grafului vid