Multigrafo

De Wikipedia, la enciclopedia libre
Ir a la navegación Ir a la búsqueda
Un multigrafo con aristas múltiples (en rojo) y tres bucles (en azul). No todos los autores permiten multigrafos con bucles.

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]

Definición formal[editar]

Formalmente, un multigrafo es un par ordenado donde:

Un multidigrafo se define de manera análoga, pero con considerando aristas dirigidas. Si admite aristas dirigidas y no dirigidas, entonces se habla de multidigrafo mixto.

Etiquetado[editar]

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 donde:

  • V es un conjunto de nodos y A un multiconjunto de arcos.
  • y son alfabetos finitos para las etiquetas de nodos y arcos.
  • y son dos funciones que indican la fuente y objetivo de los nodos de un arco.
  • y son dos funciones que asocian cada nodo y arco con una etiqueta.

Aplicaciones[editar]

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[editar]

  1. a b c 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. 

Referencias[editar]

  • 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.