Grafo caminho
Grafo não ramificado
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 | |
Ver também editar
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 editar
- Weisstein, Eric W. «Path Graph» (em inglês). MathWorld