Grafo caminho

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
Grafo caminho
Path-graph.svg

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 P_n

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 | editar código-fonte]

Referências

  1. CERIOLI, Marcia R.; POSNER, Daniel F. D.. L(2, 1)-colorações: algoritmos e limites superiores em classes de grafos 26 pp.. Visitado em 2010-10-25.

Ligações externas[editar | editar código-fonte]