Glossari de teoria de grafs

De Viquipèdia
Dreceres ràpides: navegació, cerca
Graf simple no dirigit, amb 6 vèrtexs i 7 arestes.

A continuació es detallen els principals conceptes de la teoria de grafs. Per a les definicions formals o més detallades, podeu adreçar-vos a l'article principal corresponent o bé a l'article Termes de teoria de grafs.

Tots els exemples estan basats en la imatge de la dreta.


Índex A B C D E F G H I J K L M N O P Q R S T U V W X Y Z


A[modifica | modifica el codi]

Adjacència[modifica | modifica el codi]

En un graf, els vèrtexs són adjacents si estan units mitjançant una aresta.

Vegeu Veïnatge .

Arbre[modifica | modifica el codi]

Un arbre és un graf connex simple acíclic. Algunes vegades, un vèrtex de l'arbre és distingit cridant arrel . Els arbres s'usen freqüentment com estructures de dades en ciències de la computació (vegeu arbre).

Arc[modifica | modifica el codi]

Vegeu Aresta .

Aresta[modifica | modifica el codi]

Una aresta o arc és una relació matemàtica que connecta dos vèrtexs. Una aresta dirigida és una aresta d'un digraf i té una adreça associada amb si, és a dir, posseeix un vèrtex inicial i un vèrtex final. Una aresta no dirigida és una on no es distingeix un vèrtex inicial ni un final.

B[modifica | modifica el codi]

Bosc[modifica | modifica el codi]

Un bosc és un conjunt de arbres, o de forma equivalent, un bosc és un graf acíclic.

Bucle[modifica | modifica el codi]

Un bucle o loop en un graf o digrafs una aresta que connecta al mateix vèrtex amb si mateix.

Cerca en profunditat[modifica | modifica el codi]

La Cerca en profunditat o DFS (Depth First Search) és un algorisme que permet recórrer tots els vèrtexs d'un graf de manera ordenada, però no uniforme.

C[modifica | modifica el codi]

Camí[modifica | modifica el codi]

Un camí és una successió de vèrtexs tal que de cada un dels seus vèrtexs hi ha una aresta cap al vèrtex successor. Un camí simple és aquell en què totes les arestes del camí són diferents.
Dos camins són aliens o independents si no tenen cap vèrtex en comú excepte el primer i l'últim.
La longitud d'un camí és el nombre d'arestes que fa servir aquest camí, comptant arestes recorregudes diverses vegades el mateix nombre de vegades que les recorrem. En l'exemple, (1, 2, 5, 1, 2, 3) és un camí amb longitud 5, i (5, 2, 1) és un camí simple de longitud 2 ..

Camí eulerià[modifica | modifica el codi]

Un camí eulerià en un graf és un camí que fa servir cada aresta una i només una vegada. Si existeix tal camí diem que el graf és travessar . Aquesta definició és dual a la d'camí hamiltonià.

Camí hamiltonià[modifica | modifica el codi]

Hi ha un concepte dual de camí/cicle eulerià. Un camí hamiltonià en un graf és un camí que "visita" cada vèrtex una i només una vegada, i un cicle hamiltonià és un cicle que visita cada vèrtex una i només una vegada.
L'exemple de la imatge té un camí hamiltonià.

Cicle[modifica | modifica el codi]

Un Cicle (o circuit) és un camí que comença i acaba en el mateix vèrtex. Els cicles de longitud 1 són els bucles. En l'exemple, (1, 2, 3, 4, 5, 2, 1) és un cicle de longitud 6.
Un cicle simple és un cicle que té com a longitud almenys 3 i en què el vèrtex del començament només apareix una vegada més i com a vèrtex final, i els altres només apareixen una vegada. En el graf de dalt (1, 5, 2, 1) és un cicle simple.

Cicle eulerià[modifica | modifica el codi]

Un cicle eulerià en un graf és un cicle que utilitza cada aresta una i només una vegada.

Cicle hamiltonià[modifica | modifica el codi]

Un cicle hamiltonià en un graf és un cicle que visita cada vèrtex una i només una vegada.

Clique[modifica | modifica el codi]

