Vídeo 25- Grafos eulerianos e hamiltonianos. T. 4 cores

Introdução aos Circuitos Eulerianos

Problema das Pontes

• O objetivo é encontrar soluções para percorrer várias arestas sem repeti-las, passando por todas antes de resolver os problemas.

• Um problema clássico envolve atravessar um rio com sete pontos e a possibilidade de cruzar todas as pontes uma única vez, retornando ao ponto inicial.

Modelo Simplificado

• A situação é modelada simplificando as pontes como arestas e as zonas de terra como vértices.

• Os vértices representam diferentes partes da terra cercadas pelo rio, enquanto as ligações são as pontes entre elas.

Grau dos Vértices

• O grau ou valência de um vértice é o número de arestas que nele concorrem, podendo ser par ou ímpar.

• É importante distinguir entre vértices de grau par e ímpar; a sugestão é começar em um vértice ímpar e terminar em outro ímpar.

Análise da Possibilidade de Trajetos

Atividade 1: Vértices Ímpares

• A atividade analisa se é possível começar em um vértice e passar por todas as arestas uma única vez, terminando no mesmo ou em outro vértice.

• Se todos os outros vértices têm grau par, pode-se iniciar em um ímpar e terminar em outro ímpar.

Conceitos Fundamentais

• Um trajeto euleriano percorre todas as arestas do grafo uma única vez; não precisa terminar no mesmo ponto onde começou.

• Um circuito euleriano começa e termina no mesmo vértice, passando por todas as arestas exatamente uma vez.

Regras para Trajetos Eulerianos

Condições Necessárias

• Para existir um trajeto euleriano, deve haver no máximo dois vérticos com grau ímpar.

• Um grafo admite um circuito se todos os seus vérticos tiverem grau par; isso permite entrar e sair sem ficar preso.

Exemplos Práticos

• Em situações onde todos os graus são pares, é possível realizar o percurso completo sem restrições.

Grafo e Circuitos: Entendendo Trajetos Elianos

Conceitos de Grafo e Grau dos Vértices

• O grau de um vértice em um grafo determina se é possível sair e voltar ao mesmo ponto. Se o grau for par, pode-se retornar; se ímpar, não.

• Em um grafo com vértices de grau ímpar (como B e E), é necessário começar em um deles e terminar no outro para formar um trajeto iliano.

• Um trajeto iliano percorre todas as arestas sem repetições, mas não precisa começar e terminar no mesmo vértice.

Diferença entre Trajeto Iliano e Circuito Lariano

• É crucial distinguir entre trajetos ilianos (não precisam começar e acabar no mesmo ponto) e circuitos larianos (devem iniciar e finalizar no mesmo vértice).

• Um grafo que não é conexo, mesmo com todos os vértices de grau par, não admite circuito eliano devido à falta de conexão entre partes do grafo.

Exemplos Práticos de Circuitos Elianos

• No exemplo apresentado, a presença de dois vértices com grau ímpar impede a formação de um circuito eliano.

• Para encontrar circuitos elianos em grafos específicos, como o descrito na sequência A-B-D-C-A-D-E-B, é necessário experimentar diferentes combinações.

Problemas do Carteiro Chinês

• O problema envolve determinar se um carteiro pode percorrer todas as ruas uma única vez antes de retornar ao ponto inicial.

• Todos os vértices devem ter grau par para garantir a possibilidade de um circuito eliano; caso contrário, será necessário repetir algumas arestas.

Análise Final do Percurso

• A análise final mostra que o percurso ideal deve minimizar repetições. No entanto, se houver graus ímpares nos vértices envolvidos (como A ou D), isso complicará a solução.

Problema do Carteiro Chinês e Circuitos Eulerianos

Introdução ao Problema

• O problema envolve a repetição de arestas para transformar um grafo em um grafo euleriano, onde todos os vértices têm grau par, exceto dois.

• A questão central é se o carteiro pode fazer a entrega passando uma única vez por cada rua. Se não for possível, deve-se minimizar as ruas repetidas.

Solução Ideal

• A solução ótima ocorre quando o grafo forma um circuito de Euler. Para resolver problemas do carteiro chinês, é necessário encontrar uma maneira de criar esse circuito.

• "Elizar" refere-se à repetição econômica de arestas até que se obtenha um circuito euleriano.

Exemplos Práticos

• Um exemplo mostra que para elizar um grafo com vértices ímpares, são necessárias duplicações específicas das arestas.

• Ao duplicar a aresta entre os vértices B e E, todos os graus tornam-se pares, permitindo a formação de um circuito euleriano.

Técnicas para Elização em Grafos

Grafos Retangulares

• Em grafos grelha, muitos vértices podem ter grau ímpar. Uma técnica comum é conectar vértices ímpares sequencialmente até que todos fiquem com grau par.

Processo de Conexão

• Começa-se por qualquer vértice ímpar e conecta-se ao próximo também ímpar. Se ambos ficarem pares após a conexão, o processo continua até que todos sejam pares.

Circuitos Hamiltonianos

Definição do Circuito Hamiltoniano

• O objetivo dos circuitos hamiltonianos é passar por todos os vértices uma única vez e retornar ao ponto inicial. Não há preocupação em passar por todas as arestas.

Exemplo Prático

• Um exemplo ilustra como iniciar no ponto C e visitar outros pontos (M, F, P, Q...) antes de retornar ao C.

Distinções Importantes

• É crucial notar que nos circuitos hamiltonianos não é necessário percorrer todas as arestas; apenas os vértices devem ser visitados uma vez.

Análise Final sobre Circuitos

Características dos Circuitos Hamiltonianos

• O circuito hamiltoniano começa e termina no mesmo vértex enquanto percorre todos os outros apenas uma vez. Essa característica distingue-o dos circuitos eulerianos.

Exemplificação da Estrutura do Grafo

Circuitos Hamiltonianos e Eulerianos em Grafos

Conceitos Básicos de Grafos

• Vértices com grau ímpar, como os vértices B e E, são problemáticos para a existência de um circuito euleriano. A solução envolve duplicar uma aresta.

• Um circuito hamiltoniano é formado ao passar por todos os vértices e retornar ao inicial sem repeti-los, exceto o primeiro.

Resolução de Problemas com Grafos

• Para um grafo ter um circuito euleriano, é necessário que todos os vértices tenham grau par. A repetição da aresta EB pode ser uma solução.

• O teorema das quatro cores aplica-se à coloração de mapas, permitindo colorir qualquer mapa com apenas quatro cores diferentes.

Aplicação do Teorema das Quatro Cores

• A transformação de um mapa em grafo envolve representar países como vértices e fronteiras como arestas. Por exemplo, o país A faz fronteira com B e C.

• Após estabelecer as ligações entre os países (vértices), inicia-se o processo de coloração dos vértices.

Processo de Coloração dos Vértices

• O primeiro passo na coloração é atribuir a cor vermelha ao país A; o país B recebe a cor verde devido à sua ligação direta com A.

• O país D pode ser vermelho porque não tem fronteira direta com A, enquanto C não pode ser vermelho ou verde devido às suas ligações diretas.

Conclusões sobre Coloração em Grafos

• Com as cores vermelho, verde e azul, conseguimos colorir o mapa. Existe um teorema geral que garante que qualquer mapa pode ser colorido usando apenas quatro cores diferentes.