Quantas centopéias não isomorfas com seis vértices existem?

Passo 1

O enunciado pede o número de centopéias não isomorfas com seis vértices. Aqui o conteúdo é Teoria de Grafos (árvores especiais). Uma centopéia é uma árvore obtida a partir de um caminho simples (chamado de espinha) a que se pode anexar no máximo uma folha a cada vértice da espinha.

Passo 2

Seja s o número de vértices da espinha e \ell o número de folhas anexadas. Temos
s + \ell = 6, \qquad \ell \le s
pois cada vértice da espinha admite no máximo uma folha. Da segunda desigualdade resulta
6 - s \le s \quad\Longrightarrow\quad s \ge 3.
Logo só podem ocorrer s=3,4,5,6.

Passo 3

Para cada s\in\{3,4,5,6\} calculamos \ell=6-s e contamos as maneiras de escolher \ell vértices de uma espinha com s vértices, até isomorfismo. A única simetria da espinha é a reflexão (reversão da ordem dos vértices).

Passo 4

s=6, \ell=0. Não se anexa nenhuma folha, sobra o caminho P_6.
Número de não-isomorfismos: 1. s=5, \ell=1. Escolhemos 1 de 5 vértices para anexar uma folha. Até reflexão há
\bigl\lfloor\tfrac{5+1}{2}\bigr\rfloor = 3
casos distintos (âncora em extremidade, penúltimo, ou central).

Passo 5

s=4, \ell=2. Escolhemos 2 de 4 vértices; \binom{4}{2}=6 subconjuntos. Sob reflexão, as órbitas são: \{1,2\}\sim\{3,4\}, \{1,3\}\sim\{2,4\}, além de \{1,4\} e \{2,3\} fixos. Total de órbitas: 4.

Passo 6

s=3, \ell=3. Só há um jeito de anexar uma folha a cada vértice da espinha de 3 vértices.
Número de não-isomorfismos: 1.

Passo 7

Somando todos os casos:
1 \;(\!s=6\!)\;+\;3\;(\!s=5\!)\;+\;4\;(\!s=4\!)\;+\;1\;(\!s=3\!) \;=\;9.

Resposta

9

Exercícios de Livros Relacionados