Grafo caminho
Origem: Wikipédia, a enciclopédia livre.
| 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 |  |
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.
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 pp. 26. Página visitada em 2010-10-25.
