probleme teoria grafurilor.doc

5/19/2018 Probleme teoria grafurilor.doc

1/31

UNIVERSITATEA DE STAT DIN MOLDOVA Facultatea de Matematic i Informatic

Sergiu ATARANIU

TEORIA GRAFURILORN PROBLEME I

APLICAII

!iinu " #$$%NO&IUNI DE 'A()

A* Defini+ia grafului* Su,grafuri


2/31

Perechea de mulimi ( )UX, , unde X este o mulime devid cu elemente distincte, iar U este format din perechineordonate de elemente din X , se numete graf neorientat.Elementele mulimii X se numesc vrfuri, iar elementelemulimii U muchiiale grafului.

Un graf determinat de perechea ( )UX, se noteaz prin( )UXG ,= . n cele ce urmeaz vom studia numai grafuri finite,

adic grafuri cu mulimile X i U finite. Graful ( )UXG ,= ,pentru care nX = , mU = , se numete ( )mn, -graf.e maispune c graful cu n v!rfuri este graf de ordin n . Pentru aspecifica, c X i Usunt mulimile de v!rfuri i respectiv demuchii ale unui graf G vom utiliza notaiile GX , GU .

"ac o muchie ju este determinat de perechea dev!rfuri ( )lk xx , , atunci vom scrie ( )lkj xxu ,= . n acest caz kxi lx se numesc extremitiale muchiei ju , iar #nsi v!rfurilese numesc adiacente. e spune, c fiecare dintre v!rfurile kx i

lx este incidentmuchiei ju i reciproc. $diacena dintre kx ,

lx se noteaz prin kx % lx . "ou muchii se numescadiacente, dac sunt incidente unui v!rf comun.

"ac ix este un v!rf al grafului ( )UXG ,= , atuncimulimea UxxXx jij ,& se numete vecintatea v!rfului

ix i se noteaz prin ( )iG x sau simplu ( )ix . Grad sauvalen a v!rfului Xxi este cardinalul mulimii ( )ix i senoteaz prin ixdeg , sau ( )ixg .


3/31

'ecintate a unei su(mulimi de v!rfuri XA a

grafului ( )UXG ,= se numete mulimea ( ) { &)AXzA =zA & % } . 'alena ma*im i valena minim a

v!rfurilor unui graf G se noteaz prin ( )G i ( )G , adic&

( ) { }xG Xx degma*= , ( ) { }xG Xx degmin= .'!rful Xx se numete izolat #n graful G , dac+deg =x i!u!"endatdac deg =x -v!rful suspendat se mai

numete vrf terminal. /uchia incident unui v!rf suspendat deasemenea se numete!u!"endat.

Pentru un ( )mn, 0graf ( )UXG ,= se verific cu uurinegalitatea

mxXx

