Dê exemplo de dois Grafos unicursais e dois não unicursais. Justifique que seus desenhos são dos tipos escolhidos.
Passo 1
O enunciado pede para dar exemplos de dois grafos unicursais (isto é, que admitem um trajeto que percorre todas as arestas sem repeti-las e sem levantar o lápis) e dois grafos não unicursais, justificando cada caso. O critério teórico é o seguinte: num grafo conexo existe um trajeto unicursal se, e somente se, o número de vértices de grau ímpar for 0 ou 2. Se for 0, há circuito euleriano; se for 2, há trilha que não fecha; caso contrário, não há trilha unicursal.
Passo 2
Exemplo 1 (unicursal com circuito): o ciclo
com vértices
e arestas
.
Em cada vértice , que é par. Como o grafo é conexo e todos os graus são pares, existe circuito euleriano e, portanto, é unicursal.
Em cada vértice
Passo 3
Exemplo 2 (unicursal sem circuito): o caminho
com vértices
e arestas
.
Aqui (ímpar) e
(pares). Há exatamente 2 vértices de grau ímpar e o grafo é conexo, logo existe trilha euleriana que une
a
, e o grafo é unicursal.
Aqui
Passo 4
Exemplo 3 (não unicursal): a estrela
com centro
e folhas
, arestas
.
Temos e
. São 4 vértices de grau ímpar (>2), portanto não existe trilha que percorra todas as arestas sem repeti-las, e o grafo não é unicursal.
Temos
Passo 5
Exemplo 4 (não unicursal): grafo desconexo formado por dois ciclos
separados, digamos
com arestas
e
com arestas
.
Cada componente é euleriana isoladamente, mas o grafo total é desconexo e não há como traçar um único trajeto que cubra arestas de ambas, logo não é unicursal.
Cada componente é euleriana isoladamente, mas o grafo total é desconexo e não há como traçar um único trajeto que cubra arestas de ambas, logo não é unicursal.
Resposta
- Ciclo
— unicursal (graus todos pares). - Caminho
— unicursal (exatamente 2 vértices ímpares). - Estrela
— não unicursal (4 vértices ímpares). - Dois ciclos
desconexos — não unicursal (grafo não conectado).