teorie grafuri neorientate

7/24/2019 Teorie grafuri neorientate

1/9

Teorie grafuri neorientate

Definitie :Se numeste graf neorientatG o pereche de multimi (X,), unde X este

o multime finita si nevida de elemente, iar U o multime de perechi cu elemente distincte din

multimea X.

Terminologie:

Elementele multimii X se numesc nodurisau varfuri.Multimea X se mai numeste si multimea

nodurilorsau varfurilor.

Ordinul grafuluireprezinta numarul de noduri ale grafului.

Elementele multimii U se numescmuchii. Multimea U se mai numeste si multimea muchiilor.

umim noduri adiacenteorice pereche de noduri care formeaza o muchie. !iecare din celedoua noduri spunem, ca sunt incidentecu muchia pe care o formeaza.

Se numesc muchii incidente doua muchii care au o e"tremitate comuna.

#n memoria calculatorului un graf neorientat se reprezinta cu a$utorul matricii de adiacenta notata

cu %(i,$).

Matricea de adiacentaeste o matrice patratica si simetrica fata de diagonala principala.

E"emplu de matrice patratica&
http://2.bp.blogspot.com/_krWzCjzuO0s/S-qwlpuz47I/AAAAAAAAAEA/_SrT7XQW4QI/s1600/pt+blog.bmp


2/9

Definitie:Gradul unui nod " al grafului G este egal cu numarul muchiilor incidente cu nodul si

