Caminho (teoria dos grafos)

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa

Em teoria de grafos, um caminho em um grafo é uma sequência de vértices tal que de cada um de seus vértices há uma aresta para o próximo vértice da sequência. O primeiro vértice é chamado de vértice inicial e o último é chamado de vértice final.

Definição matemática[editar | editar código-fonte]

Matematicamente: Seja G um grafo. Um caminho em G é uma sequência de vértices de G, digamos

({vi1, vj1} , . . ., {vir, vjr})

tal que

vja = via+1,

para todo 1 ≤ a ≤ r − 1.

Tipos de caminhos[editar | editar código-fonte]

Um ciclo de comprimento r é um caminho constituído por r + 1 vértices, onde o primeiro vértice é igual ao último. Note que a escolha do vértice inicial em um ciclo é arbitrária.

Um caminho sem vértices repetidos é chamado de caminho simples e um ciclo sem vértices repetidos com exceção do inicial/final é um ciclo simples. Por vezes o termo "simples" é omitido de "caminho simples" e "ciclo simples", embora essa não seja a regra.

Um ciclo simples que envolva todos os vértices de um grafo é chamado de caminho hamiltoniano.

Um grafo é dito conexo se para quaisquer dois vértices existe um caminho que começa num vértice e termina no outro.

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

  • Bondy, J. A.; Murty, U. S. R. (1976). Graph Theory with Applications. North Holland. pp. 12–21. ISBN 0-444-19451-7.
  • Diestel, Reinhard (2005). Graph Theory (3rd ed. ed.). Graduate Texts in Mathematics, vol. 173, *Springer-Verlag. pp. 6–9. ISBN 3-540-26182-6.
  • Gibbons, A. (1985). Algorithmic Graph Theory. Cambridge University Press. pp. 5–6. ISBN 0-521-28881-9.
  • Korte, Bernhard; Lovász, László; Prömel, Hans Jürgen; Schrijver, Alexander (Eds.) (1990). Paths, Flows, and VLSI-Layout. Algorithms and Combinatorics 9, Springer-Verlag. ISBN 0-387-52685-4.
Ícone de esboço Este artigo sobre matemática é um esboço. Você pode ajudar a Wikipédia expandindo-o.