Multigraf

Un multigraf amb arestes múltiples (en vermell) i diversos bucles (en blau).

En matemàtiques, i més concretament en teoria de grafs, un multigraf és un graf que pot tenir arestes múltiples[1] (de vegades anomenades també arestes paral·leles[2][3]); és a dir, arestes que tenen els mateixos vèrtexs incidents. Així, dos vèrtexs poden estar connectats per més d'una aresta. Per a alguns autors, un multigraf no permet l'existència de bucles, i reserven el terme pseudograf per a multigrafs amb bucles. Altres autors permeten que els multigrafs admetin bucles,[1] i consideren com a sinònims els termes "pseudograf" i "multigraf".

Existeixen dues nocions diferents d'arestes múltiples:

• Arestes sense identitat pròpia: la identitat d'una aresta queda definida únicament pels dos vèrtexs que connecta. En aquest cas, el terme "arestes múltiples" significa que la mateixa aresta pot aparèixer diverses vegades entre aquests dos vèrtexs.
• Arestes amb identitat pròpia: les arestes són entitats primitives, igual que els vèrtexs. Quan hi ha arestes múltiples que connecten dos vèrtexs, es tracta d'arestes diferents.

Un multigraf és diferent d'un hipergraf, que és un graf en el qual una aresta pot connectar qualsevol nombre de vèrtexs, no només dos.

Multigraf no dirigit (arestes sense identitat pròpia)

Un multigraf G és un parell ordenat G:=(V, E) amb

• V un conjunt de vèrtexs o nodes,
• E un multiconjunt de parells no ordenats d'arestes.

Multigraf no dirigit (arestes amb identitat pròpia)

Un multigraf G és un triplet ordenat G:=(V, E, r) amb

• V un conjunt de vèrtexs o nodes,
• E un conjunt d'arestes,
• r : E → {{x,y} : x, y ∈ V}, una aplicació que assigna a cada aresta un parell no ordenat de vèrtexs extrems.

Alguns autirs permeten que els multigrafs tinguin bucles, és a dir, una aresta que connecta un vèrtex amb ell mateix,[1][4] mentre que altres autors els anomenen pseudografs, reservant el terme "multigraf" al cas sense bucles.[5][6]

Multigraf dirigit (arestes sense identitat pròpia)

Un multidigraf és un graf dirigit on es permeten arestes múltiples, és a dir, arcs amb els mateixos vèrtexs inicial i final. Un multidigraf G és un parell ordenat G:=(V,A) amb

• V un conjunt de vèrtexs o nodes,
• A un multiconjunt de parells ordenats de vèrtexs, anomenats '"arestes dirigides, arcs o fletxes.

Un multigraf mixt G:=(V,E, A) es pot definir de la mateixa manera que un graf mixt.

Multigraf dirigit (arestes amb identitat pròpia)

Un multidigraf (o buirac,[7] (anglès) quiver) G és una 4-pla G:=(V, A, s, t) amb

• V un conjunt de vèrtexs o nodes,
• A un conjunt d'arestes o nodes,
• ${\displaystyle s:A\rightarrow V}$, que assigna a cada aresta el seu vèrtex inicial,
• ${\displaystyle t:A\rightarrow V}$, que assigna a cada aresta el seu vèrtex final.

Aquesta noció es pot emprar per modelar les diferents connexions de vol oferides per una aerolínia. En aquest cas, el multigraf seria un graf dirigit amb parells d'arestes dirigides paral·leles que cinnecten ciutats, il·lustrant que és possible viatjar cap a i des d'aquests llocs.

En teoria de categories, es pot definir una petita categoria com un multigraf (on les arestes tenen identitat pròpia), equipat amb una llei de composició associativa i un bucle diferenciat a cada vèrtex,que representa la identitat per l'esquerra i per la dreta de la composició. Per aquest motiu, el terme graf s'acostuma a assumir que vol dir "multidigraf", i del multidigraf subjacent d'una categoria se'n diu el seu graf subjacent.

Etiquetatge