se noteaza cu d(").

Terminologie:

Se numeste nod terminalun nod care are gradul egal cu '.Se numeste nod izolatun nod care are gradul .

X*',+,,-,,/0

U*(',+),(',/),(+,/),(,)0

nodurile ' si + sunt nodurile vecine nodului /1nodurile si sunt noduri terminale1

nodul - este nod izolat.
http://2.bp.blogspot.com/_krWzCjzuO0s/S-qVkH75m3I/AAAAAAAAACQ/RxRkfJdlHlk/s1600/grafblog1.bmphttp://1.bp.blogspot.com/_krWzCjzuO0s/S-EC0g0TvNI/AAAAAAAAABc/KudWpDd6AR8/s1600/dannymeu.bmphttp://1.bp.blogspot.com/_krWzCjzuO0s/S-ECmK2J7bI/AAAAAAAAABU/Vn2yF_wNNec/s1600/dannymeu22.bmp


3/9

Teoreme:

umarul total de grafuri cu n noduri este&

2.Suma gradelor tuturor nodurilor unui graf neorientat este egala cu du2lul numarului de muchii.

3.3aca graful G neorientat are nnoduri, n4+, atunci cel putin + noduri au acelasi grad.

4.5entru orice grad neorientat numarul nodurilor de grad impar este par.

5.umarul minim de muchii pe care tre2uie sa le ai2a un graf neorientat cu n noduri, ca sa nu

e"iste noduri izolate este&

Se numeste lantintr6un graf neorientat o succesiune de varfuri cu proprietatea ca intre oricare

doua varfuri(noduri) alaturate e"ista o muchie.

umim lant elementaro succesiune de varfuri care respecta proprietatea de lant si6n care

oricare doua varfuri sunt distincte. #n caz contrar lantul se numeste neelementar.

7anturile sunt&
http://3.bp.blogspot.com/_krWzCjzuO0s/S-EGL5SYlmI/AAAAAAAAABs/TuB66s-MEO4/s1600/boring.bmphttp://2.bp.blogspot.com/_krWzCjzuO0s/S96cLTDsisI/AAAAAAAAAAU/dNTopggFT2M/s1600/dkjgbfcuysgeyufwge.bmp


4/9

-simle:o succesiune de varfuri cu proprietatea ca fiecare muchie este vizitata o singura data.

-comuse: in care o muchie este vizitata de doua ori.

Se numeste cicluintr6un lant neorientat o succesiune de varfuri cu proprietatea ca primul nod

coincide cu ultimul.

Se numeste graf artialnotat cu Gp(",v), cu proprietatea ca multimea v de perechi de varfuri

este inclusa in multimea ".

imaginea +

imaginea '

#maginea ' prezinta un graf oarecare iar imaginea + prezinta graful partial al primului prin

eliminarea muchilor (',+) si (+,-).

Se numestesu!graf al unui graf G(X,U) , un graf Gs(8,v) cu proprietatea ca multimea 89X si

v9U si v este formata din valori distincte ale multimii 8.
http://4.bp.blogspot.com/_krWzCjzuO0s/S-qqanwxZbI/AAAAAAAAADY/cKR0k3Eog9M/s1600/grafblog4.bmphttp://4.bp.blogspot.com/_krWzCjzuO0s/S-qoe43ErlI/AAAAAAAAADQ/QrxcxJYLoHc/s1600/grafblog2.bmp


5/9

%m transformat din graf in su2graf eliminand un nod&

Matricea si graful dupa eliminarea nodului&

Grafuri speciale&

6graful nul& graful care are multimea U1
http://1.bp.blogspot.com/_krWzCjzuO0s/S-qnUFSIWyI/AAAAAAAAADI/i4L2ZUTrWG4/s1600/matrice+blog2.bmphttp://4.bp.blogspot.com/_krWzCjzuO0s/S-qnHMor2QI/AAAAAAAAADA/y57KC_MtP-8/s1600/grafblog3.bmphttp://1.bp.blogspot.com/_krWzCjzuO0s/S-qkkU5HtKI/AAAAAAAAAC4/qZJJBf_uLNw/s1600/matrice+blog1.bmphttp://2.bp.blogspot.com/_krWzCjzuO0s/S-qhmqZreVI/AAAAAAAAACY/CSxF3r_lVP0/s1600/grafblog2.bmp


6/9

6graful complet cu noduri& graful care are intre oricare doua noduri adiacente o muchie.

E"emplu de graf complet&

Teorie grafuri orientate

G"#$%"& O"&'(T#T'

3efinitieSe nume te graf orientatnotat cu G o pereche ordonat: de mul imi *X,U0 G *X,U0

unde X este mul imea v;rfurilor si U este multimea arcelor.
http://4.bp.blogspot.com/_krWzCjzuO0s/S-GhmtYmjII/AAAAAAAAAB0/ltcCeT9ecX8/s1600/untitled.bmphttp://3.bp.blogspot.com/_krWzCjzuO0s/S-qtqB3OlYI/AAAAAAAAADg/k8IwRfGhl7Q/s1600/grafcomplet.bmp


7/9

X*',+,,-,0

U*(',+)1(',)1(+,)1(-,+)1(-,)0

MATRICEA DE ADIACENTA.

Matricea de adiacenta asociata unui graf orientat este patratica si nesimetrica&a


8/9

.Un graf cu mai mult de + noduri este hamiltonian daca gradul fiecarui nod este 4n>+.

-. Un graf ce nu contine grafuri izolate este eulerian daca si numai daca este cone" si gradele

tuturor nodurilor sunt pare.. umarul de cicluri hamiltoniene dintr6un graf complet cu n noduri este

/. ?rice graf turneu contine un drum elementar care trece prin toate nodurile grafului.

@. 5entru orice graf turneu, e"ista un nod ", astfel incat toate nodurile 8A" sunt accesi2ile din "pe un drum care contine un arc sau doua arce.

GRAFURI SPECIALE.

Graful G se numeste graf !iartit daca e"ista + multimi nevide de noduri % si B care au

urmatoarele proprietati& #u+, si #n+, multimea vidasi orice muchie(arc) din multimea U

are o e"tremitate in multimea de noduri % si o alta e"tremitate in multimea de noduri B.Graful 2ipartit se numeste graf !iartit comletdaca pentru orice nod "i care apartine lui % si

orice nod "jcare apartine lui B e"ista o muchie ( un arc ) formata din cele + noduri care apatin

multumii U( < "i, "j =e U).

Graful GT' este graf 2ipartit.

%*',,0

B*+,-,/,@0

GT'

Graful GT+ este 2ipartit complet.%* ',+0

B*,/,@0
http://4.bp.blogspot.com/_krWzCjzuO0s/S-G83rLCGcI/AAAAAAAAACE/SfpgYvJknsI/s1600/gt2.bmphttp://2.bp.blogspot.com/_krWzCjzuO0s/S-G5sY4pwGI/AAAAAAAAAB8/Ep8ARcQWBJQ/s1600/GT1.bmp


9/9

GT+

umim lant hamiltonian un lant elementar ce contine toate nodurile grafului.

antul elementareste lantul care contine numai noduri distincte.

umim ciclu hamiltonianun ciclu elementar ce contine toate nodurile grafului.

Un graf ce contine un ciclu hamiltonianse numeste graf hamiltonian.

umim ciclu eulerianun ciclu ce contine toate muchiile grafului.

Un graf ce contine un ciclu eulerianse numeste graf eulerian.

Un graf orientat in care , intre oricare + noduri e"ista un singur arc si numai unul se numeste graf

turneu.

teorie grafuri neorientate

Documents