Grafuri neorientate

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.

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].

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.

Observatii :
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.

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ţ).

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

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.