Laço (teoria dos grafos)

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
Um grafo com um laço no vértice 1

Em teoria dos grafos, um laço ou auto-loop (em inglês: loop, self-loop ou buckle) é uma aresta que conecta um vértice a ele mesmo. Um grafo simples, não contém nenhum laço.

Dependendo do contexto, um grafo ou um multigrafo pode ser definido de forma a permitir ou proibir a presença de laços (muitas vezes em combinação com a permissão ou proibição do uso de arestas múltiplas entre os mesmos vértices:

  • Onde os grafos são definidos de modo a permitir laços e arestas múltiplas, um grafo sem laços é muitas vezes chamado de multigrafo.1 2 3
  • Onde os grafos são definidos de modo a não permitir laços e arestas múltiplas, um multigrafo ou pseudografo é muitas vezes definido como um grafo que pode ter laços e arestas múltiplas.4 5

Grau[editar | editar código-fonte]

Para um grafo não direcionado, o grau de um vértice é igual ao número de vértices adjacentes.

Um caso especial é um laço, que acrescenta dois para o grau. Isso pode ser entendido se deixando cada conexão da contagem de arestas do laço como seu próprio vértice adjacente. Em outras palavras, um vértice com um laço "vê" a si mesmo como um vértice adjacente de ambas as extremidades da aresta, assim, se soma dois e não um, para o grau.

Para um grafo direcionado, um laço soma um ao grau de entrada e um ao grau de saída

Ver também[editar | editar código-fonte]

Referências

  1. Balakrishnan, V. K.. Graph Theory (em inglês). New York: McGraw-Hill, 1997. ISBN 0-07-005489-4
  2. GROSS, Jonathon L.;YELLEN, Jay (eds.). Handbook of Graph Theory (em inglês). [S.l.]: CRC, 2003. ISBN 1-58488-090-2
  3. ZWILLINGER, Daniel. CRC Standard Mathematical Tables and Formulae (em inglês). 31ª ed. [S.l.]: Chapman & Hall/CRC, 2002. ISBN 1-58488-291-3
  4. BOLLOBÁS, Béla. Modern Graph Theory (em inglês). 1ª ed. New York/Berlin: Springer, 2002. ISBN 0-387-98488-7
  5. DIESTEL, Reinhard. Graph Theory (em inglês). 2ª ed. New York/Berlin: Springer, 2000. ISBN 0-387-98976-5

Ligações externas[editar | editar código-fonte]