Multigrafo

En teoría de grafos, un multigrafo o grafo multivariado es una generalización de un grafo que permite aristas múltiples, o equivalentemente, más de un conjunto de aristas. De esta forma, dos nodos pueden estar conectados por más de una arista.^[1]​ Algunos autores permiten que los multigrafos tengan bucles, es decir, que una arista conecte a un nodo consigo mismo.^[2]​^[3]​ Un pseudografo se puede definir como un sinónimo de multigrafo, aunque en ocasiones también se utiliza para distinguir a los multigrafos en general, de aquellos que permiten bucles.^[4]​ Si se consideran aristas dirigidas, al multigrafo también se le conoce como multigrafo dirigido o multidigrafo. También se puede hablar de grafo complejo en oposición a un grafo simple (esto es, un grafo sin bucles ni aristas múltiples), como un grafo que posee bucles y/o al menos un par de vértices con más de una arista.^[1]​

Un multigrafo con aristas múltiples (en rojo) y tres bucles (en azul). No todos los autores permiten multigrafos con bucles.

Definición formal

Formalmente, un multigrafo ${\displaystyle G}$  es un par ordenado ${\displaystyle G=(V,E)}$  donde:

• ${\displaystyle V}$  es un conjunto de vértices o nodos;
• ${\displaystyle E}$  es un multiconjunto (finito) de aristas o líneas, o alternativamente, una familia de conjuntos de aristas.^[1]​

Un multidigrafo se define de manera análoga, pero con ${\displaystyle E}$  considerando aristas dirigidas. Si ${\displaystyle E}$  admite aristas dirigidas y no dirigidas, entonces se habla de multidigrafo mixto.

Etiquetado

Los multigrafos y multidigrafos pueden etiquetarse de manera análoga a un grafo tradicional. Sin embargo, solo existe consenso con respecto a la terminología para los multidigrafos.

Un multidigrafo etiquetado G es un grafo etiquetado con arcos etiquetados. Formalmente, es una 8-tupla ${\displaystyle G=(\Sigma _{V},\Sigma _{A},V,A,s,t,\ell _{V},\ell _{A})}$  donde:

• V es un conjunto de nodos y A un multiconjunto de arcos.
• ${\displaystyle \Sigma _{V}}$  y ${\displaystyle \Sigma _{A}}$  son alfabetos finitos para las etiquetas de nodos y arcos.
• ${\displaystyle s\colon A\rightarrow \ V}$  y ${\displaystyle t\colon A\rightarrow \ V}$  son dos funciones que indican la fuente y objetivo de los nodos de un arco.
• ${\displaystyle \ell _{V}\colon V\rightarrow \Sigma _{V}}$  y ${\displaystyle \ell _{A}\colon A\rightarrow \Sigma _{A}}$  son dos funciones que asocian cada nodo y arco con una etiqueta.

Aplicaciones

Los multigrafos podrían usarse, por ejemplo, para modelar las posibles conexiones de vuelo ofrecidas por una aerolínea. Para este caso tendríamos un grafo dirigido, donde cada nodo es una localidad y donde pares de aristas paralelas conectan estas localidades, según un vuelo es hacia o desde una localidad a la otra.

Notas

1. Wasserman y Faust, 2013, «Grafos y matrices» (por Dawn Iacobucci), pp. 121-188.
2. Bollobas, 2002, p. 7.
3. Diestel, 2000, p. 25.
4. Pogliani, L. (2000). «From molecular connectivity indices to semiempirical connectivity terms: Recent trends in graph theoretical descriptors». Chemical Reviews 100 (10). pp. 3827-3858. doi:10.1021/cr0004456.  Falta la |url= (ayuda)

Referencias

• Bollobas, B. (2002). Modern Graph Theory (I edición). Springer. ISBN 0-387-98488-7. 
• Diestel, R. (2000). Graph Theory (II edición). Springer. ISBN 0-387-98976-5. 
• Wasserman, Stanley; Faust, Katherine (2013) [1994]. Análisis de redes sociales: Métodos y aplicaciones. Madrid: Centro de Investigaciones Sociológicas. ISBN 978-84-7476-631-8. OCLC 871814053. 

•   Datos: Q2642629
•   Multimedia: Multigraphs