Teorie completă cu exemple, desene și explicații pentru elevi
Teorie cu exemple și desene
Definiția grafului neorientat
Un graf neorientat este o pereche ordonată
G = (X, U), unde:
X este mulțimea vârfurilor;
U este mulțimea muchiilor, fiecare muchie fiind o pereche neordonată de vârfuri.
Exemplu:
X = {1, 2, 3, 4, 5, 6, 7}
U = {(1,2), (2,3), (1,4), (4,3), (2,4)}
1. Vârfuri adiacente
Definiție: Două vârfuri sunt adiacente dacă există muchia care le unește.
Exemplu: Vârfurile 1 și 2 sunt adiacente.
2. Muchii incidente
Definiție: Două muchii sunt incidente dacă au un vârf comun.
Exemplu: Muchiile (1,2) și (2,3) sunt incidente în vârful 2.
3. Gradul unui vârf
Definiție: Gradul unui vârf = numărul de muchii incidente la acel vârf.
Exemplu: Vârful 2 are gradul 3 (este conectat la 1,3 și 4).
4. Vârf izolat și terminal
Definiție: Vârf izolat = grad 0; Vârf terminal = grad 1.
Exemplu: Vârful 4 este izolat, iar vârful 3 este terminal.
5. Graf complet K₄
Definiție: Toate perechile de vârfuri sunt adiacente.
Exemplu: În K₄ fiecare vârf are gradul 3.
Lanțuri și cicluri
Lanț
Definiție: Un lanț într-un graf neorientat este o succesiune de vârfuri
(v₁, v₂, ..., vₖ) astfel încât între oricare două vârfuri consecutive există o muchie.
Lungimea unui lant este egala cu numarul de muchii ale acestuia.
Lanț elementar
Definiție: Un lanț elementar este un lanț în care
niciun vârf nu se repetă.
Orice lanț elementar este, în mod necesar, un lanț simplu.
Exemplu: 1 → 2 → 3 → 4 → 5 → 6 → 7
Lanț neelementar
Definiție: Un lanț neelementar este un lanț în care
cel puțin un vârf se repetă.
Exemplu: 1 → 2 → 3 → 4 → 2 → 5 → 6
Lanț compus
Definiție: Lanț în care cel puțin o muchie apare de mai multe ori.
Un lanț compus este întotdeauna neelementar.
Exemplu: 1 → 2 → 3 → 2 → 4 → 5 → 6
Muchia (2,3) este parcursă de două ori.
Lanț simplu neelementar
Definiție: Lanț în care nu se repetă muchii, dar se repetă vârfuri.
Exemplu: 1 → 2 → 3 → 4 → 2 → 5 → 6
Muchiile sunt distincte, dar vârful 2 apare de două ori.
Ciclu
Definiție: Un ciclu este un lanț care începe și se termină în același vârf.
Prin definiție, un ciclu este întotdeauna simplu și nu poate fi compus.
Ciclu elementar
Definiție: Ciclu în care nu se repetă alte vârfuri în afară de primul/ultimul.
Exemplu: 1 → 2 → 3 → 4 → 5 → 6 → 7 → 1
Ciclu neelementar
Definiție: Ciclu în care se repetă cel puțin un vârf intermediar.
Exemplu: 1 → 2 → 3 → 4 → 2 → 5 → 6 → 1
7. Graf bipartit
Definiție: Vârfurile sunt împărțite în două mulțimi A și B, muchiile conectează doar între A și B.
Exemplu: Mulțimile A={1,2}, B={3,4} cu muchii (1,3), (2,4).
8. Graf conex
Definiție: Pentru orice două vârfuri există un lanț care le unește.
Exemplu: Graful 1-2-3-4 este conex.
9. Componentă conexă
Definiție: O componentă conexă a unui graf neorientat este un subgraf maximal în care există un lanț între orice două vârfuri.
Vârfurile izolate formează componente conexe de un singur vârf.
Exemplu: Graful cu 12 vârfuri și 5 componente conexe (2 vârfuri izolate, restul cu 2–3 muchii fiecare).
Componente conexe:
C1 = {1}
C2 = {2}
C3 = {3, 4, 5}
C4 = {6, 7, 8, 9}
C5 = {10, 11}
C6 = {12}
10. Graf biconex
Definiție: Rămâne conex după eliminarea oricărui vârf.
Exemplu: Ciclu 1-2-3-4-1 este biconex.
11. Graf parțial
Definiție: Graf parțial = se păstrează toate vârfurile, dar se elimină unele muchii.
Exemplu: Pornim din K₄ și eliminăm muchia (3,4).
Graful inițial (K₄):
Graful parțial (fără muchia 3–4):
12. Subgraf
Definiție: Subgraf = alegem o submulțime de vârfuri și muchiile lor incidente.
Exemplu: Din K₄ păstrăm doar vârfurile {1,2,3}. Vârful 4 și muchiile sale sunt eliminate.
Graful inițial (K₄):
Subgraful (pe vârfurile {1,2,3}, cu 4 eliminat):
13. Graf eulerian
Lanț eulerian
Definiție: Un lanț eulerian este un lanț care trece exact o dată prin fiecare muchie a grafului.
Circuit eulerian
Definiție: Un circuit eulerian este un lanț eulerian care începe și se termină în același vârf.
Graf eulerian
Definiție: Un graf este eulerian dacă conține un circuit eulerian, adică un lanț eulerian închis care trece prin toate muchiile si graful este conex.
Exemplu: Graful cu 5 vârfuri și 6 muchii, toate vârfurile au grad par.
Observație: Toate vârfurile grafului au grad par, deci graful este eulerian.
14. Graf hamiltonian
Lanț hamiltonian
Definiție: Un lanț hamiltonian este un lanț care trece o singură dată prin toate vârfurile grafului.
Circuit hamiltonian
Definiție: Un circuit hamiltonian este un lanț hamiltonian care începe și se termină în același vârf.
Graf hamiltonian
Definiție: Un graf este hamiltonian dacă conține un circuit hamiltonian.
Exemplu: Graful cu 7 vârfuri unde există un circuit hamiltonian 1 → 2 → 3 → 4 → 5 → 6 → 7 → 1.
Observație: Traseul roșu reprezintă circuitul hamiltonian care trece o singură dată prin toate vârfurile și se întoarce la 1.
15. Formule utile
Formule utile în teoria grafurilor
Suma gradelor vârfurilor:
Suma gradelor tuturor vârfurilor dintr-un graf este egală cu dublul numărului de muchii:
∑deg(v) = 2m
Numărul de grafuri parțiale:
Pentru un graf cu m muchii, numărul de grafuri parțiale este:
2^m
Numărul de subgrafuri:
Pentru un graf cu n vârfuri, numărul de subgrafuri (nu izolate) este:
2^n - 1
Numărul total de grafuri neorientate:
Pentru n vârfuri, numărul total de grafuri neorientate care se pot forma este:
2^(n(n-1)/2)
Număr par de vârfuri de grad impar:
În orice graf există un număr par de vârfuri cu grad impar.
Vârfuri de același grad:
Dacă un graf are cel puțin 2 vârfuri, există cel puțin două vârfuri cu același grad.
Număr minim de muchii fără noduri izolate:
Pentru un graf cu n vârfuri fără noduri izolate, numărul minim de muchii este:
⌈(n+1)/2⌉
Graf complet:
Un graf neorientat complet cu n vârfuri are:
n(n-1)/2 muchii
Numărul maxim de cicluri independente:
Pentru un graf cu n vârfuri, m muchii și p componente conexe, numărul maxim de cicluri independente este:
m - n + p
Numărul maxim de muchii cu p componente conexe:
Un graf neorientat cu n vârfuri și p componente conexe poate avea maxim:
(n - p)(n - p + 1)/2 muchii
Numărul de cicluri elementare într-un graf conex:
Pentru un graf conex cu n vârfuri și m muchii:
Număr de cicluri elementare = m - n + 1
Graf eulerian:
Un graf este eulerian dacă și numai dacă fiecare vârf are grad par.
Condiție suficientă pentru graf hamiltonian:
Dacă gradul fiecărui vârf este ≥ jumătate din numărul de vârfuri, graful este hamiltonian.
(grad(v) ≥ n/2 ⇒ graful este hamiltonian) Reciproca nu este obligatoriu valabilă.
Metode de reprezentare
Matrice de adiacență
Matrice pătratică n×n: A[i][j] = 1 dacă există muchia (i,j), altfel 0.
Pentru graf neorientat: A[i][j] = A[j][i].
Se păstrează toate perechile de vârfuri care formează muchii. În C++ putem folosi struct:
struct Muchie {
int v1;
int v2;
};
Muchie U[2];
U[0] = {1,2};
U[1] = {2,3};
Probleme C++ rezolvate
Problema 1
Exemplu:
#include <iostream>
using namespace std;
struct Muchie {
int v1;
int v2;
};
int main() {
int n = 3;
Muchie U[2] = {{1,2},{2,3}};
for(int i=0;i<2;i++)
cout << "(" << U[i].v1 << "," << U[i].v2 << ") ";
return 0;
}
Problema 2 (rezolvare teoretică)
Exemplu:
Se determină dacă un graf este complet: verificăm pentru fiecare vârf dacă gradul = n-1. Dacă toate sunt egale, graf complet.
Exerciții propuse
Un graf neorientat cu 6 noduri este reprezentat prin listele de adiacență:
1: 2, 3, 5 2: 1, 4, 6 3: 1, 4 4: 2, 3, 5 5: 1, 4, 6 6: 2, 5
Scrieți mulțimea nodurilor și a muchiilor unui subgraf conex și eulerian.
Un graf complet are 9 noduri și 36 de muchii. Indicați numărul minim de muchii ce trebuie eliminate pentru ca graful să aibă două componente conexe cu cel puțin 3 noduri fiecare.
a. 9 b. 12 c. 15 d. 18
Indicați numărul de noduri ale unui graf complet cu 231 de muchii.
a. 21 b. 22 c. 23 d. 24
Un graf neorientat are 30 de noduri și 6 componente conexe, fiecare fiind un arbore. Determinați numărul de muchii.
a. 23 b. 24 c. 25 d. 26
Un graf neorientat are 14 muchii. Două noduri au grad 0, șase au grade impare, restul au grade pare. Indicați numărul maxim de noduri ale grafului.
a. 12 b. 13 c. 14 d. 15
Un graf cu 7 noduri și muchiile [1,2], [1,3], [2,4], [3,5], [4,6], [5,7], [6,7] are un subgraf conex și fără cicluri. Scrieți listele de adiacență ale acestuia.
Într-un oraș sunt 6 stații de autobuz, una fiind conectată prin drumuri bidirecționale cu toate celelalte. Câte drumuri suplimentare trebuie adăugate pentru ca graful să fie eulerian?
a. 0 b. 2 c. 4 d. 6
Un graf neorientat are 6 noduri cu gradele: (3, x, 2, 4, y, 3). Indicați o pereche posibilă pentru (x, y).
a. 0 și 4 b. 1 și 3 c. 2 și 2 d. 3 și 1
Un graf admite un ciclu eulerian de lungime 13 și un ciclu hamiltonian de lungime 8. Indicați câte muchii trebuie eliminate pentru ca graful să fie arbore.
a. 3 b. 4 c. 5 d. 6
Un graf cu 8 noduri și 9 muchii are deja [1,2], [2,5], [3,4], [4,6], [6,7]. Știind că un lanț elementar maxim este 1-2-5-3-4-6-7, care ar putea fi celelalte 4 muchii?
a. [1,3], [2,4], [5,6], [7,8]
b. [1,6], [2,7], [3,7], [4,8]
c. [1,5], [2,6], [3,8], [6,8]
d. [1,4], [2,3], [5,7], [6,8]
Un graf cu 6 noduri și muchiile [1,2], [1,3], [2,3], [4,6]. Indicați numărul de componente conexe.
a. 2 b. 3 c. 4 d. 5
Un graf cu 7 noduri și muchiile [1,2], [1,4], [2,3], [2,5], [3,6], [4,7], [5,6]. Scrieți mulțimea muchiilor unui subgraf complet cu număr maxim de noduri.
Un graf neorientat fără cicluri are 24 de muchii și 3 componente conexe. Indicați numărul de noduri.
a. 22 b. 23 c. 24 d. 25
Un graf complet cu 5 noduri. Indicați o valoare care NU poate fi numărul de muchii ale unui subgraf.
a. 0 b. 3 c. 5 d. 7
Un graf cu 15 noduri, numerotate 1..15, are muchia [i,j] dacă și numai dacă suma cifrelor lui i este egală cu suma cifrelor lui j. Indicați numărul de valori nule din matricea de adiacență.
a. 135 b. 150 c. 165 d. 180
Un graf cu 6 noduri și muchiile [1,2], [1,3], [2,3], [3,4], [4,5], [5,6]. Indicați un ciclu elementar.
a. 1-2-3-1 b. 2-3-4-2 c. 3-4-5-3 d. 4-5-6-4
Indicați numărul de noduri ale unui graf complet cu 153 de muchii.
a. 17 b. 18 c. 19 d. 20
Un graf complet cu 12 noduri. Indicați câte muchii trebuie eliminate pentru ca graful să fie arbore.
a. 55 b. 66 c. 67 d. 70
Un graf cu 25 de noduri și 4 componente conexe, fiecare fiind arbore. Indicați numărul de muchii.
a. 20 b. 21 c. 22 d. 23
Un graf cu 6 noduri este reprezentat prin listele:
1: 2,6 2: 1,3,5 3: 2,4 4: 3,5,6 5: 2,4,6 6: 1,4,5
Scrieți un lanț neelementar și un ciclu elementar al acestuia.
Un graf eulerian cu 6 noduri are un nod de grad 6. Indicați numărul minim de muchii.
a. 6 b. 8 c. 10 d. 12
Un graf cu 5 noduri este reprezentat prin matricea:
0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0
Indicați numărul de subgrafuri conexe distincte, diferite de graful dat.
a. 5 b. 6 c. 8 d. 10
Care dintre următoarele șiruri pot reprezenta gradele nodurilor unui graf cu 5 noduri?
a. 1,1,2,2,2 b. 0,2,2,3,3 c. 0,0,4,4,2 d. 5,4,3,2,1
Un graf cu 15 noduri și 7 muchii. Numărul maxim de componente conexe?
a. 9 b. 10 c. 11 d. 15
Un graf conex are 12 muchii. Care este numărul maxim de noduri?
a. 10 b. 11 c. 12 d. 13
Un graf cu 9 noduri și muchiile [1,2], [1,3], [2,4], [4,5], [5,6], [6,7], [7,8], [8,9]. Care trei noduri nu fac parte din niciun ciclu?
a. 1, 2, 3 b. 4, 5, 6 c. 7, 8, 9 d. 2, 5, 8
Un graf fără cicluri are 30 de muchii și 10 componente conexe. Determinați numărul de noduri.
a. 35 b. 36 c. 37 d. 38
Un graf complet cu 10 noduri. Pentru a obține două componente conexe, fiecare completă, câte muchii maxim se pot elimina?
a. 18 b. 20 c. 25 d. 27
Un graf cu 4 noduri este reprezentat prin matricea:
0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0
Scrieți un subgraf în care un nod are grad 1 și altul grad 3.