definiţie - c++informatik.ddbuftea.ro/grafuritr.pdf · 4 definiţie : un graf parţial al grafului...

32
1 GRAFURI NEORIENTATE .............................................................................................................................................................................................................................3 Se numeste graf partial...............................................................................................................................................................................................................................4 Se numeste subgraf ....................................................................................................................................................................................................................................4 Reprezentarea grafurilor neorientate ........................................................................................................................................................................................................7 matricea de adiacenta ....................................................................................................................................................................................................................7 listele vecinilor ................................................................................................................................................................................................................................7 vectorul muchiilor ...........................................................................................................................................................................................................................7 Moduri de memorare ale unui graf ............................................................................................................................................................................................................7 Proprietatile matricei : ................................................................................................................................................................................................................................9 Vectorul muchiilor. .....................................................................................................................................................................................................................................9 Parcurgerea grafurilor ..............................................................................................................................................................................................................................12 Algoritmul de parcurgere in latime BF (Breadth First); ............................................................................................................................................................................14 Algoritmul de parcurgere in adancime DF (Depth First);.....................................................................................................................................................................15 Aplicatie ....................................................................................................................................................................................................................................................16 In C++ vom afisa matricea de adiacenta: ..................................................................................................................................................................................................17 Calcularea gradelor nodurilor ...................................................................................................................................................................................................................18 Parcurgerea in latime: ..............................................................................................................................................................................................................................19 CONEXITATE ..............................................................................................................................................................................................................................................22 Definiţie -lant ............................................................................................................................................................................................................................................23 Sa se afiseze un lant de lungime minima intre nodurile a si b: ................................................................................................................................................................26 Se numeşte graf hamiltonian....................................................................................................................................................................................................................29 Grafuri hamiltoniene si euleriene .............................................................................................................................................................................................................31

Upload: others

Post on 13-Oct-2019

9 views

Category:

Documents


0 download

TRANSCRIPT

Page 1: Definiţie - C++informatik.ddbuftea.ro/grafuritr.pdf · 4 Definiţie : Un graf parţial al grafului G=(X,U) este un graf G1(X,V) astfel încât V U, adică G1 are aceeaşi mulţime

1

GRAFURI NEORIENTATE ............................................................................................................................................................................................................................. 3

Se numeste graf partial ............................................................................................................................................................................................................................... 4

Se numeste subgraf .................................................................................................................................................................................................................................... 4

Reprezentarea grafurilor neorientate ........................................................................................................................................................................................................ 7

matricea de adiacenta .................................................................................................................................................................................................................... 7

listele vecinilor ................................................................................................................................................................................................................................ 7

vectorul muchiilor ........................................................................................................................................................................................................................... 7

Moduri de memorare ale unui graf ............................................................................................................................................................................................................ 7

Proprietatile matricei : ................................................................................................................................................................................................................................ 9

Vectorul muchiilor. ..................................................................................................................................................................................................................................... 9

Parcurgerea grafurilor ..............................................................................................................................................................................................................................12

Algoritmul de parcurgere in latime BF (Breadth First); ............................................................................................................................................................................14

Algoritmul de parcurgere in adancime DF (Depth First); .....................................................................................................................................................................15

Aplicatie ....................................................................................................................................................................................................................................................16

In C++ vom afisa matricea de adiacenta: ..................................................................................................................................................................................................17

Calcularea gradelor nodurilor ...................................................................................................................................................................................................................18

Parcurgerea in latime: ..............................................................................................................................................................................................................................19

CONEXITATE ..............................................................................................................................................................................................................................................22

Definiţie -lant ............................................................................................................................................................................................................................................23

Sa se afiseze un lant de lungime minima intre nodurile a si b: ................................................................................................................................................................26

Se numeşte graf hamiltonian ....................................................................................................................................................................................................................29

Grafuri hamiltoniene si euleriene .............................................................................................................................................................................................................31

Page 2: Definiţie - C++informatik.ddbuftea.ro/grafuritr.pdf · 4 Definiţie : Un graf parţial al grafului G=(X,U) este un graf G1(X,V) astfel încât V U, adică G1 are aceeaşi mulţime

2

Page 3: Definiţie - C++informatik.ddbuftea.ro/grafuritr.pdf · 4 Definiţie : Un graf parţial al grafului G=(X,U) este un graf G1(X,V) astfel încât V U, adică G1 are aceeaşi mulţime

