multigrafo

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 , sendo * um conjunto de vértices ou nós, * 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; outros chamam estes de pseudografos, reservando o termo multigrafo para os casos em que não há laços. 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 é um par ordenado , sendo * um conjunto de vértices ou nós, * um multiconjunto de pares ordenados de vértices, chamado arestas dirigidas, arcos ou flechas. Um multigrafo misto pode ser definido do mesmo jeito que um grafo misto (com arestas que podem ser dirigidas ou não).