# Euler, Hamilton, planaridade e coloração Critérios para percursos, grafos bipartidos, fórmula de Euler e número cromático. Página: https://resumos.rgo.pt/cadeiras/md/euler-hamilton-coloracao/ Num grafo, percorrer todas as arestas e visitar todos os vértices são problemas diferentes. Um grafo pode permitir o primeiro e impedir o segundo, como a borboleta abaixo. Antes de aplicar um critério, identifica o que tem de ser visitado e o que pode repetir-se. ## Trilhos e circuitos de Euler Um **trilho de Euler** usa todas as arestas exatamente uma vez. Um **circuito de Euler** é um desses trilhos que termina onde começou. Os vértices podem repetir-se. Para um grafo não dirigido com arestas, precisamos de que todos os vértices incidentes em arestas estejam na mesma componente. Sob essa condição: * Existe um circuito de Euler se e só se todos os graus são pares. * Existe um trilho de Euler se e só se há zero ou dois vértices de grau ímpar. * Se há exatamente dois ímpares, o trilho começa num deles e acaba no outro. A formulação habitual da cadeira assume o grafo conexo. Excluir vértices isolados da condição permite tratar o mesmo critério quando eles estão presentes. Um grafo sem arestas admite o percurso sem passos a partir de qualquer vértice que exista. A necessidade da paridade vem de cada visita intermédia usar uma aresta para entrar e outra para sair. Num circuito, o início também emparelha a primeira saída com a última entrada. Num trilho aberto, sobram os dois extremos. Para construir um circuito num grafo com graus pares, começa um trilho sem repetir arestas. Não fica preso num vértice diferente do inicial, pois cada entrada deixa uma saída disponível. Se ainda sobram arestas, a conectividade garante um vértice do circuito ligado a arestas não usadas. Constrói outro circuito a partir dele e intercala-o no primeiro. Repetindo, usas todas as arestas. ## Caminhos e ciclos de Hamilton Um **caminho de Hamilton** visita todos os vértices exatamente uma vez. Um **ciclo de Hamilton** faz isso e fecha-se na origem. Não precisa de usar todas as arestas. Não há um critério de paridade semelhante ao de Euler. Para provar existência, apresenta a sequência completa de vértices e verifica cada ligação. Para provar impossibilidade, usa uma obstrução necessária: * Um vértice de grau 1 impede um ciclo de Hamilton. * Um grafo desconexo não tem caminho de Hamilton que visite todos os vértices. * Se retirar um vértice separa o grafo em várias componentes, não há ciclo de Hamilton. O ciclo sem esse vértice teria de ser um caminho que ainda liga todos os restantes. Estas condições não são critérios suficientes. Ter todos os graus pelo menos 2 não garante um ciclo de Hamilton. ## O exemplo da borboleta ![Dois triângulos a-b-c-a e c-d-e-c partilham só o vértice c.](https://resumos.rgo.pt/cadeiras/md/euler-hamilton-coloracao/figura-1.svg) Os graus são $2,2,4,2,2$. Há um circuito de Euler: $$ a,b,c,d,e,c,a. $$ Usa as seis arestas uma vez e repete apenas o vértice $c$ durante o percurso. Não há ciclo de Hamilton. Retirar $c$ deixa as duas componentes $\{a,b\}$ e $\{d,e\}$; um ciclo teria de voltar a passar por $c$ para as ligar. O circuito resulta da intercalação: no primeiro triângulo, $a,b,c,a$, paramos ao chegar a $c$; percorremos $c,d,e,c$ no segundo e retomamos a aresta $c,a$. As arestas dos dois circuitos são disjuntas, por isso a intercalação não repete nenhuma. Há, no entanto, um caminho de Hamilton: $a,b,c,d,e$. O triângulo também mostra que o grafo não é bipartido. ## Grafos bipartidos Um grafo é **bipartido** quando os vértices podem dividir-se em duas partes disjuntas, de forma a que todas as arestas liguem partes diferentes. Isto equivale a poder colorir os vértices com duas cores sem ligar vértices da mesma cor. Admitimos uma parte vazia para grafos sem arestas. Um grafo é bipartido se e só se não tem ciclos de comprimento ímpar. Se alternarmos as partes ao longo de um ciclo, só voltamos à parte inicial depois de um número par de passos. Na direção inversa, podemos colorir por paridade da distância a uma origem em cada componente; uma aresta entre cores iguais permitiria construir um ciclo ímpar. Todo o ciclo par é bipartido. Todo o ciclo ímpar precisa de uma terceira cor. Todas as árvores são bipartidas, pois não têm ciclos. Se um grafo bipartido tem ciclo de Hamilton, as duas partes têm o mesmo tamanho. O ciclo alterna entre elas e visita todos os vértices. Esta condição não garante a existência do ciclo. Para $K_{m,n}$ com $m,n\ge1$, há $mn$ arestas. Num grafo bipartido simples com $v$ vértices, o máximo é $\lfloor v^2/4\rfloor$: o produto dos tamanhos das duas partes é maior quando são tão próximos quanto possível. Assim, cinco vértices e sete arestas já excluem bipartição, pois o máximo seria $2\cdot3=6$. ## Planaridade e fórmula de Euler Um grafo é **planar** quando pode desenhar-se no plano sem cruzamentos entre arestas, exceto nos extremos comuns. Ter cruzamentos num desenho não prova que seja não planar, porque pode existir outro desenho. Desenho com cruzamento ABCD Desenho sem cruzamentos ABCD Os dois desenhos representam K4: os mesmos quatro vértices e as mesmas seis arestas. O cruzamento das diagonais não é um vértice. Ao mudar a disposição dos vértices, obtemos um desenho sem cruzamentos, por isso o grafo é planar. Uma representação planar divide o plano em faces, incluindo a face exterior. Para um grafo finito, conexo e planar: $$ v-e+f=2. $$ Aqui, $v=|V|$, $e=|E|$ e $f$ é o número de faces dessa representação. Uma árvore tem uma única face, logo $n-(n-1)+1=2$. Podemos justificar a fórmula retirando arestas de ciclos. Cada remoção conserva a conectividade, diminui $e$ em 1 e junta duas faces, diminuindo $f$ em 1. Ao chegar a uma árvore, a expressão vale 2 e não mudou pelo caminho. Com $c$ componentes não vazias, a fórmula generaliza-se para $v-e+f=1+c$. Não uses a versão conexa sem conferir a hipótese. ## Limites de arestas Para um grafo simples planar com $v\ge3$: $$ e\le3v-6. $$ Se não há triângulos, em particular se o grafo é bipartido: $$ e\le2v-4. $$ Num grafo conexo que contém um ciclo, o limite de cada face percorre pelo menos três arestas, ou quatro se não há triângulos. Cada aresta conta duas vezes nos limites das faces; uma ponte conta duas vezes na mesma face. Logo $3f\le2e$ ou $4f\le2e$. Como $f=2-v+e$, a primeira dá $3(2-v+e)\le2e$, isto é, $e\le3v-6$. A segunda dá $e\le2v-4$. Se o grafo conexo não tem ciclos, é uma árvore: $e=v-1\le2v-4\le3v-6$ para $v\ge3$. Num grafo desconexo, podemos ligar as componentes por pontes sem criar triângulos ou cruzamentos. O grafo conexo obtido satisfaz os limites e tem mais arestas do que o original. Não apliques o argumento “quatro lados por face” diretamente a uma árvore. $K_5$ tem cinco vértices e dez arestas, mas $3v-6=9$, por isso não é planar. $K_{3,3}$ tem seis vértices e nove arestas; como é bipartido, o limite seria $2v-4=8$, por isso também não é planar. Satisfazer uma desigualdade necessária não prova planaridade. Para provar que um grafo é planar, podes fornecer uma representação sem cruzamentos. Para $K_4$, desenha um triângulo exterior e o quarto vértice dentro, ligado aos três. ## Coloração e número cromático Uma **$k$\-coloração** atribui a cada vértice uma das $k$ cores, com cores diferentes em extremos de cada aresta. O número cromático $\chi(G)$ é o menor $k$ possível. Para determinar esse mínimo, precisamos de duas direções: uma coloração que mostra que $k$ cores chegam e uma razão por que menos não chegam. * $\chi(K_n)=n$, porque todos os pares são adjacentes. * $\chi(C_n)=2$ se $n$ é par e $3$ se é ímpar. * $\chi(K_{m,n})=2$ se ambas as partes são não vazias. * Um grafo não vazio sem arestas tem número cromático 1. Na borboleta, um triângulo exige pelo menos três cores. Três chegam: dá uma cor a $c$, outra a $a,d$ e outra a $b,e$. Portanto, $\chi(G)=3$. Uma **clique** é um conjunto de vértices todos adjacentes entre si. Se a maior clique tem tamanho $\omega(G)$, precisamos de pelo menos esse número de cores. Por outro lado, uma coloração gulosa usa no máximo $\Delta(G)+1$, onde $\Delta$ é o grau máximo: ao colorir um vértice, os seus vizinhos já coloridos proíbem no máximo $\Delta$ cores. Portanto: $$ \omega(G)\le\chi(G)\le\Delta(G)+1. $$ Os dois limites podem ser diferentes. Em $C_5$, a maior clique tem tamanho 2, mas o ciclo ímpar exige três cores. Todo o grafo planar finito pode colorir-se com no máximo quatro cores. A recíproca é falsa: $K_{3,3}$ usa duas cores e não é planar. O número de cores também não decide se existe percurso de Euler ou de Hamilton. ## Exercícios Euler num grafo bipartido completo Decide se $K_{3,4}$ tem circuito de Euler, trilho de Euler aberto ou nenhum dos dois. E $K_{2,4}$? Pista Em $K_{a,b}$, os vértices da primeira parte têm grau $b$ e os da segunda grau $a$. Mais uma pista $K_{3,4}$ tem quatro graus ímpares; $K_{2,4}$ tem todos os graus pares. Solução Em $K_{3,4}$ há três vértices de grau 4 e quatro de grau 3. Como há quatro vértices ímpares, não existe trilho de Euler que use todas as arestas. Em $K_{2,4}$ há dois de grau 4 e quatro de grau 2. É conexo e todos os graus são pares, logo o critério de Euler garante um circuito que usa cada aresta uma vez, por exemplo $a1b2a3b4a$, com $a,b$ na parte de tamanho 2 e $1,2,3,4$ na outra. Confere a tua resposta: * Calculei os graus em cada parte. * Contei vértices de grau ímpar. * Verifiquei conectividade ignorando isolados e construí o circuito dado pelo critério. Erros frequentes Um circuito de Euler pode repetir vértices. O que não pode repetir são as arestas. [Voltar à explicação](https://resumos.rgo.pt/cadeiras/md/euler-hamilton-coloracao/#trilhos-e-circuitos-de-euler) Um ciclo de Hamilton num bipartido Pode $K_{3,4}$ ter ciclo de Hamilton? Pode ter caminho de Hamilton? Apresenta um percurso quando existir. Pista Cada passo troca de parte. Mais uma pista Num ciclo, as quantidades visitadas nas duas partes têm de ser iguais. Num caminho, podem diferir por 1. Solução Não tem ciclo de Hamilton, porque um ciclo bipartido alterna e usa o mesmo número de vértices de cada parte, mas aqui seriam 3 e 4. Tem caminho: $b_1,a_1,b_2,a_2,b_3,a_3,b_4$. Todas as arestas existem e os sete vértices aparecem exatamente uma vez. Confere a tua resposta: * Usei alternância das duas partes. * Refutei o ciclo pela diferença dos tamanhos. * Construí um caminho que visita os sete vértices uma vez. Erros frequentes Não confundas a condição de graus ímpares de Euler com Hamilton. Aqui o argumento é a alternância de vértices. [Voltar à explicação](https://resumos.rgo.pt/cadeiras/md/euler-hamilton-coloracao/#grafos-bipartidos) Dois quadrados com um vértice comum Os ciclos $a,b,c,d,a$ e $a,e,f,g,a$ partilham só $a$. Não há outras arestas. Exibe um circuito de Euler, decide se há ciclo de Hamilton e determina o número cromático. Pista $a$ tem grau 4 e os outros seis vértices têm grau 2. Os dois ciclos são pares. Mais uma pista Retira $a$ para testar Hamilton. Para colorir, começa com a mesma cor em $a,c,f$. Solução $a,b,c,d,a,e,f,g,a$ usa todas as oito arestas uma vez, logo é um circuito de Euler. Não há ciclo de Hamilton: retirar $a$ deixa as componentes $\{b,c,d\}$ e $\{e,f,g\}$, mas retirar um vértice de um ciclo de Hamilton deixaria um caminho que liga todos os restantes. Duas cores chegam, com partes $\{a,c,f\}$ e $\{b,d,e,g\}$. Cada aresta liga partes diferentes. Uma cor não chega, pois há arestas, logo $\chi(G)=2$. A articulação continua a impedir Hamilton, mesmo sem triângulos. Confere a tua resposta: * Usei as oito arestas uma vez no circuito. * Justifiquei a ausência de ciclo de Hamilton pelo vértice de articulação. * Construí uma coloração e provei que uma cor não chega. Erros frequentes Não transportes o número cromático 3 do exemplo com triângulos. Aqui as arestas permitem uma bipartição. Euler continua a admitir repetição de vértices. [Voltar à explicação](https://resumos.rgo.pt/cadeiras/md/euler-hamilton-coloracao/#o-exemplo-da-borboleta) O limite geral não chega $K_{3,3}$ tem 6 vértices e 9 arestas e satisfaz $m\le3n-6$. Isto prova planaridade? Usa um limite adequado para decidir. Pista O limite geral vale para todo o grafo planar simples, mas não caracteriza todos eles. Mais uma pista Um grafo planar simples bipartido com $n\ge3$ satisfaz $m\le2n-4$. Solução Não prova. $K_{3,3}$ é bipartido, e se fosse planar teria $9\le2\cdot6-4=8$, falso. Portanto não é planar. Satisfazer uma condição necessária mais fraca não impede falhar outra condição necessária. Confere a tua resposta: * Distingo condição necessária de suficiente. * Usei que o grafo é bipartido e simples. * Comparei 9 com 2 × 6 − 4. Erros frequentes Não uses $m\le2n-4$ em grafos que tenham triângulos. A ausência de ciclos ímpares é a hipótese que permite o limite bipartido. [Voltar à explicação](https://resumos.rgo.pt/cadeiras/md/euler-hamilton-coloracao/#limites-de-arestas) Faces e número de componentes Um grafo tem 8 vértices e 12 arestas. Sabe-se que é planar e dispõe de um desenho sem cruzamentos. Quantas faces tem, incluindo a exterior, se for conexo? E se tiver duas componentes conexas? Explica por que a contagem não pode ser feita apenas a partir de um desenho com cruzamentos. Pista Usa v − e + f = 1 + c, com c igual ao número de componentes. Solução Se for conexo, $v-e+f=2$, logo $f=2-8+12=6$. Com duas componentes, $v-e+f=1+2=3$, logo $f=3-8+12=7$. A face exterior conta uma vez, mesmo quando rodeia várias componentes. Num desenho com cruzamentos, uma interseção de arestas pode criar regiões visuais sem ser um vértice do grafo; essas regiões não são as faces a que a fórmula se aplica. Primeiro é necessária uma representação planar. Confere a tua resposta: * Usei a versão de Euler adequada ao número de componentes. * Incluí a face exterior uma só vez. * Distingui faces de uma representação planar de regiões de um desenho com cruzamentos. [Voltar à explicação](https://resumos.rgo.pt/cadeiras/md/euler-hamilton-coloracao/#planaridade-e-f%C3%B3rmula-de-euler) Número cromático de um ciclo Qual é o número cromático de $C_5$? Prova o limite inferior e apresenta uma coloração que o atinja. Pista Um ciclo ímpar não admite duas cores. Mais uma pista Tenta alternar duas cores nos cinco vértices e observa a última aresta. Solução $\chi(C_5)=3$. Com duas cores, a alternância ao longo do ciclo colocaria a mesma cor nos vértices primeiro e quinto, que são adjacentes. Logo $\chi\ge3$. A sequência de cores $1,2,1,2,3$ numa volta do ciclo é válida, logo $\chi\le3$. Confere a tua resposta: * Excluí uma coloração com duas cores pela alternância num ciclo ímpar. * Verifiquei as cinco arestas na coloração de três cores. * Concluí o valor exato a partir dos dois limites. Erros frequentes Exibir uma coloração de três cores só prova um limite superior. É preciso excluir duas cores para obter o valor exato. [Voltar à explicação](https://resumos.rgo.pt/cadeiras/md/euler-hamilton-coloracao/#colora%C3%A7%C3%A3o-e-n%C3%BAmero-crom%C3%A1tico) Construir uma representação planar Considera $V=\{a,b,c,d,e\}$. O conjunto de arestas reúne: * $\{a,b\}$, $\{b,c\}$ e $\{c,a\}$; * $\{c,d\}$, $\{d,e\}$ e $\{e,c\}$. Não há outras arestas. Desenha este grafo sem cruzamentos e verifica a fórmula de Euler com a face exterior. Pista Puxa um dos triângulos para fora. Mais uma pista A borboleta tem $5$ vértices e $6$ arestas. Solução ![Dois triângulos, a-b-c e c-d-e, ficam de lados diferentes de c sem cruzamentos.](https://resumos.rgo.pt/cadeiras/md/euler-hamilton-coloracao/figura-2.svg) Colocamos um triângulo de cada lado de $c$, partilhando só esse vértice. Todas as seis arestas estão desenhadas e só se encontram nos extremos comuns. Há duas faces interiores, uma em cada triângulo, e uma face exterior. Logo $f=3$ e $5-6+3=2$. A contagem confere Euler; o desenho sem cruzamentos é que prova planaridade. Confere a tua resposta: * Redesenhei o grafo sem cruzamentos. * Contei vértices, arestas e faces com a exterior. * Verifiquei Euler $n - m + f = 2$. Erros frequentes Um limite de arestas não prova planaridade. Uma representação sem cruzamentos fornece a prova construtiva pedida. [Voltar à explicação](https://resumos.rgo.pt/cadeiras/md/euler-hamilton-coloracao/#planaridade-e-f%C3%B3rmula-de-euler)