Laço (teoria dos grafos)
Da Wikipédia, a enciclopédia livre
Da Wikipédia, a enciclopédia livre
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:
Para um grafo não direcionado, o grau de um vértice é igual ao número de arestas que nele incidem (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
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.