3

Notiuni de bazã : Definitii:grad, subgraf :

http://portal.edu.ro/bac2012/materiale/TIC_011/M1/index.html

GRAFURI NEORIENTATE

Definiţie: Se numeşte graf neorientat o pereche ordonată de mulţimi (X,U), X

fiind o mulţime de elemente numite noduri sau vâfuri, iar U o mulţime din X

numite muchii.

Pentru graful de mai sus avem:

X={1, 2, 3, 4, 5, 6, 7, 8} :noduri

U={(1,2), (1,4), (1,5), (2,3), (2,5), (3,4), (6,7)} ;muchii

Dacă u1şi u2 sunt două muchii ce au o extremitate comună ele se vor numi

adiacente.

Page 4: Definiţie - C++informatik.ddbuftea.ro/grafuritr.pdf · 4 Definiţie : Un graf parţial al grafului G=(X,U) este un graf G1(X,V) astfel încât V U, adică G1 are aceeaşi mulţime

4

Definiţie : Un graf parţial al grafului G=(X,U) este un graf G1(X,V) astfel încât V U,

adică G1 are aceeaşi mulţime de vârfuri ca G, iar muţimea de muchii V este chiar U sau o

submulţime a acesteia.

Se numeste graf partial daca se pastreaza nodurile si se suprima niste muchii

Ex. Mai jos avem un graf parţial al grafului de mai sus (Fig. 1)

Cu alte cuvinte, un graf parţial al unui graf se obţine păstrând aceeaşi mulţime de

noduri şi eliminând o parte din muchii.

Definiţie : Un subgraf al unui graf G=(X,U) este un graf H(Y,V) astfel încât Y X

iar V conţine toate muchiile din U care au ambele extremităţi în Y. Vom spune că

subgraful H este indus sau generat de mulţimea de vârfuri Y.

Se numeste subgraf daca se elimina niste noduri

Ex. Mai jos avem un subgraf al grafului din Fig. 1 obţinut prin eliminarea nodului 3

Page 5: Definiţie - C++informatik.ddbuftea.ro/grafuritr.pdf · 4 Definiţie : Un graf parţial al grafului G=(X,U) este un graf G1(X,V) astfel încât V U, adică G1 are aceeaşi mulţime

5

Definiţie : Gradul unui vârf x este numărul muchiilor incidente cu x.

Gradul vârfului x se notează d(x).

Ex. în Fig. 1 : d(1)=3 ; d(4)=2 ; d(8)=0 ; d(6)=1 ;

Un vârf care are gradul 0 se numeşte vârf izolat.

Un vârf care are gradul 1 se numeşte vârf terminal.

Propoziţia 1 : Dacă un graf G(X,U) are m muchii şi n vârfuri, iar X={x1,x2,...,xn}

atunci suma gradelor fiecarui nod este dublul muchiilor :

d(x1)+d(x2)+...+d(xn)=2*m ;

Corolar : În orice graf G există un număr par de vârfuri cu grad impar.

Page 6: Definiţie - C++informatik.ddbuftea.ro/grafuritr.pdf · 4 Definiţie : Un graf parţial al grafului G=(X,U) este un graf G1(X,V) astfel încât V U, adică G1 are aceeaşi mulţime

6

Definiţie : Se numeşte graf complet cu n vârfuri un

graf care are proprietatea că orice două noduri diferite sunt

adiacente.

4 varfuri are : 4*(4-1)/2=6 muchii

Propoziţia 2 : Un graf complet Kn are n(n-1)/2 muchii.

Definiţie: Un graf G=(X,U) se numeşte bipartit dacă

există două mulţimi nevide A, B astfel încât X=A U B, A∩B

Page 7: Definiţie - C++informatik.ddbuftea.ro/grafuritr.pdf · 4 Definiţie : Un graf parţial al grafului G=(X,U) este un graf G1(X,V) astfel încât V U, adică G1 are aceeaşi mulţime

7

= şi orice muchie a lui G are o extremitate în A iar cealaltă în B.

Unele noduri din A pot fi adiacente cu nodurile din B

Definiţie: Un graf bipartit complet dacă pentru orice x din

