Definiţie
Se numeşte graf neorientat G=(X,U) o pereche de mulţimi (X,U), unde X este o mulţime finită şi nevidă de elemente numite noduri (vârfuri) iar U o mulţime de perechi, formate cu elemente distincte din mulţimea X numite muchii.
Se numesc noduri adiacente orice pereche de noduri între care există o muchie.
ex:muchia (1,2)
Spunem că un nod este incident cu o muchie daca nodul reprezintă o extremitate pentru aceea muchie.
ex:nodul 1 este incident cu muchia (1,2)
Spunem ca 2 muchii sunt incidente daca au un nod comun .
ex: muchia (1,2), (1,3) au nodul 1 comun
Nodurile vecine unui nod sunt toate noduriile adiacente cu nodul respectiv.
Gradul unui nod X al grafului G este egal cu numarul de muchii incidente cu nodul respectiv şi se noteaza cu d(x).
ex:d(3)=5
Un nod care are gradul 1 se numeşte nod terminal.
ex: d(4)=1
Un nod care are gradul 0 se numeşte vârf izolat.
ex: d(7)=0
Numim lanţ o succesiune de noduri cu proprietatea că oricare ar fi 2 noduri successive ele sunt adiacente.
Se numeşte ciclu ,un lanţ în care toate muchiile sunt distincte 2 câte 2 şi între primul şi ultimul nod există o muchie.
Se numeşte lungimea unui lanţ ,numărul de muchii din care este format.
Se numeşte lanţ elementar,un lanţ care conţine doar noduri distincte.
Se numeşte lanţ simplu,un lanţ care conţine doar muchii distincte.
Un lanţ care nu este simplu se numeşte lanţ compus.
Se numeşte un ciclu elementar,ciclul în care toate nodurile sunt distincte 2 câte 2; excepţie primul şi ultimul nod.
Observaţii :
Orice lanţ elementar este un lanţ simplu.
Orice lanţ elementar este un lanţ simplu.
Nu este ciclu lanţul compus deoarece muchiile nu sunt distincte 2 câte 2.
TEOREME :
Numărul total de grafuri neorientate este:
2 la puterea Cn2 = 2 la puterea [n(n-1)]/2
Suma gradelor tuturor noduriilor unui graf neorientat este egală cu dublul nr. de muchii.
Dacă graful G neorientat are n noduri, iar n>2 atunci cel puţin 2 noduri au acelaşi grad.
Pentru orice graf neorientat,numărul noduriilor de grad impar este par.
Numărul minim de muchii pe care trebuie să le conţina un graf neorientat cu n noduri ca să nu existe vârfuri izolate este [(n+1)/2].
Numărul total de grafuri neorientate este:
2 la puterea Cn2 = 2 la puterea [n(n-1)]/2
Suma gradelor tuturor noduriilor unui graf neorientat este egală cu dublul nr. de muchii.
Dacă graful G neorientat are n noduri, iar n>2 atunci cel puţin 2 noduri au acelaşi grad.
Pentru orice graf neorientat,numărul noduriilor de grad impar este par.
Numărul minim de muchii pe care trebuie să le conţina un graf neorientat cu n noduri ca să nu existe vârfuri izolate este [(n+1)/2].
Moduri de reprezentare a grafurilor în memorie
a) Matrice de adiacenţă
Matricea de adiacenţă este o matrice patratică cu n linii şi m coloane .
Fiecare element i,j este de forma
aij= 0,dacă nu există muchie între nodul i şi nodul j;
1,dacă există muchie între nodul i şi nodul j.
a) Matrice de adiacenţă
Matricea de adiacenţă este o matrice patratică cu n linii şi m coloane .
Fiecare element i,j este de forma
aij= 0,dacă nu există muchie între nodul i şi nodul j;
1,dacă există muchie între nodul i şi nodul j.
Observatii :
1) Diagonala principală este întotdeauna egală cu 0.
2) Matricea este simetrică faţă de diagonala principală.
1) Diagonala principală este întotdeauna egală cu 0.
2) Matricea este simetrică faţă de diagonala principală.
b) Matricea de incidenţă
Are n linii(n=numărul de noduri) şi m coloane (m=numărul de muchii).
! Pe fiecare coloană există 2 valori de 1 care reprezintă extremităţile unei muchii; toate celelalte elemente fiind 0.
Are n linii(n=numărul de noduri) şi m coloane (m=numărul de muchii).
! Pe fiecare coloană există 2 valori de 1 care reprezintă extremităţile unei muchii; toate celelalte elemente fiind 0.
Grafuri speciale
Graful G se numeşte nul dacă mulţimea U este vidă (nu are muchii).Un graf se numeşte complet dacă are proprietatea că oricare 2 noduri ale sale sunt adiacente.
Teoremă: Numărul de muchii ale unui graf complet cu n noduri este
[n(n-1)]/2.
Se numeşte graf parţial al lui G=(X,U) graful Gp=(X,V) unde V este egal sau inclus în U (din graful G eliminăm muchii).
Se numeşte subgraf al lui G=(X,U), Gs=(Y,V) unde Y este egal sau inclus în X şi toate muchiile din mulţimea V aparţin şi mulţimii U,care au ambele extremităţi în mulţimea Y,adică se obţine din graful G prin eliminarea unor noduri şi a tuturor muchilor incidente cu acestea.
Se numeşte graf complementar al lui G,graful Gc care are propritatea că 2 noduri sunt adiacente în graful complementar dacă şi numai dacă nu sunt adiacente în graful G.Teoremă: Numărul grafurilor parţiale ale unui graf cu m muchii este 2 la puterea m.
Teoremă: Numărul de subgrafuri ale unui graf cu n noduri este 2ⁿ-1.
Conexitate
Definitie:
1) Un graf G se numeşte graf conex dacă are proprietatea că pentru orice pereche de noduri distincte există un lanţ care le leagă.
2) Dacă un graf G nu este conex se numeşte componentă conexă a grafului, un subgraf conex
al său maximal în raport cu această proprietate (conţine numărul maxim de noduri din graful G care au proprietatea că sunt legate de un lanţ).
2) Dacă un graf G nu este conex se numeşte componentă conexă a grafului, un subgraf conex
al său maximal în raport cu această proprietate (conţine numărul maxim de noduri din graful G care au proprietatea că sunt legate de un lanţ).
Teoreme:
1) Numărul minim de muchii necesare pentru ca un graf neorientat să fie conex este: n-1,unde n reprezintă numărul de noduri.
2) Un graf conex cu n noduri şi n-1 muchii este aciclic şi maximal în raport cu această proprietate.
3) Dacă un graf neorientat conex are n noduri şi m muchii, numărul de muchii care trebuie eliminate pentru a obţine un graf parţial conex aciclic este: m-n+1.
4) Dacă un graf are n noduri şi m muchii şi p componente conexe, numărul de muchii care trebuie eliminat pentru a obţine un graf parţial aciclic(arbore) este egal cu: m-n+p.
5) Pentru a obţine dintr-un graf neorientat conex 2 componente conexe numărul minim de muchii care trebuie eliminate este egal cu gradul minim din graf.
6) Numărul maxim de muchii dintr-un graf cu n noduri şi p componente conexe este [(n-p)(n-p+1)]/2.
Grafuri speciale
1) Numărul minim de muchii necesare pentru ca un graf neorientat să fie conex este: n-1,unde n reprezintă numărul de noduri.
2) Un graf conex cu n noduri şi n-1 muchii este aciclic şi maximal în raport cu această proprietate.
3) Dacă un graf neorientat conex are n noduri şi m muchii, numărul de muchii care trebuie eliminate pentru a obţine un graf parţial conex aciclic este: m-n+1.
4) Dacă un graf are n noduri şi m muchii şi p componente conexe, numărul de muchii care trebuie eliminat pentru a obţine un graf parţial aciclic(arbore) este egal cu: m-n+p.
5) Pentru a obţine dintr-un graf neorientat conex 2 componente conexe numărul minim de muchii care trebuie eliminate este egal cu gradul minim din graf.
6) Numărul maxim de muchii dintr-un graf cu n noduri şi p componente conexe este [(n-p)(n-p+1)]/2.
Grafuri speciale
Un graf G se numeşte graf bipartit dacă există două mulţimi nevide de noduri A si B care au proprietatea: A ∩ B= Ø iar A U B=X şi orice muchie din mulţimea U are o extremitate în mulţimea A şi o altă extremitate în mulţimea B.Un graf bipartit se numeşte graf bipartit complet dacă pentru oricare nod X care aparţine mulţimii A şi orice nod Y care aparţine mulţimii B există o muchie care le leagă.
Se numeşte lanţ Hamiltonian,lanţul care conţine toate nodurile grafului şi este elementar.Un graf care conţine un ciclu Hamiltonian se numeşte graf Hamiltonian.
Un ciclu se numeşte eulerian,ciclul elementar ce conţine toate muchiile grafului.
Se numeşte graf eulerian,graful care conţine un ciclu eulerian.
TEOREME
1) Un graf cu mai mult de 2 noduri este Hamiltonian dacă graful fiecărui nod este mai mare sau egal decât n/2.
2) Un graf ce nu conţine vârfuri izolate este eulerian dacă şi numai dacă este conex iar gradele tuturor noduriilor sunt numere pare.3) Numărul de cicluri hamiltoniene dintr-un graf complet cu n noduri este (n-1)!/2.
Definiţii
Se numeşte graf orientat sau digraf o pereche de mulţimi (X, U), unde X este o mulţime finită şi nevidă de elemente numite noduri sau vârfuri, iar U este o mulţime de perechi ordonate formate cu elemente distincte din mulţimea X, numite arce.
Mulţimea arcelor care ies dintr-un nod: ω +
Mulţimea arcelor care intră într-un nod: ω-
În graful G=(X,U) avem:
X = 1, 2, 3, 4, 5.
U={ (5,3), (1, 2), (1, 3), (1,4), (1,5), (2,3), (2,4), (2, 5), (3,4), (4, 5)}
Numim vârfuri adiacente orice pereche de vârfuri care formează un arc. Două vârfuri spunem că sunt incidente cu arcul pe care îl formează.
Pentru arcul (x, y) spunem că x este extremitatea iniţială şi y este extremitatea finală.
Spunem că doua arce sunt incidente dacă au o extremitate comună.
Se numeşte succesor al vârfului x orice vârf la care ajunge un arc care iese din x.
Mulţimea succesorilor se notează: Γ+.
Se numeşte predecesor al vârfului x orice vârf de la care intră un arc în vârful x.
Mulţimea predecesorilor se notează: Γ-.
Gradul intern al unui nod este egal cu numărul arcelor care intră în nod şi se noteazăd-(x).
Gradul extern al unui nod este egal cu numărul arcelor care ies din nod şi se noteazăd+(x).
Teoreme
Teorema 1: Numărul total de grafuri orientate cu n noduri este n(n-1)/2;
Teorema 2: Într-un graf orientat cu n noduri suma gradelor interne este egală cu suma gradelor externe şi este egală cu numărul arcelor.
Aplicaţii ale definiţiilor
Mulţimea arcelor care intră în nodul 2: ω +(2)= {(2, 5), (2, 3), (2, 4)};
Mulţimea arcelor care ies din nodul 2: ω- (2)={(1, 2)};
Nodurile 2 si 4 sunt adiacente.
Pentru arcul (2, 3) spunem ca 2 este extremitatea iniţială şi 3 este extremitatea finală.
Arcele (2, 3) şi (3, 4) sunt incidente.
Nodul 4 este succesor al nodului 2.
Nodul 2 este predecesor al nodului 4.
Mulţimea succesorilor nodului 2: Γ+2= {3, 4, 5};
Mulţimea predecesorilor nodului 2: Γ-2={1};
Gradul extern al nodului 2: 3
Grad intern al nodului 2: 1
Graf parţial
Fie graful G=(X,U). Se numeşte graf parţial al lui G, un graf G1=(X,V), cu V inclus în U. Altfel spus, un graf parţial al lui G este chiar G, sau se obţine din G, păstrând toate vârfurile şi suprimând nişte arce.
Fie graful G=(X,U). Se numeşte graf parţial al lui G, un graf G1=(X,V), cu V inclus în U. Altfel spus, un graf parţial al lui G este chiar G, sau se obţine din G, păstrând toate vârfurile şi suprimând nişte arce.
Se consideră graful G=(X, U), în care X={1, 2, 3, 4, 5, 6} şi U={(2,1), (1, 3), (4, 3), (3, 5), (6,4), (5, 6).
Graful parţial al lui G este G1=(X, V), în care X={1, 2, 3, 4, 5, 6} şi V={(2, 1), (3, 2), (4, 3), (6, 4), (5, 6)}.
Graful parţial al lui G este G1=(X, V), în care X={1, 2, 3, 4, 5, 6} şi V={(2, 1), (3, 2), (4, 3), (6, 4), (5, 6)}.
Subgraf
Fie graful G=(X, U). Un subgraf al lui G este un graf G2=(Y, V), unde Y inclus in U, iar V va conţine toate arcele din U, care au ambele extremităţi în Y. Altfel spus, un subgraf al unui graf se obţine eliminând nişte noduri şi arcele incidente acestor noduri.
Se consideră graful G=(X, U), în care X={1, 2, 3, 4, 5, 6} şi U={ (2, 1), (1, 3), (3, 2), (4, 3), (3, 5), (6, 4), (5, 6).
Subgraful lui G este G2=(Y, V), în care Y={3, 4, 5, 6} şi V={(4, 3), (3, 5), (6, 4), (5, 6).
Numim drum o succesiune de noduri care au proprietatea că oricare ar fi două noduri succesive acestea sunt legate printr-un arc.
Numim circuit un drum în care toate arcele sunt distincte două câte două şi există un arc de la ultimul nod la primul (numărul minin de noduri este 3).
- Elementar - un drum care conţine doar noduri distincte.
- Neelementar - un drum care nu conţine doar noduri distincte.
- Simplu - un drum care conţine doar muchii distincte.
- Compus - un drum care nu conţine doar muchii distincte.
Un circuit poate fi:
- Elementar - un circuit care conţine doar noduri distincte (cu excepţia primului şi a ultimului, care coincid).
- Neelementar - un circuit care nu conţine doar noduri distincte (cu excepţia primului şi a ultimului, care coincid).
Observaţii!
- Noţiunea de lanţ/ciclu este valabilă şi în cazul grafurilor orientate (nu are importanţă sensul arcelor).
- La drumuri/circuite toate arcele trebuie să aibă aceeaşi orientare.
Exemple de drumuri şi circuite
- Drum elementar
- Drum neelementar
- Circuit elementar
