Grafuri neorientate

Definiţii Se numeşte graf neorientat o pereche ordonată de mulţimi G=(X,U), unde X este mulţime

finită şi nevidă de elemente numită mulţimea vârfurilor (nodurilor), iar U este o mulţime de perechi neordonate de elemente din X numită mulţimea muchiilor.

Se notează: G=(X,U)-graf neorientat

u=[x,y] aparţine lui U se numeşte muchie a grafului G=(X,U) x,y se numesc extremităţi ale muchiei u [x,y]=[y,x] deoarece nu contează orientarea muchieiVârfurile x şi y sunt adiacente în G dacă sunt extremităţi ale aceleiaşi muchii.Spunem despre vârful x şi muchia u că sunt incidente (la fel vârful y şi muchia u).Două muchii sunt incidente dacă au o extremitate comună.Exemplu figura alăturată-G=(X,U)-X{1,2,3,4,5} U={[1,5],[5,2],[5,4],[2,4]}Vârfurile 2 şi 4 sunt adiacente. Vârfurile 1 şi 4 nu sunt incidente.Muchiile [1,5] şi [2,5] sunt incidente.Muchia [2,4] şi vârful 2 sau 4 sunt incidente. Muchia [2,4] şi vârful 1 sau 4 nusunt incidente.

Fie G=(X,U) un graf neorientat şi x un vârf. Gradul unui vârf x, notat d(x), reprezintă numărul muchiilor care trec prin nodul x

(incidente cu nodul x).,sau numărul de vârfuri adiacente cu acesta.

Fie graful G=(X,U)un graf neorientat si x un vârf. a)Dacă gradul vârfului x este = cu 0,atunci vârful x este izolat. b)Dacă gradul vârfului x este = cu 1, atunci vârful x se numeşte vârf terminal sau frunză.

Fie G=(X,U) un graf neorientat.a)Se numeşte graf complet dacă oricare două vârfuri ale sale sunt adiacenteb)Se numeşte graf bipartit dacă există două mulţimi A şi B incluse în X, astfel încât:*A intersectat cu B=mulţimea vidă, A reunit cu B=X,*toate muchiile grafului au o extremitate în A şi cealaltă în B.

Fie G=(X,U) un graf neorientat.a) Se numeşte graf parţial al grafului G,un graf G1=(X,U1), cu proprietatea că U1 inclus în U.b)Se numeşte subgraf al grafului G un graf H=(X1,U1) cu proprietatea că X1 inclus în X ,U1 inclus în U, şi orice muchie din U1 are ambele extremităţi în X1.Noţiuni de lanţ şi cicluObservaţie 6: a)Un graf parţial se obţine prin păstrarea tuturor vârfurilor şi eliminarea unor muchii.b)Un subgraf se obţine prin eliminarea unor vârfuri şi a muchiilor incidente cu acestea.Fie G=(X,U) un graf neorientat.a)Se numeşte lanţ în graful G, o succesiune de vârfuri L=(z1,z2,...,zk), unde z1.z2,...,zk aparţin lui X, cu proprietatea ca oricare două vârfuri consecutive sunt adiacente, adică există muchiile [z1,z2], [z2,z3],...,[zk-1,zk] aparţin lui U.b)Un lanţ se numeşte elementar dacă oricare 2 vârfuri ale sale sunt distincte.c) Se numeşte ciclu într-un graf, un lanţ L=(z1,z2,...,zk) cu proprietatea că z1=zk şi muchiile [z1,z2],[z2,z3],...,[zk-1,zk] sunt distincte două câte douăd)Un ciclu se numeşte elementar dacă oricare două vârfuri ale sale cu excepţia primului şi al ultimului vârf sunt distincte.

Fie G=(X,U) un graf neorientat.

Un graf G este conex, dacă oricare ar fi două vârfuri ale sale, există un lanţ care le leagă. În teoria grafurilor, un arbore este un graf neorientat, conex şi fără cicluri.

Arborii reprezintă grafurile cele mai simple ca structură din clasa grafurilor conexe, ei fiind şi cei mai frecvent utilizaţi în practică.

Propoziţii şi teoreme

Fie un graf neorientat G=(V,E), unde V e mulţimea vârfurilor, iar E cea a muchiilor sale. Următoarele afirmaţii sunt echivalente:

