ATA EXERCICIOS TEORIA DOS GRAFOS

Propostaos em 2002-11-06

Correspondente à aula do dia 11 – 11 – 2002

Exercício 7. 3. 2: Exibir grafos simples 3-regulares com as seguintes propriedades:

  1. Planar, mas não 3 aresta-colorável.

    2. Resposta [ Desireé]: O grafo da Figura 1.

    Justificativas:

    Planaridade: Trivial

    Não é 3 aresta-colorável: 1) Pelo absurdo: A partir do vértice central (em vermelho), pintando as 3 arestas incidentes nele, o grafo é forzado a ter mais uma cor a mais em cada um nos "pentagonos".

    2) [Comentário de Meidanis junto com a turma] Por teorema de Tutte: Eliminando o vértice central temos 3 componentes ímpares. Logo o grafo não possue 1-fator. Por outro lado, sabemos que os grafos n-regulares podem ser n-aresta coloráveis se e somente se (comentário da página 276) podem ser descompostos por 1-fatores. Como G não pode, e considerando que G é 3-regular, não e 3-aresta colorável.

     

    FIGURA 1

     

     

     

  2. 2-conexo, mas não 3 aresta-colorável.

    3. Resposta [Diogo]: O grafo de Petersen.

    Justificativas:

    O grafo é 2 conexo: Eliminando qualquer vértice o grafo ainda continua conexo (comprovação computacional).

    Não é 3-aresta colorável [Sugestão de Meidanis]: Consideramos a representação do grafo de Petersen segundo a Figura 2, e "tentamos" pintar o "ciclo exerior C5" com somente 3 cores. Temos assim uma aresta com uma cor, e as outras 4 arestas do ciclo com 2 cores cada uma (indicados com A, B e C). A partir daí as arestas são forzadas a ser pintadas como é indicado, mas chegamos a arestas adjacentes com a mesma cor.

    FIGURA 2

     

  3. Planar, com conectividade 2, mas não Hamiltoniano.

Resposta [Evandro]: O grafo da Figura 3.

Justificativas:

Planaridade: Trivial

Conectividade 2: Eliminando os vértices A e B o grafo fica desconexo. Por outro lado, é fácil ver que eliminando somente um vértice não é possível desconectar o Grafo.

Não é Hamiltoniano: Eliminando os mesmos vértices A e B, o grafo resultante tem 3 componentes conexas. Pela proposição 7.2.3 o grafo não é Hamiltoniano.

FIGURA 3

 

Em cada um dos exercícios anteriores, a 3-regularidade é comprovada computacionalmente.

 

 

Exercício 7.3.8: ...Mostrar que o número aresta-cromático do icosaedro G (ver Figura 4) coincide com o "Deltão" de G.

Resposta [Gilberto]: Dado que Deltão de G é 5, e portanto o número aresta-cromático de G é 5 o 6, é suficiente exibir uma coloração própria usando 5 cores. Tal coloração aparece na mesma Figura 4.

FIGURA 4

 

 

Exercício 7.3.14: Dado o grafo G da Figura 5, provar que não é Hamiltoniano.

 

FIGURA 5

Resposta [Janaína]: Eliminando os 6 vértices enquadrados com vermelho, o grafo resultante tem 7 componentes conexas. Pela Proposição 7.2.3 o grafo não pode ser Hamiltoniano.

Resposta Alternativa [Meidanis]: Por absurdo. Suponha que G tem um ciclo hamiltoniano C. Como o gráu dos vértices marcados com azul na figura é igual a 2, os vizinhos (em C) de tais vértices estão univocamente determinados. Unindo cada vértice marcado em azul com os seus vizinhos temos que C fecha-se sem conseguir passar pelos vértices "internos" de G. Portanto, C não é hamiltoniano.

Autor: Víctor Fernández

RA: 994992