A şi y din B, există muchia (x,y).

toate noduriledin A sunt adiacente cu nodurile din B

Reprezentarea grafurilor neorientate

Cele mai cunoscute forme de reprezentare ale unui astfel de graf sunt:

matricea de adiacenta,

listele vecinilor si

vectorul muchiilor.

Moduri de memorare ale unui graf

Page 8: Definiţie - C++informatik.ddbuftea.ro/grafuritr.pdf · 4 Definiţie : Un graf parţial al grafului G=(X,U) este un graf G1(X,V) astfel încât V U, adică G1 are aceeaşi mulţime

8

1. Lista vecinilor : Putem memora graful dând pentru fiecare nod mulţimea nodurilor cu

care formează arce în care el este pe prima poziţie. x1 { x2, x3,x5}

x2 { x1, x3 }

x3 {x1, x2}

x4 { 0}

x5 { x1 }

x6 { x10, x7}

x7 { 6,8}

x8 { 9,7 }

x9 { x10, x8}

x10 { x6, x9}

2. Un graf poate fi memorat printr-o matrice pătratică booleană, de dimensiune egală cu

numărul de noduri, în care o poziţie aij va fi 1 dacă există muchia (xi,xj) şi 0 în caz

contrar, numită matricea adiacenţelor directe.

x1 x2 x3 x4 x5 x6

x1 0 1 1 1 1 0

x2 1 0 1 1 1 1

x3 1 1 0 0 0 0

x4 1 1 0 0 1 1

x5 1 1 0 1 0 0

x6 0 0 0 1 0 0

Page 9: Definiţie - C++informatik.ddbuftea.ro/grafuritr.pdf · 4 Definiţie : Un graf parţial al grafului G=(X,U) este un graf G1(X,V) astfel încât V U, adică G1 are aceeaşi mulţime

9

Proprietatile matricei : 1. Este o matrice simetrica

2. Elementele de pe diagonala principale sunt egale cu 0

3. Suma elementelor pe lini i sau coloana j este egala cu gradul nodului i

4. Daca toate elementele pe linia/ coloana i sunt egale cu 0 atunci nodul este izolat

5. Daca toate elementele sunt egale cu 1 mai putin cele de pe DP atunci inseamna ca

graful este complet

Vectorul muchiilor.

Fiecare muchie a grafului poate fi privita ca o inregistrare cu doua componente: cele doua

varfuri care constitue extremitatile muchiei. Notand aceste extremitati cu nod1 si nod2, putem

defini tipul de date tmuchie, astfel:

int tmuchie

{ int nod1, nod2;

};

Graful in ansamblul sau, este o multime de muchii, adica o multime de elemente de tipul

tmuchie.In consecinta definim graful ca un “vector de muchii”, adica un vector cu elementele

de tipul muchie:

tmuchie vector[25];

Page 10: Definiţie - C++informatik.ddbuftea.ro/grafuritr.pdf · 4 Definiţie : Un graf parţial al grafului G=(X,U) este un graf G1(X,V) astfel încât V U, adică G1 are aceeaşi mulţime

10

Exemplul 2: Reprezentăm graful de mai sus prin cele două metode :

1.

0000000

0010000

0100000

0000110

0001010

0001101

0000010

A 2.

7

56

65

3,24

4,23

4,3,12

21

_

.

vecinilorlistanodul

Def. Fie graful G = (X,U). Un graf parţial se obţine din G păstrând toate vârfurile

şi suprimând nişte muchii.

Def. Fie graful G = (X,U). Un subgraf al lui G se obţine din G eliminând nişte vârfuri şi

păstrând doar acele muchii care au ambele extremităţi în mulţimea vârfurilor rămase.

Ex :

-graful initial

Page 11: Definiţie - C++informatik.ddbuftea.ro/grafuritr.pdf · 4 Definiţie : Un graf parţial al grafului G=(X,U) este un graf G1(X,V) astfel încât V U, adică G1 are aceeaşi mulţime

11

a. Eliminam muchiile care trec prin nodul 4 → graf partial

Am eliminat muchiile u3 şi u4, păstrând toate vârfurile.

b. Eliminăm vârfurile 5,6,7 şi muchiile corespunzătoare(u5) → subgraf

