Multigrafo

Un Multígrafo es cuando se acepta más de un arco uniendo dos vértices. En términos formales, no son grafos. Un multígrafo es un grafo que consta de segmentos múltiples y lazos.

Otra definición similar es que un multígrafo es un grafo en el que hay pares de vértices unidos por más de una arista, es decir, que tiene aristas múltiples.

La imagen muestra un multígrafo con múltiples aristas en rojo y tres bucles en azul. No todos permiten multígrafos con bucles.

Esta imagen es un multígrafo con dos pares de aristas

Esto resulta sencillo transformar un pseudografo o un multígrafo en un grafo añadiendo un vértice en medio de cada lazo o de algunas aristas múltiples. En las siguientes figuras, añadiendo vértices y uniéndolos mediante aristas, se han convertido el pseudografo y el multígrafo en grafos.

Este es un grafo generado a partir de un Pseudografo de 3 lazos

Este es un grafo generado a partir de un Multígrafo con dos pares de aristas

Un multígrafo M se dice que es finito si tiene un número finito de nodos y de aristas.

Observe que un grafo G con un número finito de nodos debe automáticamente un número finito de aristas y por tanto debe ser finito.

Pero esto no es cierto para un multígrafo “M”, ya que “M” puede tener múltiples aristas.

A menos que se indique lo contrario, los grafos y multígrafos de este texto siempre serán finitos.

Tema original: Un multígrafo es un grafo dirigido que está diseñado para tener aristas múltiples, es decir, para tener aristas con los mismos nodos iniciales y finales.

Un multígrafo G es un par ordenado de G = (V,A) donde:

· “V” es un conjunto de vértices o nodos

· “A” es un multiconjunto de pares ordenados de nodos, llamados aristas dirigidas, arcos o flechas.

Un pseudografo es un grafo en el que hay aristas o lazos que tienen el mismo extremo.

Un dígrafo es un grafo donde a cada arista se le indica un sentido mediante una flecha.

Los multidigrafos o pseudomultidigrafos son combinaciones de los otros tipos de grafos. Un multidigrafo mixto G = (V, E, A) tiene la misma definición que un grafo mixto, es decir, tiene la capacidad de poseer al mismo tiempo las aristas dirigidas “A” y las aristas no dirigidas “E”.