Un clique en un graf és un conjunt de vèrtexs tal que per a tot parell de vèrtexs, hi ha una aresta que les connecta. En l'exemple, els vèrtexs 1, 2 i 5 formen un clique de mida 3.

Cobertura de vèrtexs[modifica | modifica el codi]

La cobertura de vèrtexs , covering o recobriment de vèrtexs d'un graf és un conjunt de vèrtexs els elements són adjacents a tots els altres vèrtexs del graf.

Coloració de grafs[modifica | modifica el codi]

La coloració de grafs és potser el problema NP-complet més famós de la teoria de grafs, i consisteix a assignar diferents colors o marques als vèrtexs d'un graf, de manera que cap parell de vèrtexs adjacents comparteixin el mateix color o marca.

Component fortament connex[modifica | modifica el codi]

Un component fortament connex és un graf tal que per a cada parell de vèrtexs, hi ha un camí d'un cap a l'altre, i viceversa. Els components fortament connexos d'un graf dirigit són els seus subgrafs màxims fortament connexos. Aquests subgrafs formen una partició del graf.

Conjunt estable[modifica | modifica el codi]

Vegeu Conjunt independent .

Conjunt independent[modifica | modifica el codi]

Un conjunt independent en un graf és un conjunt de vèrtexs tal que cap és adjacent a un altre. En l'exemple, els vèrtexs 1,3, i 6 formen un conjunt tal els 3,5, i 6 formen un altre conjunt independent.

Covering[modifica | modifica el codi]

Vegeu Cobertura de vèrtexs .

D[modifica | modifica el codi]

Depth First Search[modifica | modifica el codi]

Vegeu Cerca en profunditat .

DFS[modifica | modifica el codi]

Vegeu Cerca en profunditat .

Digraf[modifica | modifica el codi]

És un graf les arestes són dirigides, és a dir, cada aresta té un vèrtex inicial i un final.

G[modifica | modifica el codi]

Girth[modifica | modifica el codi]

El girth d'un graf és la longitud del cicle simple més curt en el graf. El "girth" d'un graf acíclic es defineix com infinit.

Grau[modifica | modifica el codi]

El grau o valència d'un vèrtex és el nombre d'arestes que hi incideixen. Per a un graf amb bucles, aquests són comptats per dos. En l'exemple, els vèrtexs 1 i 3 tenen grau 2, els vèrtexs 2, 4 i 5, grau 3, i el vèrtex 6, grau 1.
En un dígraf, podem distingir el grau sortint (el nombre d'arestes que deixen el vèrtex) i el grau entrant (el nombre d'arestes que entren en un vèrtex). El grau d'un vèrtex seria la suma dels dos nombres.

Graf[modifica | modifica el codi]

Un graf és un conjunt de vèrtex o nodes units per arestes o arcs.

Graf acíclic[modifica | modifica el codi]

Un graf es diu acíclic si no conté cap cicle simple.

Graf bipartit[modifica | modifica el codi]

Un graf bipartit és qualsevol graf els vèrtexs poden ser dividits en dos conjunts, tal que no hi hagi arestes entre els vèrtexs del mateix conjunt. Es veu que un graf és bipartit si no hi ha cicles de longitud senar. Vegeu també graf bipartit complet.
Un graf k -partit o graf k -colorable és un graf amb els vèrtexs es pot fer una partició en k subconjunts disjunts tal que no hi hagi arestes entre vèrtexs d'aquest subconjunt. Un graf 2-partit és el mateix que un graf bipartit.
Un graf k -partit es diu semiregular si cada partició té un grau uniforme.

Graf complet[modifica | modifica el codi]

Un graf complet és un graf simple en el qual cada vèrtex és adjacent a qualsevol tot altre vèrtex. El de l'exemple no és complet. El graf complet en n vèrtexs es denota sovint per K n . Té n ( n -1)/2 arestes (corresponent a totes les possibles eleccions de parells de vèrtexs).

Graf connex[modifica | modifica el codi]

Si és possible formar un camí des de qualsevol vèrtex a qualsevol altre en el graf, diem que el graf és connex . Si és possible fer-ho fins i tot després de treure k -1 vèrtexs, diem que el graf és k -connex .
Un graf és k -connex si i només si conté k camins independents entre qualssevol dos vèrtexs. Teorema de Menger El graf exemple és connex (i per tant 1-connex), però no és 2-connex.