Page 12: Definiţie - C++informatik.ddbuftea.ro/grafuritr.pdf · 4 Definiţie : Un graf parţial al grafului G=(X,U) este un graf G1(X,V) astfel încât V U, adică G1 are aceeaşi mulţime

12

Parcurgerea grafurilor

Ne amintim:

Ce este un graf? Se numeşte graf neorientat o pereche ordonată de mulţimi (X,U), X fiind o mulţime

de elemente numite noduri sau vâfuri, iar U o mulţime de perechi neordonate

numite muchii.

Ce este un graf

partial?

Se numeste graf partial daca se pastreaza nodurile si se suprima niste muchii

Ce este un subgraf? Se numeste subgraf daca se elimina niste noduri dintr-un graf

Cum aflam gradul

unui nod?

Gradul unui nod x este egal cu numărul muchiilor adiacente cu x.

Construim matricea de adiacenta si suma de ‘1’ de pe fiecare linie este egal cu

gradul nodului i de pe linia i

Care sunt

proprietatile unei

matrice de

adiacenta?

(reprezentarea

grafului in

memorie)

Este o matrice simetrica

Elementele de pe diagonala principale sunt egale cu 0

Suma elementelor pe lini i sau coloana j este egala cu gradul nodului i

Daca toate elementele pe linia/ coloana i sunt egale cu 0 atunci nodul este izolat

Dac toate elementele sunt egale cu 1 mai putin cele de pe DP atunci inseamna ca

graful este complet

Page 13: Definiţie - C++informatik.ddbuftea.ro/grafuritr.pdf · 4 Definiţie : Un graf parţial al grafului G=(X,U) este un graf G1(X,V) astfel încât V U, adică G1 are aceeaşi mulţime

13

http://portal.edu.ro/bac2012/materiale/TIC_011/M8/index.html

1) parcurgere in latime BF (Breadth First):

6,3,5,1,4,2

2) parcurgere in adancime DF (Depth First):

6,3, 1,2,4,5

Page 14: Definiţie - C++informatik.ddbuftea.ro/grafuritr.pdf · 4 Definiţie : Un graf parţial al grafului G=(X,U) este un graf G1(X,V) astfel încât V U, adică G1 are aceeaşi mulţime

14

Algoritmul de parcurgere in latime BF (Breadth First);

Metoda consta in:

1) se viziteaza varful de pornire,

2) se viziteaza toate varfurile adiacente in ordine crescatoare,

3) in ordine crescatoare se alege primul varf adiacent cu varful de pornire si se

viziteaza toate varfurile adiacente cat timp este posibil.

Exemplul 1:

Presupunem ca varful de pornire este 1,atunci parcurgerea BF este:1,2,5,6,3,4,7.

Pentu 3 varf de pornire:3,2,4,1,5,6,7.

Pentru implementare vom folosi :

1) un vector care are proprietatile unei cozi, fie

c=(c1,c2,…,ck). Capetele de intoducere si

extragere vor fi identificate prin pozitiile p si

respectiv u.

2) Mai avem nevoie de un vector viz cu n elemente, in care elementele viz[k]

(k=1,2,….,n) au semnificatia: viz*i+=0, daca varful i nu a fost vizitat sau viz[i]=1daca a

fost vizitat. Mai intai initializam tot vectorul viz cu 0.

Page 15: Definiţie - C++informatik.ddbuftea.ro/grafuritr.pdf · 4 Definiţie : Un graf parţial al grafului G=(X,U) este un graf G1(X,V) astfel încât V U, adică G1 are aceeaşi mulţime

15

Initial in coada se gaseste varful de pornire: p=1, u=1, c[p]:=x, viz[x]:=1.

Cat timp mai sunt elemente in coada(“while p<=u”):

Extragem din coada varful aflat in capatul de extragere u, si-l memoram intr-o variabila

z{z:=c[p]};

Pe linia z in a cautam vecinii lui z si ii introducem in coada.

Algoritmul de parcurgere in adancime DF (Depth First);

Metoda consta in: 1) alegem varful de pornire, 2) se alege primul vecin al sau nevizitat inca, 3) pentru acest vecin cautam primul vecin al sau

nevizitat si asa in continuare. 4) In cazul in care un varf nu mai are vecini

nevizitati atunci ne intoarcem la nodul anterior, iar pentru acel nod cautam urmatorul vecin nevizitat al sau.

