Multigrafo

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
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  G = \left(V, E\right) , sendo

  • \,V um conjunto de vértices ou nós,
  • \,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 vôo 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 multidígrafo é um dígrafo (grafo com arestas dirigidas) em que pode-se ter arestas múltiplas. Um multidígrafo \,G é um par ordenado  G = \left(V, A\right) , sendo

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

Um multigrafo misto  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[editar | editar código-fonte]

Multigrafos e multidígrafos 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 multidígrafos etiquetados são similares, e definiremos apenas o último:

Um multidígrafo etiquetado é um grafo etiquetado com arcos etiquetados.

Formalmente: Um multidígrafo etiquetado G é um multigrafo com nós etiquetados e arcos. Formalmente é uma 8-tupla G=(\Sigma_V, \Sigma_A, V, A, s, t, \ell_V, \ell_A), em que:

  • \,\Sigma_V e \,\Sigma_A são alfabetos finitos de nós e etiquetas de arcos disponíveis.
  • s\colon A\longrightarrow\ V e t\colon A\longrightarrow\ V são duas funções indicando o nó de origem e o de destino de um arco.
  • \ell_V\colon V\longrightarrow\Sigma_V e \ell_A\colon A\longrightarrow\Sigma_A são duas funções descrevendo a etiquetagem dos nós e arestas.


Notas[editar | editar código-fonte]

  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

Referências[editar | editar código-fonte]