Loop (teoria dos grafos) - Loop (graph theory)

Um gráfico com um loop no vértice 1

Na teoria dos grafos , um loop (também chamado de self-loop ou fivela ) é uma aresta que conecta um vértice a si mesmo. Um gráfico simples não contém loops.

Dependendo do contexto, um gráfico ou multigrafo pode ser definido de modo a permitir ou proibir a presença de loops (muitas vezes em conjunto com a permissão ou proibição de várias arestas entre os mesmos vértices):

  • Onde os gráficos são definidos de modo a permitir loops e arestas múltiplas, um gráfico sem loops ou arestas múltiplas é freqüentemente distinguido de outros gráficos chamando-o de gráfico simples .
  • Onde os gráficos são definidos de forma a não permitir loops e arestas múltiplas, um gráfico que tem loops ou arestas múltiplas é freqüentemente distinguido dos gráficos que satisfazem essas restrições chamando-o de multigrafo ou pseudógrafo .

Em um gráfico com um vértice, todas as arestas devem ser loops. Esse gráfico é chamado de buquê .

Grau

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

Um caso especial é um loop, que adiciona dois ao grau. Isso pode ser entendido permitindo que cada conexão da borda do loop conte como seu próprio vértice adjacente. Em outras palavras, um vértice com um loop "vê" a si mesmo como um vértice adjacente de ambas as extremidades da aresta, adicionando assim dois, não um, ao grau.

Para um gráfico direcionado , um loop adiciona um ao grau de entrada e um ao grau de saída .

Veja também

Na teoria dos grafos

Em topologia

Referências

  • Balakrishnan, VK; Teoria dos grafos , McGraw-Hill; 1 edição (1 de fevereiro de 1997). ISBN   0-07-005489-4 .
  • Bollobás, Béla; Teoria dos grafos modernos , Springer; 1ª edição (12 de agosto de 2002). ISBN   0-387-98488-7 .
  • Diestel, Reinhard; Teoria dos Grafos , Springer; 2ª edição (18 de fevereiro de 2000). ISBN   0-387-98976-5 .
  • Gross, Jonathon L e Yellen, Jay; Graph Theory and Its Applications , CRC Press (30 de dezembro de 1998). ISBN   0-8493-3982-0 .
  • Gross, Jonathon L e Yellen, Jay; (eds); Handbook of Graph Theory . CRC (29 de dezembro de 2003). ISBN   1-58488-090-2 .
  • Zwillinger, Daniel; Tabelas e fórmulas matemáticas padrão CRC , Chapman & Hall / CRC; 31ª edição (27 de novembro de 2002). ISBN   1-58488-291-3 .

links externos