Pentru graful de mai sus parcurgerea in adancime plecand de la varful 1 este: 1,2,3,4,6,7,5. Pentru a implementa vom folosi o stiva si metoda backtracking.

Page 16: Definiţie - C++informatik.ddbuftea.ro/grafuritr.pdf · 4 Definiţie : Un graf parţial al grafului G=(X,U) este un graf G1(X,V) astfel încât V U, adică G1 are aceeaşi mulţime

16

Aplicatie

Construirea matricei de adiacenta: Se considera urmatorul graf:

Page 17: Definiţie - C++informatik.ddbuftea.ro/grafuritr.pdf · 4 Definiţie : Un graf parţial al grafului G=(X,U) este un graf G1(X,V) astfel încât V U, adică G1 are aceeaşi mulţime

17

In C++ vom afisa matricea de adiacenta:

else cout<<a[i][j]<<" "; cout<<endl;}}

Page 18: Definiţie - C++informatik.ddbuftea.ro/grafuritr.pdf · 4 Definiţie : Un graf parţial al grafului G=(X,U) este un graf G1(X,V) astfel încât V U, adică G1 are aceeaşi mulţime

18

Calcularea gradelor nodurilor

cout<<" nodurile la dreapta muchiei: "<<i; cin>>y; a[x][y]=1; a[y][x]=1; }

Page 19: Definiţie - C++informatik.ddbuftea.ro/grafuritr.pdf · 4 Definiţie : Un graf parţial al grafului G=(X,U) este un graf G1(X,V) astfel încât V U, adică G1 are aceeaşi mulţime

19

for(i=1;i<=n;i++) //afisare grad nod cout<<"varful "<<i<<" are gradul "<<grad(i)<<endl; }

Parcurgerea in latime:

Page 20: Definiţie - C++informatik.ddbuftea.ro/grafuritr.pdf · 4 Definiţie : Un graf parţial al grafului G=(X,U) este un graf G1(X,V) astfel încât V U, adică G1 are aceeaşi mulţime

20

Page 21: Definiţie - C++informatik.ddbuftea.ro/grafuritr.pdf · 4 Definiţie : Un graf parţial al grafului G=(X,U) este un graf G1(X,V) astfel încât V U, adică G1 are aceeaşi mulţime

21

Metoda consta in:

-alegem varful de pornire, pentru acesta se alege primul vecin al sau nevizitat inca,pentru acest

vecin cautam primul vecin al sau nevizitat si asa in continuare. In cazul in care un varf nu mai

are vecini nevizitati atunci ne intoarcem la nodul anterior, iar pentru acel nod cautam urmatorul

vecin nevizitat al sau.

Page 22: Definiţie - C++informatik.ddbuftea.ro/grafuritr.pdf · 4 Definiţie : Un graf parţial al grafului G=(X,U) este un graf G1(X,V) astfel încât V U, adică G1 are aceeaşi mulţime

22

Pentru graful de mai sus parcurgerea in adancime plecand de la varful 1 este: 1,2,3,4,5,6,7.

Pentru a implementa vom folosi o stiva si metoda backtracking.

CONEXITATE

Prin parcurgerea in latime acelui graf am subliniat o

proprietate importanta a grafului:faptul ca in urma

parcurgerii au fost vizitate toate varfurile.

Luand oricare doua varfuri,putem gasi cel putin un traseu care porneste dintr-un varf si

ajunge in celalalt.

Luand oricare doua varfuri, ele pot fi legate printr-un lant. Dar nu toate grafurile sunt conexe. In schimb putem desprinde din el “portiuni” care, fiecare

luata separat, este un graf conex.

Exemplu:

Se numeste componenta conexa a grafului G=(X,U), un subgraf G1=(X1,U1) a lui G,

conex, cu proprietatea ca nu exista nici un lant care sa lege un varf din X1 cu un varf din

X-X1.

Fie G=(X,U) un graf neorientat, X={x1,x2,..,xn}.

Page 23: Definiţie - C++informatik.ddbuftea.ro/grafuritr.pdf · 4 Definiţie : Un graf parţial al grafului G=(X,U) este un graf G1(X,V) astfel încât V U, adică G1 are aceeaşi mulţime

23