1deg = .ntr0adevr vom o(serva c la calcularea sumei

Xx

xdeg fiecare muchie din graf se va numra de dou ori,

deoarece gradul unui v!rf mai poate fi considerat i ca numrulde muchii din graf, incidente acestui v!rf.

Graful, oricare dou v!rfuri ale cruia sunt adiacente, se

numete graf com"let i se noteaz prin n# . 2umrul de

muchii ale lui n# este( )1

1 = nn

$n . Graful ( )UXG 3= cu

%U /= se numetegraf vidi se noteaz prin n% , iar graful,pentru care =X , %U /= se numete graf trivial. "ac

XX , XX 1 , 1 XXX = , %XX /=1 i fiecare muchiea grafului ( )UXG 3= are o e*tremitate #n X , iar alta #n 1X ,atunci graful G se numete &i"artit i se noteaz prin

( )UXXG 3, 1= . Graful (ipartit, #n care fiecare v!rf din Xeste adiacent cu fiecare v!rf din 1X se numetegraf &i"artitcom"let.

4onform definiiei grafului neorientat mulimea GU arputea s conin muchii ale cror e*tremiti coincid. $stfel demuchii se numesc &ucle. "e asemenea, o pereche de v!rfuri


4/31

poate fi prezent de mai multe pro #n GU . n acest cazmulimea de muchii determinat de aceeai pereche de v!rfuri semai numete muchie multi"l. Graful, ce conine (ucle i muchiimultiple se numete"!eudograf, iar graful ce conine (ucle senumete multigraf.

Graful ( )UXG 3= se numete orientat, dac U este omulime de perechi ordonate de elemente din X . Grafulorientat se noteaz prin UXG 3= . Elementele mulimii U senumesc arce. Pentru arcul ( )xu ,= v!rful x este extremitateiniial, iar extremitate final. e spune c arcul ( )xu ,=este orientat de la x spre . '!rful X se mai numete"redece!orul vrfului , iar !ucce!orul vrfului X .

"in definiia grafului orientat rezult c perechile dev!rfuri ji xx , i ij xx , reprezint arce diferite. Graful

orientat UXG 3= , care pentru orice dou v!rfuri Xxx ji ,

nu conine #n acelai timp arcele ji x , i ij x , se numeteantisimetric, iar graful antisimetric cu un numr ma*im de arcese numeteturnir.

'emigradul exterior al unui v!rf Xxi , notat prin

( )ixg+ , al grafului UXG 3= este cardinalul mulimii( ) UxxXx jij ,& , adic este numrul succesorilor lui ix .

'emigradul interior al unui v!rf Xxi , notat prin( )ixg , al grafului UXG 3= este cardinalul mulimii

( ) UxxXx ijj ,& , adic este numrul predecesorilor lui ix .Gradul sau valena v!rfului ix al grafului orientat este

( ) ( ) ( )iii xgxgxg + += .n cazul grafului neorientat are loc egalitatea

( ) ( ) ( )iii xgxgxg + == . Graful, #n care gradele tuturor v!rfurilorsunt egale cu un numr k, se numetegraf k-regulat.

n cele ce urmeaz, dac nu se va concretiza #n modspecial, vom considera, c graful G este neorientat, fr (ucle

i muchii multiple. $stfel de grafuri se mai numesc grafuri


5/31

!im"le.Graf com"lementaral unui graf ( )UXG 3= este graful

G cu aceeai mulime de v!rfuri X , #n care dou v!rfuri suntadiacente dac i numai dac ele nu sunt adiacente #n G . Graful

( )G( , v!rfurile cruia corespund muchiilor grafului G i #n

care dou v!rfuri sunt adiacente dac i numai dac suntadiacente muchiile corespunztoare lor #n G , se numetegrafal muchiilorgrafului G .

"ou grafuri ( ) 3UXG = i ( )111 3UXG = se numescizomorfedac e*ist o aplicaie (i5ectiv 1& XX astfel #nc!t

, Uxx ji dac i numai dac ( ) 1, Uxx ji . teoria grafurilor se acord un interes deose(it unor

su(mulimi de v!rfuri sau muchii cu proprieti speciale, ce #igsesc aplicaie la soluionarea unui ir de pro(leme practice.Printre aceste su(mulimi se afl mulimile intern sta(ile, e*ternsta(ile, nucleul grafului, cupla5ul .a.

6 su(mulime de v!rfuri X' a unui graf ( )UXG 3=se numete interin !ta&ildac orice dou v!rfuri 'x , nusunt adiacente #n G . /ulimea intern sta(il ' se numete

ma*imal, dac #n G nu e*ist o alt mulime intern sta(il Aastfel #nc!t A' , i respectiv mulimea intern sta(il ' senumete ma*im dac pentru orice mulime intern sta(il Adin G are loc inegalitatea A' . 4ardinalul mulimiima*ime intern sta(ile se numete numr de !ta&ilitate internagrafului G i se noteaz prin ( )Go .

6 su(mulime de v!rfuri X) a unui graf ( )UXG 3=

se numete e*tern sta(il dac pentru orice AXx ) e*ist unv!rf ) adiacent cu x . /ulimea e*tern sta(il ) senumete minim dac #n graful G nu e*ist o alt mulimee*tern sta(il $ astfel #nc!t )$ , i respectiv mulimeae*tern sta(il ) se numete minim dac pentru orice mulimee*tern sta(il $ din G are loc inegalitatea $) .

4ardinalul mulimii minime e*tern sta(ile se numetenumr de


6/31

!ta&ilitate externa grafului G i se noteaz prin ( )Go ./ulimea de v!rfuri care este #n acelai timp intern

sta(il i e*tern sta(il se numete nucleu.6 su(mulime de muchii U# a unui graf ( )UXG 3=

se numete cu"laj dac orice dou muchii #uu ji , nu suntadiacente #n G . 4upla5ul # se numete ma*imal dac #n Gnu e*ist un alt cupla5 *astfel #nc!t *# , i respectivcupla5ul # se numete ma*im, dac pentru orice cupla5 *dinG are loc inegalitatea *# .

Graful ( )++ UX+ 3= se numete !u&graf al grafului( )

GGUXG 3= dac G+ XX , G+ UU . n cazul c!ndG+ XX = graful

+se numete!u&graf "arialal grafului G .

"ac ( ) G+++ UXXU = atunci + se numete !u&graf,generatde su(mulimea de v!rfuri G+ XX . 4u alte cuvinte,dac + este un su(graf al grafului G , generat de osu(mulime de v!rfuri G+ XX atunci dou v!rfuri suntadiacente #n + dac i numai dac ele sunt adiacente i #n G .

7ie acum ( )UXG ,= un graf simplu, iar kun numr

natural oarecare. 7uncia { }kXf ,...,1,& se numete k -colorarea v!rfurilor grafului G . 4olorarea se numete corect,dac ( ) ( )fxf pentru orice dou v!rfuri adiacente Xx , .e spune c graful G este k0 colora(il, dac e*ist o k 0colorare corect a v!rfurilor sale. 2umrul minim kpentru caregraful G este k0 colora(il se numete numr cromatic alacestui graf i se noteaz prin ( )G . "ac ( )G 8 katunci Gse numete kcromatic.

'* Lan+uri i cicluri6 consecutivitate de v!rfuri ( )1 ,,...,, += kk xxxx se

numete mar,rut #n graful ( )UXG ,= dac ( ) Uxx ii +,pentru ki ,= . e consider, c o muchie =ju l" xx , dinG aparine marrutului dac i numai dac "x i lx sunt

v!rfuri vecine #n consecutivitatea , adic { }k" ,...,1, i


7/31

+= "l . '!rfurile , +kxx se numesc extremiti alemarrutului, iar numrul k- lungimea lui. "ac += kxxatunci e numete mar,rut nchi!.

Un marrut, ce conine fiecare muchie a grafului cel multo singur dat se numete lan. 9anul, toate v!rfurile cruia suntdistincte dou c!te dou se numete lan elementar.

Un marrut #nchis, ce conine fiecare muchie a grafuluicel mult o singur dat se numete ciclu. 4iclul, toate v!rfurilecruia, cu e*cepia celor e*tremale, sunt distincte dou c!te douse numete ciclu elementar. 2u orice graf conine ciclurielementare. Graful ce nu conine cicluri elementare se numetear&ore.

ntr0un graf ( )UXG 3= , su(graful parial, ce nu coninecicluri elementare se numete ar&ore "arial.9anul -ciclul, ce conine fiecare muchie a grafului e*act

o singur dat se numete lan ciclu/ eulerian.9anul -ciclul ce conine fiecare v!rf al grafului e*act o

singur dat se numete lan ciclu/ hamiltonian.Graful #n care oricare dou v!rfuri sunt unite printr0un

lan elementar se numetegraf conex. u(graful ma*imal cone*

al grafului G , adic su(graful cone* ce nu se conine #ntr0un altsu(graf cone* mai mare, se numete com"onent conex. Prinurmare, dac graful G nu este cone*, atunci el conine cel puindou componente cone*e.

2otm prin ( )xd , lungimea minim a lanurilorelementare, ce unesc v!rfurile x, . 2umrul ( )xd , e*primdi!tana dintre x i . n cazul c!nd #ntre dou v!rfuri

GXx , nu e*ist nici un lan, se consider ( ) =xd , ."istana v!rfurile unui graf cone* ( )UXG 3= definit

astfel satisface a*iomele metricii, adic pentru orice trei v!rfuriGXzx ,, au loc urmtoarele relaii&

( ) +, xd i ( ) +, =xd dac i numai dac x=1 ( ) ( )xdxd ,, =: ( ) ( ) ( )zxdzdxd ,,, + .


8/31

4u a5utorul distanei se definete puterea de gradulk a grafului. e numete"utere de gradul ka unui graf G

graful kG , ce conine aceeai mulime de v!rfuri ca i G i #ncare dou v!rfuri x, sunt adiacente dac i numai dac #n Gare loc inegalitatea ( ) kxd , .

Pentru un v!rf oarecare GXx al unui graf G numrul( ) ( )xdxe

X,ma*

=

se numete excentricitatea acestui v!rf. 4ea mai mare i cea maimic dintre e*centricitile v!rfurilor unui graf G se numescrespectiv diametru - ( )Gd i raz - ( )Gr a grafului. Prinurmare

( ) ( ) ( )xdxeGdXXxXx

,ma*ma*ma* ==

( ) ( ) ( )xdxeGrXXxXx

,ma*minmin

== .

Evident ( ) ( )GdGr i e*ist grafuri G pentru care areloc egalitatea ( ) ( )GdGr = . "e e*emplu, #n cazul c!nd G esteun ciclu elementar de lungime par egalitatea indicat serespect. '!rful, e*centricitatea cruia coincide cu raza grafuluise numete vrf central. /ulimea tuturor v!rfurilor centrale senumete centrul grafului.

u(mulimea minim de v!rfuri GXA , adicsu(mulimea cu un numr minim de v!rfuri, se numete mulimede articulaie a grafului G , dac la eliminarea ei din Go(inem un graf nou, ce conine cu o component cone* maimult dec!t G -deci la eliminarea din G a oricrei su(mulimi

GX) , A) < , o(inem un graf nou, #n care numrul

componentelor cone*e nu este mai mare dec!t #n G . n cazulc!nd mulimea de articulaie este format dintr0un singur v!rf,acest v!rf se numete "unct de articulaie. /uchia, ce unetedou puncte de articulaie se numete i!tm. "ac muchia ju

este istm #n graful G , atunci la eliminarea ei o(inem un grafnou cu mai multe componente cone*e dec!t G . u(grafulma*imal, ce nu conine puncte de articulaie se numete &loc.


9/31

a ( c

7igura

* Re-re.entri ale grafurilorn afar de reprezentarea alge(ric ce const #n

descrierea nemi5locit a mulimilor de v!rfuri i de muchii ungraf mai poate fi reprezentat geometric, prin matricea deadiacen, matricea de inciden, . a.

n reprezentarea geometric v!rfurile grafului sereprezint prin puncte sau cercuri etichetate, iar orice muchie sereprezint printr0o linie continu, ce unete punctelecorespunztoare e*tremitilor muchiei respective. n cazulgrafurilor orientate liniile sunt #nzestrate cu o sgeat, cecorespunde orientrii arcului. "e e*emplu, fie 1,GG dougrafuri reprezentate alge(ric&

( ) { }( ) ( ) ( )( ){ }

:1;1:1


10/31

Graful ( )UXG 3= se numete "lanar dac admite oreprezentare geometric #n plan, #n care orice dou muchii nu aupuncte comune interioare. nsi reprezentarea geometric agarfului planar, ce posed proprietatea indicat se numetegraf-"lan. e mai spune c graful0plan este o reprezentare

corect #n plan a grafului planar. Graful din figura a este ungraf planar, iar una dintre reprezentrile corecte ale sale dinplan, adic graful0plan respectiv, este dat #n figura c. 9asuprimarea din plan a muchiilor i v!rfurilor unui graf0plan

( )UXG 3= #ntreg planul se #mparte #n componente cone*e,numite fee ale lui G . 4omponentele cone*e mrginite senumesc fee interioare, iar componena cone* nemrginit 0

fa exterioar. 6rice graf0plan conine o fa e*terioar.7rontiera oricrei fee este un marrut #nchis. Graful0plan dinfigura 1 conine >=n v!rfuri, 1=m muchii i ;=f fee.7eele :1 ,, fff sunt fee interioare, iar faa ;f este e*terioar.7rontiera feei f este marrutul #nchis - +:+1 ,,,,, xxxxxx ."ac un graf este planar, atunci #n orice reprezentare corect asa #n plan numrul de fee rm!ne constant. =elaia dintrenumrul de v!rfuri 0 n , muchii 0 m i fee 0 f ale unui grafplanar a fost sta(ilit de 9eonard Euler&

1=+ fmn ,-care se numete astzi formula lui Euler.

6 matrice (inar ijaA = de dimensiunea nn senumete matrice de adiacen a grafului G cu mulimea dev!rfuri { }nG xxxX ,...,, 1= , dac&

=

contrarcaz#n,+

dac, jiij

xxa

/atricea de adiacen a grafului este o matrice simetriccu elementele de pe diagonala principal egale cu zero. 9iniile icoloanele acestei matrici corespund v!rfurilor nxxx ,...,, 1 ale

grafului. 2umrul de uniti dintr0o linie -coloan este egal cu


11/31

gradul v!rfului corespunztor. Pentru graful reprezentat #nfigura a matricea de adiacen este &

=

+++++

++++

+++

++

+++

n . 4u(ul n 0 dimensional conine n1v!rfuri i 1 nn muchii.

"ac x este un v!rf al grafului ( )UXG 3= , atunci prinxG se noteaz graful ce se o(ine din G ca rezultat al

eliminrii v!rfului x -#mpreun cu muchiile incidente lui."ac x i sunt dou v!rfuri din G neadiacente, atunci prin

uG + , unde ( )xu ,= , se noteaz graful ce se o(ine din G laadugarea muchiei noi ( )x, . n figura ;( i ;c suntreprezentate respectiv grafurile


14/31

E* A-lica+ii ale teoriei grafurilor@eoria grafurilor este una dintre disciplinele matematice,

care i0a gsit o aplicaie larg la soluionarea pro(lemelorpractice din diferite domenii& fizic, chimie, economie etc. 'ommeniona c!teva pro(leme ce se reduc #n mod firesc la pro(leme

din teoria grafurilor. 1 localiti tre(uie unite #ntr0o reea informaional

astfel #nc!t informaia transmis dintr0o localitate A s poat firecepionat #n orice alt localitate printr0un canal de legturdirect sau prin intermediul altor centre -localiti, cu condiia calungimea total a acestei reele s fie minim. e tie c #ntreoricare dou localiti din punct de vedere fizic este posi(il,trasarea unui canal de legtur informaional. n aceast situaielocalitile pot fi considerate drept v!rfuri ale unui graf complet

n# #n care fiecare muchie are o pondere egal cu lungimeacanalului de legtur direct dintre centrele respective. $tuncireeaua informaional cutat va fi un ar(ore parial al grafului

n# de lungime minim. n prezent se cunosc doi algoritmieficieni de construire a ar(orilor pariali de lungime minim aunui graf& algoritmul lui ?rusAal, aprut #n anul >


15/31

) fr pericolul de a fi confundate corespunde mulimiima*ime intern sta(ile a grafului construit.

"e regul transmiterea informaiei #ntre dou centre seface #n form de te*te, formate din cuvinte. "ac presupunem ctoate cuvintele au aceeai lungime k, atunci cunoaterea

su(mulimii ma*ime de semnale, care la transmiterea princanalul informaional nu vor fi confundate, permite formarea cel

puin a ( )[ ]kG+ cuvinte diferite, recepionate corect. - ( )Goeste numrul de sta(ilitate intern a grafului G .

: 7ie dat o reea informaional format din centre depstrare i prelucrare a informaiei. Unele dintre aceste centresunt unite prin canale de transmitere a informaiei. @ransmiterea

informaiei #ntre dou centre poate avea loc nemi5locit princanalul dintre ele -dac acesta din urm e*ist sau prinintermediul altor canale i centre. =eeaua se considerfunciona(il, dac transmiterea informaiei are loc #ntre oricedou centre. 7ia(ilitatea reelei funcionale este determinat denumrul minim de centre, distrugerea crora conduce lao(inerea unei reele noi, ce nu mai este funciona(il.

7ia(ilitatea unei astfel de reele informaionale estedeterminat de numrul de cone*itate ( )GH al grafului G ,v!rfurile cruia corespund centrelor informaionale i oricaredou v!rfuri sunt adiacente dac i numai dac centrelerespective sunt unite nemi5locit printr0un canal.

; Pentru realizarea unui proiect este necesar de efectuatn lucrri, determinate de mulimea { }nlll( ,...,, 1= utiliz!nd#n acest scop m dispozitive determinate de mulimea

{ }mddd2 ,...,, 1= . e consider c o lucrare il poate firealizat prin utilizarea unor dispozitive #ntr0un volum de timpegal pentru toate lucrrile din mulimea ( , iar unul i acelaidispozitiv nu poate fi utilizat concomitent pentru efectuarea amai multor lucrri. e cere de gsit o astfel de repartizare adispozitivelor pentru #ndeplinirea lucrrilor, care ar minimizatimpul sumar de realizare a proiectului.


16/31

Pentru soluionarea acestei pro(leme construim un grafG , v!rfurile cruia corespund lucrrilor il - ni ,= ,consider!nd dou v!rfuri ji ll , adiacente, dac pentru efectuarealucrrilor respective este necesar de folosit cel puin undispozitiv comun. 9a o colorare corect a v!rfurilor grafuluiconstruit lucrrile ce corespund v!rfurilor colorate la fel pot fi#ndeplinite #n acelai timp. @impul minim necesar pentrurealizarea proiectului #n #ntregime este determinat de numrulminim de culori #n care pot fi colorate v!rfurile grafului.

0RO'LEME 0RO0USE

%* 4are dintre urmtoarele afirmaii sunt adevrate icare sunt false&

a 6rice marrut #nchis conine un ciclu elementar.( Un marrut #nchis de lungime impar conine un

ciclu elementar.

c =euniunea a dou lanuri elementare diferite, ceunesc dou v!rfuri ale unui graf conine un cicluelementar.

#* "e construit un graf cu n1 v!rfuri ( ):n , #n carevalena oricrui v!rf este trei i nu conine cicluri elementare delungimea trei -triunghiuri.

1* "e demonstrat, c dac un graf G nu este cone*,atunci graful complementar este cone*.


17/31

2*4are este numrul ma*im de muchii #ntr0un graf cu nv!rfuri, ce nu conine cicluri elementare de lungime parD

3*4are este numrul ma*im de muchii #ntr0un graf cu nv!rfuri, ce nu conine cicluri elementareD

4*4are dintre urmtoarele afirmaii este adevrat i care

este fals&a dac G , 1G sunt dou grafuri regulate, atunci sunt

regulate i grafurile 1 GG + , 1 GG 3

( "ac G , 1G sunt dou grafuri (ipartite, atunci sunt

(ipartite i grafurile 1 GG + , 1 GG .5*"e sta(ilit numrul minim de v!rfuri #ntr0un graf :0

regulat -graf cu(ic, ce conine un istm.6* 4are dintre urmtoarele afirmaii sunt adevrate i

care sunt false&a orice ar(ore este un graf (ipartit3( orice ar(ore este un graf (ipartit complet3c un graf cone* ( )UXG 3= conine un singur ciclu

dac i numai dac UX = 3

d orice ar(ore cu n v!rfuri conine n istmuri.7*"e demonstrat, c centrul unui graf cone* G aparine

unui (loc din G .%$*Pentru un graf cone* ( )UXG 3= notm prin ( )GH

numrul minim de v!rfuri, la eliminarea crora o(inem un grafnecone* sau un graf trivial, prin ( )G numrul minim demuchii, la eliminarea crora o(inem un graf necone* i prin

( )G valena minim a v!rfurilor grafului G . "e construit ungraf G pentru care ( ) :=G , ( ) ;=G , ( )


18/31

%#*ta(ilii condiiile, #n care graful muchiilor unui graf( )UXG 3= este regulat.

%1*4onstruii un graf ( )UXG 3= , ;X , pentru caregraful muchiilor ( )G( nu este eulerian, iar graful ( )G(1 este

eulerian.%2*"e construit un graf G pentru care graful muchiilor

( )G( este hamiltonian.%3*"e construit un graf G pentru care graful muchilor

( )G( este eulerian.%4*"e construit un graf G #n care orice mulime intern

sta(il se conine #n mulimea ma*im intern sta(il.

%5*"e demonstrat relaiilea8 ( ) ( ) ( )11 GGGG +=+ 3,8 ( ) ( ) ( ){ }11 ,ma* GGGG .%6* 7ie G un graf0plan, #n care toate v!rfurile aparin

frontierei unei fee. "e demonstrat c acest graf poate fi coloratcorect cu a5utorul cel mult a trei culori.

%7*Pentru grafurile reprezentate geometric #n figura

probleme teoria grafurilor.doc

Documents