Grafo caminho
No campo da matemática da teoria dos grafos, um grafo caminho ou grafo linear é um exemplo particularmente simples de uma árvore, ou seja, uma árvore com dois ou mais vértices que não tem ramificações, ou seja, contém somente vértices de grau 2 e 1.[1] Em particular, ela tem dois vértices terminais (vértices que têm grau 1), enquanto todos os outros (se houver) têm grau 2.
| Grafo caminho | |
|---|---|
 Um grafo caminho em 6 vértices | |
| vértices | n |
| arestas | n - 1 |
| Raio | ⌊n/2⌋ |
| Diâmetro | n - 1 |
| Automorfismos | 2 |
| Número cromático | 2 |
| Índice cromático | 2 |
| Propriedades | Distância-unidade Grafo bipartido Árvore |
| Notação | |
Referências
- CERIOLI, Marcia R.; POSNER, Daniel F. D. «L(2, 1)-colorações: algoritmos e limites superiores em classes de grafos» (PDF). 26 páginas. Consultado em 25 de outubro de 2010
Ligações externas
- Weisstein, Eric W. «Path Graph» (em inglês). MathWorld
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.