Multigrafo

Multigrafo com laços (azul) e arestas múltiplas (vermelho)

Multigrafo ou pseudografo é um grafo não dirigido que pode possuir arestas múltiplas (ou paralelas), ou seja, arestas com mesmos nós finais. Assim, dois vértices podem estar conectados por mais de uma aresta. Formalmente, um multigrafo G é um par ordenado ${\displaystyle G=\left(V,E\right)}$, sendo

• ${\displaystyle \,V}$ um conjunto de vértices ou nós,
• ${\displaystyle \,E}$ um multiconjunto de pares não-ordenados de vértices, chamado arestas ou linhas.

Alguns autores também consideram multigrafos aqueles que têm laços, isto é, uma aresta que conecta um vértice a ele mesmo[1]; outros chamam estes de pseudografos, reservando o termo multigrafo para os casos em que não há laços[2].

Multigrafos podem ser usados, por exemplo, pra modelar as possíveis conexões de voos oferecidas por uma linha aérea. Nesse caso o pseudografo seria um grafo dirigido com pares de arestas paralelas dirigidas conectando cidades para mostrar que é possível voar para e a partir destas locações.

Um multidigrafo é um digrafo (grafo com arestas direcionadas) em que pode-se ter arestas múltiplas. Um multidigrafo ${\displaystyle \,G}$ é um par ordenado ${\displaystyle G=\left(V,A\right)}$, sendo

• ${\displaystyle \,V}$ um conjunto de vértices ou nós,
• ${\displaystyle \,A}$ um multiconjunto de pares ordenados de vértices, chamado arestas dirigidas, arcos ou flechas.

Um multigrafo misto ${\displaystyle G=\left(V,E,A\right)}$ pode ser definido do mesmo jeito que um grafo misto (com arestas que podem ser dirigidas ou não).

Etiquetas

Multigrafos e multidigrafos podem suportar a noção de grafos etiquetados, de modo similar. Contudo não há consenso na terminologia nesse caso.

As definições de multigrafos e multidigrafos etiquetados são similares, e definiremos apenas o último:

Um multidigrafo etiquetado é um grafo etiquetado com arcos etiquetados.

Formalmente: Um multidigrafo etiquetado G é um multigrafo com nós etiquetados e arcos. Formalmente é uma 8-tupla ${\displaystyle G=(\Sigma _{V},\Sigma _{A},V,A,s,t,\ell _{V},\ell _{A})}$, em que:

• ${\displaystyle \,V}$ é um conjunto de nós e ${\displaystyle \,A}$ é um multiconjunto de arcos.

• ${\displaystyle \,\Sigma _{V}}$ e ${\displaystyle \,\Sigma _{A}}$ são alfabetos finitos de nós e etiquetas de arcos disponíveis.

• ${\displaystyle s\colon A\longrightarrow \ V}$ e ${\displaystyle t\colon A\longrightarrow \ V}$ são duas funções indicando o nó de origem e o de destino de um arco.

• ${\displaystyle \ell _{V}\colon V\longrightarrow \Sigma _{V}}$ e ${\displaystyle \ell _{A}\colon A\longrightarrow \Sigma _{A}}$ são duas funções descrevendo a etiquetagem dos nós e arestas.

Referências

1. Para exemplos, veja. Bollobas, p. 7 and Diestel, p. 25.
2. Graphs, Colourings and the Four-Colour Theorem, by Robert A. Wilson, 2002, ISBN 0198510624, p. 6

Ligações externas

• http://www.utm.edu/departments/math/graph/glossary.html#multigraph

Bibliografia

• Diestel, Reinhard; Graph Theory, Springer; 2nd edition (February 18, 2000). ISBN 0-387-98976-5.