G este arbore. G este un graf conex minimal („minimal” se numeşte proprietatea unui graf, că dacă i se elimină orice muchie, se obţine un graf neconex). G este un graf fără cicluri maximal („maximal” se numeşte proprietatea unui graf, că dacă i se adaugă orice muchie, se obţine un graf care are măcar un ciclu, şi deci nu e arbore).

Un arbore cu n ≥ 2 vârfuri conţine cel puţin două vârfuri terminale. Orice arbore cu n vârfuri are n-1 muchii. Noţiuni corelateFie G un graf neorientat. Un graf parţial H al lui G cu proprietatea că H este arbore se numeşte „arbore parţial” al lui G. Un graf neorientat G conţine un arbore parţial dacă şi numai dacă G este conex. Un graf neorientat care nu conţine cicluri se numeşte „pădure”.

Reprezentarea grafurilor în memorie

Fie G= (X,U) un graf neorientat cu n vârfuri şi m muchii. A. Matricea de adiacenţa a[i,j]= 1 , dacă există muchia a[i,j] cu i<>j 0 , în caz contrar Proprietăţi: 1)a[i][i]=0, for(i=1;i<=n;i++) (elementele de pe diagonala principală să fie egale

cu 0) 2)Matricea este simetrică faţă de diagonala principală a[i][j]=a[j][i] 3)Matricea este complexitatea spaţiu (n*n) de ordinul n pătrat. O(n*n) 4) Suma elementelor de pe linia sau coloana i este egală cu gradul vârfului i.

B.Vector de muchii Vom reprezenta graful prin intermediul unui vector cu elemente de tip

înregistrare, fiecare înregistrare având 2 ampuri:extremităţile muchiilor. Proprietăţi: Complexitatea spaţiu a acestei reprezentări este de ordinul O(2m).

C. Liste de adiacenţă O(n+2m) Proprietate: Complexitatea spaţiu a acestei reprezentări este de ordinul O(n+2m)

Teoreme

|x|=n |U|=m Teorema 1:

Într-un graf G=(X,U) cu n vârfuri şi m muchii, suma gradelor tuturor vârfurilor este egală cu 2*numărul muchiilor.

Fiecare muchie a grafului contribuie cu 2 la suma gradelor; graful are m muchii, suma tuturor gradelor este egală cu 2.

Teorema 2: Fie G=(X,U) un graf neorientat.

Există un număr par de vârfuri de grad impar. Demonstratie: Notăm: -S=suma gradelor tuturor vârfurilor -S1=suma gradelor vârfurilor de grad par -S2=suma gradelor vârfurilor de grad impar. S1+S2 =S T1 – S=2m -S1+S2=sm -S2 par. –S2 contine un numar par S1 par S2 suma termeni impari de varfuri de grad 2m par impar.   Teorema 3 :

Graful complet de ordin notat K(n) are n(n-1)/2 muchii.

Tipuri de grafuri

  Fie G=(V, E) un graf neorientat, unde V are n elemente (n noduri) şi E are m

elemente (m  muchii).     Lanţ eulerian = un lanţ simplu care conţine toate muchiile unui graf

Lanţul: L=[1.2.3.4.5.3.6.2.5.6] este lanţ eulerian   Ciclu eulerian = un ciclu simplu care conţine toate muchiile grafului Ciclul: C=[1.2.3.4.5.3.6.2.5.6.1] este ciclu eulerian   Graf eulerian = un graf  care conţine un ciclu eulerian.   Condiţie necesară şi suficientă: Un graf este eulerian dacă şi numai dacă oricare

vârf al său are gradul par. Observatie: graful poate fi eulerian si daca contine noduri izolate.

Graf hamiltonian

Fie G=(V, E) un graf neorientat, unde V are n elemente (n noduri) şi E are m elemente (m  muchii).

  Lanţ hamiltonian = un lanţ elementar care conţine toate nodurile unui graf

   L=[2 ,1, 6, 5, 4, 3] este lanţ hamiltonian Ciclu hamiltonian = un ciclu elementar care conţine toate nodurile grafului

  C=[1,2,3,4,5,6,1] este ciclu hamiltonian   Graf hamiltonian = un graf G care conţine un ciclu hamiltonian Graful anterior este graf Hamiltonian.