multigrafo

Gráfico con múltiples aristas entre dos vértices

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

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 tanto, dos vértices pueden estar conectados por más de una arista.

Hay dos nociones distintas de aristas múltiples:

• Bordes sin identidad propia : La identidad de un borde está definida únicamente por los dos nodos que conecta. En este caso, el término "múltiples aristas" significa que la misma arista puede aparecer varias veces entre estos dos nodos.
• Aristas con identidad propia : Las aristas son entidades primitivas como los nodos. Cuando múltiples aristas conectan dos nodos, estos son 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 un conjunto múltiple de pares de vértices desordenados, 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 aristas o líneas ,
• r  : E → {{ x , y } : x , y ∈ V }, asignando a cada arista un par desordenado de nodos de punto final.

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 gráfico dirigido al que se le permite tener múltiples arcos, es decir, arcos con los mismos nodos de origen y de 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 ) se puede definir de la misma manera que un grafo mixto .

Multigrafo dirigido (aristas con identidad propia)

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

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

Esta noción podría usarse para modelar las posibles conexiones de vuelo que ofrece una aerolínea. En este caso, el multigrafo sería un gráfico dirigido con pares de aristas paralelas dirigidas que conectan ciudades para mostrar que es posible volar tanto hacia como desde estos lugares.

En teoría de categorías , una categoría pequeña se puede definir como un multidígrafo (con aristas que tienen su propia identidad) equipado con una ley de composición asociativa y un autobucle distinguido en cada vértice que sirve como identidad izquierda y derecha para la composición. Por esta razón, en la teoría de categorías el término gráfico se considera estándar como "multidígrafo", y el multidígrafo subyacente de una categoría se llama dígrafo subyacente .

Etiquetado

Los multigrafos y multidigrafos también apoyan la noción de etiquetado de gráficos , de manera similar. Sin embargo, en este caso no hay unidad terminológica.

Las definiciones de multigrafos etiquetados y multidigrafos etiquetados son similares, y aquí solo definimos los últimos.

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

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

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

Definición 2 : Un multidígrafo etiquetado es un gráfico 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 gráfico etiquetado es diferente de la noción dada por el etiquetado del gráfico del artículo ).

Ver también

• Red multidimensional
• Glosario de términos de teoría de grafos
• Teoría de grafos

Notas

1. Por ejemplo, consulte Balakrishnan 1997, p. 1 o Chartrand y Zhang 2012, p. 26.
2. Por ejemplo, ver Bollobás 2002, p. 7 o Diestel 2010, p. 28.
3. Por ejemplo, consulte Wilson 2002, p. 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. Saltador. 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.). Saltador. ISBN 978-3-642-14278-9.
• Bruto, Jonathan L.; Yellen, Jay (1998). Teoría de grafos y sus aplicaciones . Prensa CRC. ISBN 0-8493-3982-0.
• Bruto, Jonathan L.; Yellen, Jay, editores. (2003). Manual de teoría de grafos . CDN. 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 : matemáticas/9310236 . Bibcode : 1993matemáticas.....10236J. doi :10.1002/rsa.3240040303. ISSN  1042-9832. SEÑOR  1220220. S2CID  206454812.
• Wilson, Robert A. (2002). Gráficas, coloraciones y el teorema de los cuatro colores. Publicación de ciencias de Oxford. ISBN 0-19-851062-4.
• Zwillinger, Daniel (2002). Tablas y fórmulas matemáticas estándar CRC (31ª ed.). Chapman y Hall/CRC. ISBN 1-58488-291-3.

enlaces externos

•  Este artículo incorpora material de dominio público de Paul E. Black. "Múltigrafo". Diccionario de Algoritmos y Estructuras de Datos . NIST .