Graf dirigit[modifica | modifica el codi]

És un conjunt de vèrtexs V i un conjunt d'arestes E tal que per a cada aresta pertanyent al conjunt d'arestes E s'associa amb dos vèrtexs en forma ordenada.

Vegeu digraf .

Graf nul[modifica | modifica el codi]

El graf nul és el graf els conjunts d'arestes i de vèrtexs són buits.

Graf plànol[modifica | modifica el codi]

Un graf pla és un que pot ser dibuixat en el pla sense que interseccionen qualssevol dues arestes. El de l'exemple ho és, el graf complet en n vèrtexs, per n > 4, no és pla.

Graf ponderat[modifica | modifica el codi]

Un graf ponderat associa un valor o pes a cada aresta al graf. El pes d'un camí en un graf amb pesos és la suma dels pesos de totes les arestes travessades.

Graf regular[modifica | modifica el codi]

Un graf regular és un graf els vèrtexs tenen tots el mateix grau.

Graf simple[modifica | modifica el codi]

Un graf simple és un graf o digraf que no té bucles, i que no és un multigrafo.

Graf universal[modifica | modifica el codi]

Un graf universal en una classe K de grafs és un graf en el qual pot incloure com subgraf tot element de K.

Graf buit[modifica | modifica el codi]

Un graf buit és el graf el conjunt d'arestes és buit.

I[modifica | modifica el codi]

Incidència[modifica | modifica el codi]

Vegeu Veïnatge .

L[modifica | modifica el codi]

Loop[modifica | modifica el codi]

Vegeu Bucle .

M[modifica | modifica el codi]

Matriu d'adjacència[modifica | modifica el codi]

Una matriu d'adjacència és una matriu d nxn que permet representar un graf o digraf finit, on cada valor en la posició (i, j) representa el nombre d'arestes des del vèrtex i -èsim l j -èsim.

N[modifica | modifica el codi]

Node[modifica | modifica el codi]

Vegeu Vèrtex .

P[modifica | modifica el codi]

Pont[modifica | modifica el codi]

Un pont a és una aresta tal que si la traiem ens vam quedar amb un graf amb una component connexa més que l'original.

Punt d'articulació[modifica | modifica el codi]

Un punt d'articulació o punt de tall és un vèrtex tal que si ho llevem ens vam quedar amb un graf amb més components connexes que l'original.

Punt de tall[modifica | modifica el codi]

Vegeu Punt d'articulació .

R[modifica | modifica el codi]

Recobriment de vèrtexs[modifica | modifica el codi]

Vegeu Cobertura de vèrtexs .

S[modifica | modifica el codi]

Subarbre[modifica | modifica el codi]

Un subarbre d'un graf G és un subgraf que és a més un arbre.

Subgraf[modifica | modifica el codi]

Un subgraf d'un graf G és un graf que utilitzen jocs de vèrtexs és un subconjunt del de G , el conjunt d'arestes és un subconjunt del conjunt de les arestes de G , i tal que l'aplicació w és la restricció de l'aplicació de G .

Subgraf d'expansió[modifica | modifica el codi]

Un subgraf d'expansió d'un graf G és un subgraf amb el mateix conjunt de vèrtexs que G . Un arbre expansió és un subgraf expansió que és un arbre. Cada graf té un arbre d'expansió.

T[modifica | modifica el codi]

Teoria espectral[modifica | modifica el codi]

La teoria espectral és la que estudia les relacions entre les propietats de la matriu d'adjacència i les del seu graf.

Torneig[modifica | modifica el codi]

Un torneig és un graf dirigit complet, simple, no generalitzat, no degenerat i sense Digón.

V[modifica | modifica el codi]

València[modifica | modifica el codi]

Vegeu Grau .

Vèrtex[modifica | modifica el codi]

Un vèrtex o node és la unitat fonamental de la qual estan formats els grafs.

Veïnatge[modifica | modifica el codi]

Dos vèrtexs són veïns , adjacents o incidents si hi ha una aresta entre ells. En l'exemple, el vèrtex 1 té dos veïns: el vèrtex 2 i el 5. Per a un graf simple , el nombre de veïns d'un vèrtex és igual al seu grau .