Definiţie -lant: Se numeşte lanţ în G succesiunea de vârfuri L={xi1,xi2,...,xik} cu

proprietate că orice două noduri consecutive din lant sunt adiacente, adică (xi1,xi2),

(xi2,xi3), ..., (xik-1,xik) U

Dacă vârfurile xi1, xi2, ..., xik sunt diferite două câte două atunci lanţul se

numeşte elementar. În caz contrar, lanţul este neelementar.

ex. L1=[1, 2, 4] – lanţ elementar

L2=[1, 2, 3, 1, 2, 4] – lanţ neelementar

Definiţie : Se numeşte ciclu în G un lanţ L pentru care xi1=xik şi toate muchiile

adiacente (xi1, xi2), (xi2, xi3), ..., (xik-1, xik) sunt diferite.

Ex. C=[1, 2, 3, 1] este un ciclu

Definiţie : Se numeşte ciclu elementar un ciclu care are proprietate că oricare

două vârfuri ale sale, cu excepţia primului şi ultimului, sunt diferite două câte două.

Ex. C1=[1, 2, 3, 1] este ciclu elementar.

C2=[3, 1, 2, 4, 8, 2, 3] este un ciclu neelementar.

Definiţie : Un graf G se numeşte conex dacă pentru orice două vârfuri x şi y

diferite ale sale există un lanţ ce le leagă.

Page 24: Definiţie - C++informatik.ddbuftea.ro/grafuritr.pdf · 4 Definiţie : Un graf parţial al grafului G=(X,U) este un graf G1(X,V) astfel încât V U, adică G1 are aceeaşi mulţime

24

Definiţie : Se numeşte componentă conexă a grafului G=(X,U) un subgraf

C=(X1,U1), conex, al lui G care are proprietatea că nu există nici un lanţ care să lege un

vârf din X1 cu un vârf din X-X1.

Def. 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ă.

Def. Dacă într-un ciclu, toate vârfurile cu excepţia primului şi a ultimului sunt distincte

două câte două, atunci ciclu se numeşte elementar. In caz contrar, el este ne-elementar.

L1 = (1,2,3,4) - lanţ elementar

L2 = (1,2,4,3,2,3,4) - lanţ ne-elementar

L3 = (2,4,3,2,1) – lanţ ne-elementar

L4 = (6,5,1,2,3,4) -lanţ elementar

Page 25: Definiţie - C++informatik.ddbuftea.ro/grafuritr.pdf · 4 Definiţie : Un graf parţial al grafului G=(X,U) este un graf G1(X,V) astfel încât V U, adică G1 are aceeaşi mulţime

25

C1 = (2,3,4,2) - ciclu elementar

C2 = (1,2,4,3,1) - ciclu elementar

C3 = (5,2,4,3,1,5) - ciclu elementar

C4 = (1,2,3,4,2,5,1) - ciclu ne-elementar

C5 = (5,2,3,4,2,1,5) - ciclu ne-elementar

Obs. In cadrul unui lanţ, muchiile se pot repeta, dar în cadrul unui ciclu ele trebuie să fie

distincte.

Def. Un graf G este conex dacă oricare ar fi două vârfuri ale sale, există un lanţ care le

leagă.

Obs. Intr-un graf conex, luând oricare două vârfuri , putem găsi cel putin un traseu(lanţ)

care porneşte dintr-un vârf şi ajunge în celălalt.

Page 26: Definiţie - C++informatik.ddbuftea.ro/grafuritr.pdf · 4 Definiţie : Un graf parţial al grafului G=(X,U) este un graf G1(X,V) astfel încât V U, adică G1 are aceeaşi mulţime

26

Def. Se numeşte componentă conexă a grafului G =(X,U), un subgraf G1=(X1,U1) a lui

G,conex, cu proprietatea că nu există nici un lanţ care să lege un vârf din X1 cu un vârf din

X-X1.

Ex.

In acest exemplu exista 3 componente conexe

