Grafuri neorientate

7/21/2019 Grafuri neorientate

http://slidepdf.com/reader/full/grafuri-neorientate-56da422d81eb4 1/24

Grafuri neorientate

Niculae Andreea



Ce este un graf neorientat?

Se numeste graf neorientat si se noteazaG=(X,U) perechea ordonata de multimi X si Uunde:

X este o multime nita si nevida de elemente

numite noduri sau varfuri; U este o multime nita de perechi neordonate

de elemente distincte din X numite muchii sauarce;

n cazul grafurilor neorientate se folosescnotiunile de nod si muchie, pe cand lagrafurile orientate se folosesc notiunile de varf



Cum se reprezinta grafic un grafneorientat?

"entru a reprezenta un graf neorientat folosimlinii pentru a reprezenta muchiile si punctepentru noduri! #e asemenea vom nota cu $n%numarul nodurilor si cu $m% numarul

muchiilor!

#oua noduri distincte pot unite de cel mult omuchie! #e e&emplu, muchia (',) unestenodul ' cu nodul ! #aca scriem (,') nereferim la aceeasi muchie! #e aceea perechea

este neordonata!

n dreapta este un graf neorientatreprezentat grac! re * noduri (n=*) si +muchii (m=+)!ezulta multimea X=-',,.,/,0,*1 simultimea U=-(',),(,.),(.,/),(/,0),(/,*),(0,'),(0,)1!



Ce este gradul ?

"entru a intelege ce este un grad, tre2uie sa stim cesunt adiacenta si incidenta! #oua noduri sunt adiacente daca e&ista o relatie intre

ele, adica daca e&ista o muchie care sa le uneasca! 3 muchie are doua e&tremitati (nodurile i si 4)!

cestea reprezinta pentru muchia respectiva nodurilela care muchia este incidenta!

ezulta gradul reprezinta numarul de muchiiincidente cu un nod sau numarul de noduri adiacente

(vecine) nodului respectiv! De exemplu, in graful nostru muchia (2,3) este

incidenta nodurilor 2 si 3, iar nodurile 4 si 6 suntadiacente, pe cand nodurile 2 si 4 nu sunt.



Lista de adiacenta (lista vecinilor)

Un graf neorientat poate avea o lista deadiacenta! "entru graful nostru, lista deadiacenta este:

Suma gradurilornodurilor unui graf

este du2lulnumarului de muchiidin graf!

5umarul ma&im de muchii dintr6un graf neorientat este n7(n6')8 9

Un nod izolat este un nod cu gradul !Un nod terminal este un nod cu gradul '! (e&: nodul *)



Graf partial

iind dat un graf neorientat G=(X,U) senumeste graf partial a lui G graful neorientat <=(X,) unde este o multime inclusa sauegala cu multimea U!

>u alte cuvinte, graful partial se o2tineeliminand din G una, mai multe sau niciomuchie! "ot eliminate toate muchiile!

Graful nul este graful in care se

elimina toate muchiile!

#e e&emplu, am eliminat muchia(/,*), (.,/) si (,0) din graful nostru!5oul graf este un graf partial!



Subgraf

iind dat graful neorientat G=(X,U) senumeste su2graf al lui G un graf neorientat ?=(5,@) unde 5AX, iar @BU si contine doaracele elemente din U care au am2ele

e&tremitati in multimea 5! >u alte cuvinte se elimina o parte din nodurile

sale si o parte din nodurile adiacente cuacesta! 5umarul ma&im de noduri ce pot

eliminate este n6'!m sters nodurile ' si * muchiilelor si asa am o2stinut su2grafulcu / noduri!



Graful complet

Un graf complet este un graf neorientat cu nnoduri si m muchii care contine numarulma&im de muchii!

m ma&im=n7(n6')8

Gradul ecarui nod din graful complet esteegal cu n6'!



Matricea de adiacenta

ie un graf neorientat G=(X,U) cu n noduri! Senumeste matrice de adiacenta a lui Gmatricea patratica cu n linii si n coloane cuelemente de forma a(i4)=' daca e&ista muchie

intre nodurile i si 4 si altfel!

"roprietati:C patraticaC 2inara, adica are elemente de sau de 're diagonala principala C simetrica fata de diagonala principala pentru ca e grafneorientatSuma elementelor de pe linia i8 coloana i reprezintagradul nodului

re 7m elemente nenule



#e e&emplu, avem in stanga un graf cu0 noduri si / muchii! 5odul . este unnod izolat (nu are nicio muchie)!

Sus avem matricea de adiacenta pentru graful nostru! "utemo2serva ca diagonala principala este , iar putem verica caeste corecta deorece suma tuturor elementelor de pe linie saude pe coloana este du2lul numarului de muchii (avem /

muchii, iar suma este D)!



Subprogramul pentru a citi elementelegrafului

nainte de a sti cum se face un su2programpentru matricea de adiacenta tre2uie sa citimnumarul de noduri si muchii!

n acest su2program am citit numarul denoduri (despre care se spune in pro2lemaca este cuprins intre si ') si numarul demuchii, care nu tre2uie sa depaseascanumarul ma&im de muchii!



Subprogramul in care construim matriceade adiacenta

Afisarea matricei de adiacenta



Matricea de incidenta

iind un graf neorientat G=(X,U) cu n noduri sim muchii se numeste matrice de incidenta agrafului G matricea cu elemente de forma

"roprietati:5u e totdeauna patraticaC 2inara, adica are elemente de sau de '

"entru acelasi graf, matricea de incidenta poate reprezentata diferit (nu e unica)Suma de pe ecare coloana este re 7m elemente nenule



#e e&emplu, in stanga avem un grafneorientat cu 0 noduri si + muchii!

Sus este matricea de incidenta pentru graf! "entru ca nueste patratica, nu avem o diagonala principala! "utemvedea ca suma elementelor de pe coloana este , iar sumade pe ecare linie reprezinta gradul nodului!



Construirea matricei de incidenta

Afisarea matricei de incidenta



Memorare prin vector

nsu2programulstruct retinemmuchiilegrafului!



LanturiEantul este o secventa de noduri ale unui graf neorientat G=(,C) cu

proprietatea ca oricare doua noduri consecutive din secventa lantsunt adiacente!

Eungimea unui lant este numarul de muchii din care este formatlantul!

Eantul simplu= lantul care contine numai muchii distincte!

Eant compus= lantul care nu este format numai din muchiidistincte!

Eant elementar= lantul care contine numai noduri distincte!

Ciclul

Un ciclu este un lant in care primul nod coincide cu ultimul!>iclul este elementar daca este format doar din noduridistincte, e&ceptie facand primul si ultimul! Eungimea unuiciclu nu poate !



=-',,.,/,0,*1U=-(',),(',.),(',0),(,0),(/,0)1

#e e&emplu, in graful neorientat demai sus un lant este .,',,0,',.,',0,/de lungime D, adica D muchii!Un lant elementar este .,',,0 de

lungime . sau lantul /,0,,',. delungime /! Un lant simplu este .,',,0,'sau /,0,'!

n cazul ciclurilor, un e&emplu este ciclul

',,0,',,0,'! Un ciclu elementar este ciclul',,0,'!



Graful bipartit

Un graf neorientat G=(,U) se numeste2ipartit daca e&ista doua multimi si Fincluse in X astfel incat multimile si F sa nuai2a niciun punct comun, reuniunea lor sa

constituie multime X si toate muchiile grafuluiau o e&tremitate in si cealalta in F! F

cesta este une&emplu de graf2ipartit complet!

cesta areproprietatea capentru orice nod& din si oricenod din F e&istamuchia (&,)!



Conexitate

Un graf G se numeHte graf cone& dacJ areproprietatea cJ pentru orice pereche denoduri distincte e&istJ un lanK care le leagJ!

#acJ un graf G nu este cone& se

numeHte componentJ cone&J a grafului, unsu2graf cone& al sJu ma&imal Ln raport cuaceastJ proprietate (conKine numJrul ma&imde noduri din graful G care au proprietatea cJ

sunt legate de un lanK)!



#e e&emplu, avem in stanga ungraf cu 0 noduri! cesta estealcatuit din doua componente

cone&e! "rima este alcatuita dinnodurile ',,. , iar cealalta dinnodurile / si 0!

n cazul in care ar mai e&ista unnod *, nod izolat, acesta ar alcatui

singur o componenta cone&a,graful devenind unul cu .componente cone&e!

*



Parcurgerea grafului neorientat "entru a parcurge un graf neorientat e&ista doua metode:

'! "arcurgerea in latime (F6 Freadth irst) ! "arcurgerea in adancime (#6 #epth irst)

"arcurgerea Ln lJKime Lncepe cu vMrful iniKial, denumit Hi vMrful destart! Se viziteazJ mai LntMi vMrful de start! Se viziteazJ Ln ordine toKivecinii nevizitaKi ai vMrfului de start! poi se viziteazJ Ln ordine toKivecinii nevizitaKi ai vecinilor vMrfului de start Hi aHa mai departe,pMnJ la epuizarea tuturor vMrfurilor accesi2ile din vMrful de start!

"arcurgerea in adancime Lncepe cu vMrful iniKial, denumit vMrful destart, care este Hi vizitat! Se viziteazJ apoi primul vecin nevizitat al

vMrfului de start! Se viziteazJ Ln continuare primul vecin nevizitat alprimului vecin al vMrfului de start, Hi aHa mai departe, mergMnd LnadMncime, pMnJ cMnd a4ungem Lntr6un vMrf care nu mai are vecininevizitaKi!



'

* .

+/ 0

"arcurgerea in latime:5od pornire ': 1 3 6 2 7 5 4 5od pornire .: 3 7 6 1 2 5 4

5od pornire *: 6 3 1 7 2 5 4

"arcurgerea in adancime:5od pornire ': 1 3 7 6 2 5

4

5od pornire .: 3 7 6 1 2 5

4

5od pornire *:6 3 7 1 2 5

4

Sus avem un e&emplu de

graf neorientat cu +noduri si + muchii!



Bibliografie

$Nanual de 53N<>, "rol real%, CdituraEOS Soft >aietul de clasa https:88infomm2r!Pordpress!com8categor8i6graf

uri8'6grafuri6neorientate8 http:88PPP!seap!usv!ro8Q

valeriul8lupu8GUR5C3C5<<C!pdf

http:88D!''!/!8'6''8>atedre8nformatica8''8"arcurgereR>one&itate!pdf

https://infommbr.wordpress.com/category/i-grafuri/1-grafuri-neorientate/



http://www.seap.usv.ro/~valeriul/lupu/GRAFURI_NEORIENTATE.pdf


http://89.121.249.92/2010-2011/Catedre/Informatica/11/Parcurgere_Conexitate.pdf












Grafuri neorientate

Documents

Transcript of Grafuri neorientate