Els multigrafs i els multidigrafs també suporten la noció d'etiquetatge de grafs, d'una manera semblant. Tanmateix, no existeix una terminologia estàndard.

Les definicions de multigrafs etiquetats i nultidigrafs etiquetats són similars, i aquí en donem només les aplicables per a multidigrafs.

Definició 1: Un multidigraf etiquetat és un graf etiquetat amb arcs etiquetats.

Formalment: Un multidigraf etiquetat G és un multigraf amb vèrtexs i arestes etiquetats. Formalment, és una 8-pla ${\displaystyle G=(\Sigma _{V},\Sigma _{A},V,A,s,t,\ell _{V},\ell _{A})}$ on

• V és un conjunt de vèrtexs i A és un conjunt d'arcs,
• ${\displaystyle \Sigma _{V}}$ i ${\displaystyle \Sigma _{A}}$ són alfabets finits de les etiquetes disponibles per als vèrtexs i als arcs,
• ${\displaystyle s\colon A\rightarrow \ V}$ i ${\displaystyle t\colon A\rightarrow \ V}$ són dues aplicacions que indiquen els vèrtexs inicial i final d'un arc,
• ${\displaystyle \ell _{V}\colon V\rightarrow \Sigma _{V}}$ i ${\displaystyle \ell _{A}\colon A\rightarrow \Sigma _{A}}$ són dues aplicacions que descriuen l'etiquetatge dels vèrtexs i els arcs.

Definició 2: Un multidigraf és un graf etiquetat amb múltiples arcs etiquetats, és a dir, arcs amb els mateixos vèrtexs extrems i la mateixa etiqueta (notem que aquesta noció de graf etiquetat és diferent a la noció donada en l'article Graf etiquetat).

Referències

1. Bollobás, 2002, p. 7.
2. Balakrishnan, 1997, p. 1.
3. Chartrand i Zhang, 2012, p. 26.
4. Diestel, 2010, p. 28.
5. Wilson, 2002, p. 6.
6. Chartrand i Zhang, 2012, p. 26-27.
7. Brustenga i Bort, Miquel. Àlgebres associades a un buirac. ISBN 9788469093290. 

Bibliografia

• Balakrishnan, V. K.. Graph Theory. McGraw-Hill, 1997. ISBN 0-07-005489-4. 
• Bollobás, Béla. Modern Graph Theory. 184. Springer, 2002 (Graduate Texts in Mathematics). ISBN 0-387-98488-7. 
• Chartrand, Gary; Zhang, Ping. A First Course in Graph Theory. Dover, 2012. ISBN 978-0-486-48368-9. 
• Diestel, Reinhard. Graph Theory. 173. 4a edició. Springer, 2010 (Graduate Texts in Mathematics). ISBN 978-3-642-14278-9. 
• Gross, Jonathan L.; Yellen, Jay. Graph Theory and Its Applications. CRC Press, 1998. ISBN 0-8493-3982-0. 
• Gross, Jonathan L.; Yellen, Jay. Handbook of Graph Theory. CRC, 2003. ISBN 1-58488-090-2. 
• Harary, Frank. Graph Theory. Addison Wesley, 1995. ISBN 0-201-41033-8. 
• Janson, Svante; Knuth, Donald E.; Luczak, Tomasz; Pittel, Boris «The birth of the giant component». Random Structures and Algorithms, 4, 3, 1993, pàg. 231–358. DOI: 10.1002/rsa.3240040303. ISSN: 1042-9832.
• Wilson, Robert A. Graphs, Colourings and the Four-Colour Theorem. Oxford Science Publ., 2002. ISBN 0-19-851062-4. 
• Zwillinger, Daniel. CRC Standard Mathematical Tables and Formulae. 31a edició. Chapman & Hall/CRC, 2002. ISBN 1-58488-291-3. 

Vegeu també

• Glossari de teoria de grafs
• Teoria de grafs

Enllaços externs

• Black, Paul E. «Multigraph». Dictionary of Algorithms and Data Structures. NIST. Arxivat de l'original el 2016-03-29. [Consulta: 27 juny 2016].