Multigrafo

En matemáticas , y más específicamente en teoría de grafos , un multigrafo es un grafo que puede tener múltiples aristas (también llamadas aristas paralelas ^{[ 1 ]} ), es decir, aristas que tienen los mismos nodos extremos . 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 se define ú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 .

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

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

Un multigrafo G es una tripleta ordenada 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 no ordenado 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 ]}

Un multigrafo dirigido es un grafo dirigido que puede tener múltiples arcos, es decir, arcos con los mismos nodos de origen y destino. Un multigrafo dirigido G es un par ordenado G  := ( V , A ) con

• V un conjunto de vértices o nodos ,
• Un multiconjunto 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 .

Un multigrafo 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 aristas o líneas ,​
• ${\displaystyle s:A\rightarrow V}$, asignando a cada arista su nodo de origen,
• ${\displaystyle t:A\rightarrow V}$, asignando a cada arista su nodo de destino.

Este concepto 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 multidigrafo (con aristas que poseen su propia identidad) dotado de una ley de composición asociativa y un bucle propio distinguido 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 suele interpretar como "multidigrafo", y el multidigrafo subyacente de una categoría se denomina su digrafo subyacente .

Los multigrafos y los multidigrafos también admiten la noción de etiquetado de grafos de manera similar. Sin embargo, no existe uniformidad terminológica en este caso.

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

Definición 1 : Un multigrafo etiquetado es un grafo etiquetado con arcos etiquetados .

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

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

Definición 2 : Un multigrafo 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 sobre etiquetado de grafos ).

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

• Balakrishnan, VK (1997). Teoría de grafos . McGraw-Hill. ISBN 0-07-005489-4.
• Bollobás, Béla (2002). Teoría moderna de grafos . 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". Random Structures and Algorithms . 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). Grafos, 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 de CRC (31.ª  ed.). Chapman & Hall/CRC. ISBN 1-58488-291-3.

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