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), es decir, aristas que tienen los mismos nodos finales. Así, dos vértices pueden estar conectados por más de una arista.

Hay dos nociones distintas de bordes 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 "múltiples aristas" significa que la misma arista puede aparecer varias veces entre estos dos nodos.
• Bordes con identidad propia: Los bordes son entidades primitivas al igual que los nodos. Cuando varios bordes conectan dos nodos, estos son bordes diferentes.

Un multigrafo es diferente de un hipergrafo, que es un grafo en el que un borde puede conectar cualquier cantidad de nodos, no solo dos.

Para algunos autores, los términos seudógrafo y multigrafo son sinónimos. Para otros, un seudógrafo 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 desordenados de vértices, 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 borde 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, mientras que otros los llaman pseudógrafos, reservando el término multigrafo para el caso sin bucles.

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 forma 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,
• , asignando a cada arista su nodo fuente,
• , asignando a cada borde 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 hacia y desde estos lugares.

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

Etiquetado

Multigraphs y multidigraphs también admiten la noción de etiquetado de gráficos, de manera similar. Sin embargo, no hay unidad en la terminología en este caso.

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 etiquetado G es un multigrafo con vértices y arcos etiquetados. Formalmente es una tupla de 8 donde

• V es un conjunto de vértices y A es un conjunto de arcos.
• y son alfabetos finitos de las etiquetas de vértice y arco disponibles,
• y son dos mapas que indican el vértice de origen y de destino de un arco,
• y son dos mapas que describen el etiquetado de los vértices y arcos.

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 (observe que esta noción de un gráfico etiquetado es diferente de la noción dada por el etiquetado del gráfico del artículo).