- G1 =(X1,U1), cu X1=,1,2,3,4- şi U1={u1,u2,u3,u4} - G2 =(X2,U2), cu X2=,5,.6- şi U2={u5} - G3 =(X3,U3), cu X3={7- şi U1= Ø

Sa se afiseze un lant de lungime minima intre nodurile a si b:

Exista un lant de la a la b daca si numai daca o percurgere DF sau BF porneste de la a si ajunge sa viziteze nodul b.

Page 27: Definiţie - C++informatik.ddbuftea.ro/grafuritr.pdf · 4 Definiţie : Un graf parţial al grafului G=(X,U) este un graf G1(X,V) astfel încât V U, adică G1 are aceeaşi mulţime

27

Page 28: Definiţie - C++informatik.ddbuftea.ro/grafuritr.pdf · 4 Definiţie : Un graf parţial al grafului G=(X,U) este un graf G1(X,V) astfel încât V U, adică G1 are aceeaşi mulţime

28

Page 29: Definiţie - C++informatik.ddbuftea.ro/grafuritr.pdf · 4 Definiţie : Un graf parţial al grafului G=(X,U) este un graf G1(X,V) astfel încât V U, adică G1 are aceeaşi mulţime

29

Def. Se numeşte ciclu hamiltonian într-un graf, un ciclu elementar care conţine toate

vârfurile grafului.

Se numeşte graf hamiltonian un graf care conţine un ciclu hamiltonian.

Ex

Graful din acest exemplu este hamiltonian, deoarece ciclu C =[2,5,1,3,4,2] este

elementar (pleacă din vârful 2 şi se întoarce tot în 2, iar muchiile *2,5+, *5,1+, *1,3+, *3,4+,

*4,2+ sunt distincte două câte două) şi în plus conţine toate vârfurile.

Def. Se numeşte lanţ hamiltonian într-un graf, un lanţ elementar care conţine toate

vârfurile grafului.

Page 30: Definiţie - C++informatik.ddbuftea.ro/grafuritr.pdf · 4 Definiţie : Un graf parţial al grafului G=(X,U) este un graf G1(X,V) astfel încât V U, adică G1 are aceeaşi mulţime

30

Ex L = [2,5,1,3,4]

Th. Dacă într-un graf G=(X,U) cu n 3 vârfuri, gradul fiecărui vârf verifică condiţia 2

)(n

xd ,

atunci graful este hamiltonian.

Def. Se numeşte ciclu eulerian într-un graf un ciclu care conţine toate muchiile

grafului.

Def: Se numeşte graf eulerian un graf care conţine un ciclu eulerian.

Ex.

Pentru acest graf, ciclu C = *2,1,5,2,3,4,2+ este eulerian, deoarece pleacă din 2 şi se

întoarce tot în doi, iar muchiile sale consecutive, adica [2,1], [1,5], [5,2], [2,3], [3,4], [4,2]

sunt distincte două câte două şi reprezintă toate muchiile grafului.

Page 31: Definiţie - C++informatik.ddbuftea.ro/grafuritr.pdf · 4 Definiţie : Un graf parţial al grafului G=(X,U) este un graf G1(X,V) astfel încât V U, adică G1 are aceeaşi mulţime

31

Th. Un graf fără vârfuri izolate este eulerian dacă şi numai dacă este conex şi gradele

tuturor vârfurilor sunt numere pare.

Grafuri hamiltoniene si euleriene

Se numeste ciclu hamiltonian intr-un graf, un ciclu elementar

care contine toate varfurile grafului.

Un graf care contine un ciclu hamiltonian se numeste graf

hamiltonian.

Un lant elementar care contine toate varfurile grafului se

numeste lant hamiltonian.

Un graf hamiltonian are cel putin trei varfuri.

Graful complet cu n varfuri este un graf hamiltonian.

Teorema:

Page 32: Definiţie - C++informatik.ddbuftea.ro/grafuritr.pdf · 4 Definiţie : Un graf parţial al grafului G=(X,U) este un graf G1(X,V) astfel încât V U, adică G1 are aceeaşi mulţime

32

Fie G=(X,U), cu n>=3 varfuri, daca oricare ar fi x un nod al

grafului si d(x)>=n/2, atunci graful este hamiltonian.

Se numeste ciclu eulerian intr-un graf, un ciclu care contine

toate muchiile grafului.

Un graf care contine un ciclu eulerian se numeste graf

eulerian.

Un lant eulerian este un lant care contine toate muchiile

grafului.

Teorema:

Un graf fara varfuri izolate este eulerian, daca si numai daca este

conex si gradele tuturor varfurilor sunt numere pare