Multigrafo

En matemáticas , y más específicamente en teoría de grafos , un multigrafo es un grafo al que se le permite tener múltiples aristas (también llamadas aristas paralelas ^[1] ), es decir, aristas que tienen los mismos nodos finales . Por lo tanto, dos vértices pueden estar conectados por más de una arista.

Existen dos nociones distintas de aristas múltiples:

Aristas sin identidad propia : La identidad de una arista está definida únicamente por los dos nodos que conecta. En este caso, el término "aristas múltiples" significa que la misma arista puede aparecer varias veces entre estos dos nodos.
Aristas con identidad propia : Las aristas son entidades primitivas, al igual que los nodos. Cuando varias aristas conectan dos nodos, se trata de aristas diferentes.

Un multigrafo es diferente de un hipergrafo , que es un grafo en el que una arista puede conectar cualquier número de nodos, no solo dos.

Para algunos autores, los términos pseudografo y multigrafo son sinónimos. Para otros, un pseudografo es un multigrafo al que se le permite tener bucles .

Multigrafo no dirigido (aristas sin identidad propia)

Un multigrafo G es un par ordenado G := ( V , E ) con

V un conjunto de vértices o nodos ,
E es un multiconjunto de pares de vértices no ordenados, llamados aristas o líneas .

Multigrafo no dirigido (aristas con identidad propia)

Un multigrafo G es un triple ordenado G := ( V , E , r ) con

V un conjunto de vértices o nodos ,
E un conjunto de bordes o líneas ,
r : E → {{ x , y } : x , y ∈ V }, asignando a cada arista un par desordenado de nodos finales.

Algunos autores permiten que los multigrafos tengan bucles , es decir, una arista que conecta un vértice consigo mismo, ^[2] mientras que otros los llaman pseudografos , reservando el término multigrafo para el caso sin bucles. ^[3]

Multigrafo dirigido (aristas sin identidad propia)

Un multidígrafo es un grafo dirigido al que se le permite tener múltiples arcos, es decir, arcos con los mismos nodos de origen y destino. Un multidígrafo G es un par ordenado G := ( V , A ) con

V un conjunto de vértices o nodos ,
Un conjunto múltiple de pares ordenados de vértices llamados aristas dirigidas , arcos o flechas .

Un multigrafo mixto G := ( V , E , A ) puede definirse de la misma manera que un grafo mixto .

Multigrafo dirigido (aristas con identidad propia)

Un multidígrafo o carcaj G es una 4-tupla ordenada G := ( V , A , s , t ) con

V un conjunto de vértices o nodos ,
Un conjunto de bordes o líneas ,
$s:A\rightarrow V$ , asignando a cada arista su nodo fuente,
$t:A\rightarrow V$ , asignando a cada arista su nodo objetivo.

Esta noción podría utilizarse para modelar las posibles conexiones aéreas que ofrece una aerolínea. En este caso, el multigrafo sería un grafo dirigido con pares de aristas paralelas dirigidas que conectan ciudades para mostrar que es posible volar tanto hacia como desde estas ubicaciones.

En teoría de categorías, una categoría pequeña puede definirse como un multidígrafo (cuyas aristas tienen su propia identidad) dotado de una ley de composición asociativa y de un bucle propio diferenciado en cada vértice que sirve como identidad izquierda y derecha para la composición. Por esta razón, en teoría de categorías el término grafo se entiende de manera estándar como "multidígrafo", y el multidígrafo subyacente de una categoría se denomina su dígrafo subyacente .

Etiquetado

Los multigrafos y multidígrafos también admiten la noción de etiquetado de grafos , de manera similar. Sin embargo, no existe una unidad en la terminología en este caso.

Las definiciones de multigrafos etiquetados y multidígrafos etiquetados son similares, y aquí definimos sólo estos últimos.

Definición 1 : Un multidígrafo etiquetado es un gráfico etiquetado con arcos etiquetados .

Formalmente: Un multidígrafo etiquetado G es un multigrafo con vértices y arcos etiquetados . Formalmente es una 8-tupla donde $G=(\Sigma _{V},\Sigma _{A},V,A,s,t,\ell _{V},\ell _{A})$

$V$ es un conjunto de vértices y es un conjunto de arcos. $A$
$\Sigma _{V}$ y son alfabetos finitos de las etiquetas de vértices y arcos disponibles, $\Sigma _{A}$
$s\colon A\rightarrow \ V$ y son dos mapas que indican el vértice de origen y destino de un arco, $t\colon A\rightarrow \ V$
$\ell _{V}\colon V\rightarrow \Sigma _{V}$ y son dos mapas que describen el etiquetado de los vértices y arcos. $\ell _{A}\colon A\rightarrow \Sigma _{A}$

Definición 2 : Un multidígrafo etiquetado es un grafo etiquetado con múltiples arcos etiquetados , es decir, arcos con los mismos vértices finales y la misma etiqueta de arco (tenga en cuenta que esta noción de grafo etiquetado es diferente de la noción dada en el artículo etiquetado de grafos ).

Véase también

Notas

^ Por ejemplo, consulte Balakrishnan 1997, p. 1 o Chartrand y Zhang 2012, p. 26.
^ Por ejemplo, véase Bollobás 2002, p. 7 o Diestel 2010, p. 28.
^ Por ejemplo, véase Wilson 2002, pág. 6 o Chartrand y Zhang 2012, págs. 26-27.

Referencias

Balakrishnan, VK (1997). Teoría de grafos . McGraw-Hill. ISBN 0-07-005489-4.
Bollobás, Béla (2002). Teoría de grafos moderna . Textos de posgrado en matemáticas . Vol. 184. Springer. ISBN 0-387-98488-7.
Chartrand, Gary ; Zhang, Ping (2012). Un primer curso de teoría de grafos . Dover. ISBN 978-0-486-48368-9.
Diestel, Reinhard (2010). Teoría de grafos . Textos de posgrado en matemáticas. Vol. 173 (4.ª ed.). Springer. ISBN 978-3-642-14278-9.
Gross, Jonathan L.; Yellen, Jay (1998). Teoría de grafos y sus aplicaciones . CRC Press. ISBN 0-8493-3982-0.
Gross, Jonathan L.; Yellen, Jay, eds. (2003). Manual de teoría de grafos . CRC. ISBN 1-58488-090-2.
Harary, Frank (1995). Teoría de grafos . Addison Wesley. ISBN 0-201-41033-8.
Janson, Svante ; Knuth, Donald E. ; Luczak, Tomasz; Pittel, Boris (1993). "El nacimiento del componente gigante". Estructuras aleatorias y algoritmos . 4 (3): 231–358. arXiv : math/9310236 . Bibcode :1993math.....10236J. doi :10.1002/rsa.3240040303. ISSN 1042-9832. MR 1220220. S2CID 206454812.
Wilson, Robert A. (2002). Gráficos, coloraciones y el teorema de los cuatro colores. Oxford Science Publ. ISBN 0-19-851062-4.
Zwillinger, Daniel (2002). Tablas y fórmulas matemáticas estándar del CRC (31.ª edición). Chapman & Hall/CRC. ISBN 1-58488-291-3.

Enlaces externos

Este artículo incorpora material de dominio público de Paul E. Black. "Multigraph". Diccionario de algoritmos y estructuras de datos . NIST .