Aresta (teoria de grafs)

En teoria de grafs, una aresta correspon a una relació entre dos vèrtexs d'un graf. Per caracteritzar un graf G són suficients únicament el conjunt de totes les seves arestes, comunament denotat amb la lletra E (del terme en anglès edge), juntament amb el conjunt dels seus vèrtexs, denotat per V. Així, un graf es pot denotar com G(V,E), o bé G=(V,E).

Alguns exemples d'arestes, orientades i no orientades: a) Aresta no orientada; b) Aresta orientada; c) Cicle orientat; d) Multiarestes, una d'orientada i l'altra no; e) Multiarestes no orientades; f) Multiarestes orientades; g) Bucle orientat; h) Bucle no orientat; i) Multibucle orientat; j) Multibucle no orientat

Un vèrtex és incident a una aresta si hi pertany, o en altres paraules, si està connectat a un altre vèrtex (o a ell mateix) a través de l'aresta.

Representació

Gràficament les arestes es representen, en el cas dels grafs no dirigits, com una línia que uneix els dos vèrtexs. Si el graf és dirigit, llavors l'aresta es representa com una fletxa, que parteix del vèrtex origen i apunta al vèrtex destí.

Algebraicament, donats dos vèrtexs a i b pertanyents al conjunt V, una aresta es defineix, per a un graf no dirigit, com el conjunt e = {a,b} (o {b,a}), mentre que per a un graf dirigit, com la parella ordenada e = (a,b) (on (b,a) representaria una aresta diferent, amb el vèrtex origen i destí intercanviats). En ambdós casos, e∈E.

D'altra banda, també és comú que les arestes portin associades una etiqueta (un nombre, una lletra o un valor qualsevol) que indica una informació associada a dos vèrtexs, de vegades un cost o indicació del treball necessari per recórrer el camí d'un vèrtex l'altre.

No és obligatori que tots els vèrtexs estiguin units amb un altre per una aresta. Els vèrtexs que no n'estan s'anomenen vèrtexs aïllats. Tampoc cal que els dos vèrtexs units per una aresta siguin diferents.

Relació d'adjacència

Les arestes d'un graf o digraf G=(V, E) indueixen una relació anomenada relació d'adjacència. Per tant, un vèrtex v és adjacent a un vèrtex w si i només si v-w és una aresta que pertany al conjunt E.

Bibliografia

• Diestel, Reinhard. Graph Theory (en anglès). Nova York: Springer-Verlag, 1997. 

Viccionari