Notas de Aula Introdução a Teoria dos Grafos

Notas de Aula de\nMatemática Finita\n\nIntrodução à Teoria dos Grafos\n\nÍndice\n\n1. Grafos 04\n2. Exemplos de grafos 04\n3. Tipos de grafos 07\n4. Grafos como modelos 08\n5. Conceitos elementares 14\n6. Grafos conexos 14\n7. Grafos eulerianos 17\n8. Isomorfismo de grafos 26\nExercícios extras 28\n\nMayo de 2007\nversão 1.2 Teoria dos Grafos\n\n§1. GRAFOS\nUm grafo G = (V, E) é um conjunto finito e não vazio V e um conjunto E de pares não ordenados de elementos distintos de V.\n\nPor exemplo, um grafo G pode ser dado por:\nV(G)={v1,v2,v3,v4}\nE(G)={e1={v1,v2},e2={v1,v3},e3={v2,v3},e4={v3,v4}}\n\nEm um grafo G = (V, E), V é o conjunto de vértices de G e cada elemento de V é chamado de vértice. O número de vértices de um grafo é chamado de ordem de G, logo a ordem de G é |V|. No exemplo acima, a ordem de G é 4.\n\nCada elemento do conjunto E é chamado de aresta e E é o conjunto de arestas do grafo. [E de “edge.”]\n\nEm geral, é conveniente denotar uma aresta {u,v} simplesmente por u-v; as, equivalentemente, por ou.\n\nTrabalhando com grafos é em geral conveniente representá-los por meio de diagramas. Em tal representação, indicamos os vértices por pequenos círculos e as arestas por segmentos de reta ou curvas ligando os círculos apropriados. As arestas devem ser desenhadas de forma a não passar por nenhum outro círculo que não sejam os seus extremos. Diagramas do grafo dado acima são mostrados abaixo. Embora os diagramas pareçam ser diferentes, eles representam o mesmo grafo pois contêm exatamente o mesmo conjunto de vértices e de arestas. Observe que o primeiro diagrama usa somente linhas retas enquanto que no segundo há linhas curvas. E no segundo diagrama, as linhas que representam as arestas e e3 e e3 intersectam. Isto é permitido (de fato, às vezes é inevitável), mas não devemos confundir este ponto de interseção com um vértice.\n\nDado que um diagrama (também chamado de representação gráfica) de um grafo descreve completamente o grafo, é consu-mido conveniente referir-se ao diagrama do grafo como sendo o grafo.\n\nMais definições:\nSe e = e(u) ∈ E(G), isto é, se u é uma aresta do grafo, então dizemos que e liga u e v, que u e v são extremos de e, e que u e v são adjacentes ou vizinhos. Dizemos ainda que e é incidente em e e e é incidente em u (e in.).\n\nSe u ∈ E(G) dizemos que u e v são não-adjacentes. As arestas e2 e e3 são adjacentes enquanto que e3 é incidente em v3.\n\nSeja G = (V, E) um grafo e v ∈ V. O grau de e é o número de arestas incidentes em v. ou, dito de outra maneira, é o número de vértices vizinhos a v em G. O grau de um vértice é denotado por g(v) ou por g(v) quando o grafo está subentendido.\n\nNo exemplo, temos:\n\ng(v1)=2 g(v2)=2 g(v3)=3 g(v4)=1\n\nO conjunto Adj(e) é o conjunto formado por todos os vértices adjacentes a e, em G.\n\nNo exemplo, temos:\nAdj(v1)={v2,v3}, Adj(v2)={v1,v3}, Adj(v3)={v1,v2,v4} e Adj(v4)={v3}. Exercícios:\n1) Desenhe o diagrama dos seguintes grafos:\n V(G) = { 1, 2, 3, 4, 5 }\n E(G) = { 12, 14, 15, 23, 35, 45 }\n T(H) = { a, b, c, d, e, f, 1, 2, 3, 4, 5 }\n2) Se um grafo tem ordem 3, quantas arestas ele tem ?\n De todas as possibilidades de grafos com ordem 3.\n3) Existe um grafo de ordem 4 tal que cada dois vértices são adjacentes e cada duas arestas são adjacentes?\n É o grafo ter ordem igual a 3?\n4) Se G é um grafo com n vértices, quantas arestas, no má-ximo, G pode ter?\n5) Se G é um grafo de ordem n (n ≥ 2), qual é o menor número de arestas que G deve ter de modo a ter um vér-tice adjacente a todos os outros?\n6) Se G é um grafo de ordem n (n ≥ 2), qual é o menor número de arestas que G deve ter de modo a todo vértice ter um vizinho?\n7) Dê exemplo de um grafo de ordem n e a seguinte propriedade: - todo vértice tem grau 2.\n8) Prove que, em todo grafo com n vértices (n ≥ 1), existem dois vértices com o mesmo grau. §2. EXEMPLOS DE GRÁFOS:\n Nesta se-ção examinaremos alguns tipos importantes de grafos.\n Aconselhamos o leitor a familiarizar-se com seus nomes e formas, dado que eles aparecem frequentemente em exemplos e exercícios.\n\nGrafo Trivial:\n O grafo G = (V,E) tal que |V|=1 e E =∅ é cha-mado de grafo trivial.\n\nGrafo Totalmente Desconexo:\n Um grafo G = (V,E) tal que E =∅ é chamado de to-talmente desconexo. Tal grafo com n vértices é deno-tado por Nn. A figura ao lado ilustra N4.\n\nGrafo Completo:\n Um grafo G = (V,E) tal que quaisquer dois de seus vér-tices são adjacentes é um grafo completo. Tal grafo com n vértices é denotado por Kn. A figura ao lado ilustra K4.\n\nGrafos Regulares:\n Um grafo G = (V,E) é k-regular se todos os vér-tices de V têm grau igual a k. Se o grafo for k-regular para algum d, dizemos que ele é regular.\n Se o grafo for d-regular, ele também é chamado de cúbico. Por exemplo, o grafo K3 é cúbico. A figura ao lado ilustra um grafo 3-regular também conhecido como grafo de Petersen.\n\nCiclos:\n Um grafo G = (V,E) é um n-ciclo se seu conjunto de vértices pode ser rotulado de 1 a n de forma que seus únicos arestas sejam 12, 23,...,n1.\n Tal grafo com n vértices é denotado por Cn. A figura ao lado ilustra Cn. Caminhos:\n Um grafo G = (V,E) é um n-caminho se seu conjunto de vértices pode ser rotulados de 1 a n de forma que suas únicas arestas sejam 12, 23,...,n-1n. Tal grafo com n vértices é denotado por Pn. A figura ao lado ilustra P5. [ P de path ]\n\nGrafos Platônicos:\n Entre os grafos regulares há um interesse especial os grafos platônicos, que são o grafo formado pelos vértices e arestas dos cinco sólidos regulares (poliedros de Platão), a saber: o tetraedro, o cubo, o octaedro, o dodecaedro e o icoedro. O tetraedro e o cubo formam ilustrados na página anterior, o octaedro é ilustrado ao lado.\n Fica como exercício ilustrar o dodecaedro e o icoedro. (ex. 7)\n\nGrafos Bipartidos:\n Dado um grafo G = (V,E) em que V pode ser par-ticionado em dois conjuntos V1 e V2 (isto é, V = V1 ∪ V2, V1 ∩ V2 = ∅) de forma que não exista aresta entre dois vértices de V1 e nem entre dois vértices de V2, então dizemos que G é bipartido, com bipartição (V1, V2). A figura ao lado ilustra um grafo bipartido com V1 consistindo de dois vértices e V2 consistindo de três vértices.\n Observe que os grafos Pn, n ≥ 4 são bipartidos.\n Um grafo bipartido completo é um grafo bipar-tido com bipartição (V1,V2) tal que todo vértice de V1 é adjacente a todo vértice de V2. Se |V1| = r e |V2| = s, tal grafo bipartido completo é denotado por Kr,s.\n Um grafo bipartido completo da forma K1,s é denominado s-estrela. Na figura ao lado temos K1,s. Exercícios:\n\n1) Quantas arestas possui o grafo completo Kn?\n\n2) Desenhar todos os grafos cúbicos com 8 ou menos vértices.\n\n3) Citar exemplo (se existir), de:\n(i) um grafo bipartido regular;\n(ii) um grafo cúbico com 9 vértices;\n(iii) um grafo platônico bipartido;\n(iv) quantos grafos 4-regulares;\n\n4) Quantos vértices e arestas tem um grafo bipartido completo kr,s?\n\n5) O cubo Qn é o grafo cujos vértices correspondem às sequências binárias de n elementos e existe uma aresta entre dois vértices se e somente se as sequências diferem em exatamente uma posição.\nDesenhe Q1, Q2, Q3,…,Qn.\nQuantos vértices e arestas tem Qn?\nMostre que Qn é regular.\nOs Q1 é bipartido? E Q2? E Q3?…?\n\n6) O grafo de Petersen é bipartido?\n\n7) Desenhe o grafo dodecaedro e o grafoicosaedro.\n\n8) Para que valores de k cada um dos grafos platônicos é regular?\n\n9) Para que valores de n os grafos Kn não são bipartidos? Kn é regular?\n\n10) Os grafos Kn são regulares? São bipartidos? 3. Tipos de Grafos (Alguns)\nUm grafo simples G é um conjunto finito e não vazio V e um con- junto E de pares não ordenados de elementos distintos de V. G=(V,E)\n\nEx:\nv({a,b,c,d})\nE({a,b},{a,c},{a,d})\n\nUm grafo com laços G é um conjunto finito e não vazio V e um conjunto E de pares não ordenados de elementos de V. G=(V,E)\n\nEx: G1 é grafo com laços\n G2=(V,E,E2) tal que V=V1 e E2=E1∪{c,c},\ntambém é grafo com laços\n\nUm multigrafo G é um conjunto finito e não vazio V e um multiconjunto E de pares não ordenados de elementos de V.\n\nEx: G1 = e = {s1,s2} multigrafos.\nG4 = G5 = (V1,E5) tal que V5=V2 e E5=E2∪{a,b},\ntambém é um multigrafo.\n\nUm dígrafo (simples) D é um conjunto finito e não vazio V e um conjunto E de pares ordenados de elementos distintos de V. D=(V,E)\nUm dígrafo também é chamado de grafo direcionado ou, ainda, de grafo orientado.\n\nEx:\nv(b)={a,b,c,d}\nE(D)={ (a,b),(a,c),(c,b),(c,d)}\n\nDe forma análoga definem-se dígrafos com laços e multigrafos. 14. Grafos como modelos matemáticos.\n\nA construção de modelos matemáticos pode tomar várias formas e envolver muitas áreas da matemática. Uma área da matemática que tem se mostrado muito proveitosa para construir tais modelos é a teoria dos grafos.\nNesta seção apresentamos exemplos de situações e descrevemos os grafos apropriados que servem como modelos matemáticos.\n\n1) Um professor deseja separar em grupos de 4 alunos todos os alunos de uma sala, mas ele deseja que em cada grupo os alunos sejam mutuamente amigos.\nA classe pode ser vista como um grafo (simples) em que os alunos são os vértices e as arestas representam a relação de amizade entre os amigos.\nO professor deseja uma partição em subgrafos K4 do grafo dado.\n\n2) Algumas ilhas estão localizadas na costa do Rio de Janeiro. Suponha que uma linha de ferryboats opere da costa entre certas ilhas. Suponha ainda que os barcos viajam também entre as ilhas.\nEsta situação pode ser representada por meio de um grafo onde os vértices representam as ilhas e a costa e dois vértices são adjacentes se e somente existe um barco que viaja de um lugar a outro.\n\n3) Uma cidade em ruas de mão única e mão dupla. O tráfego da cidade pode ser indicado por meio de um dígrafo. Por exemplo, podemos representar as esquinas por vértices e uma aresta de u para v se e somente se é possível trafegar legalmente da esquina u até o esquina v, não passando por nenhuma outra esquina. 4) Em um grupo de n pessoas (n≥2), sempre existem pelo menos duas pessoas que têm o mesmo número de amigos neste grupo.\nO grafo referente a este problema tem um vértice para cada pessoa e dois vértices são adjacentes se e somente se as pessoas correspondem dentes são amigas.\n\nDuas pessoas têm o mesmo número de amigos no grupo e equivale, no grafo, pelo menos dois vértices têm o mesmo grau.\n\n5) Considere o tabuleiro de xadrez nxn, n≥3, suponha que um cavalo foi colocado em um dos n² quadrados. De acordo com os lados do xadrez, um cavalo move-se primeiro dois quadrados verticalmente ou horizontalmente e, depois, mais um quadrado na direção perpendicular.\n\nSegundo as regras do xadrez, é possível que este cavalo visite todo o tabuleiro, visitando cada quadrado exatamente uma vez? Como representar por grafos este problema?\n\n6) Em um torneio de basquete em que todos os times jogam entre si, vence o que tiver vencido o maior número de vezes. Os times correspondem aos vértices de um diagrama e, se o time u venceu o time v, existe uma aresta de u para v no diagrama. O time vencedor é representado pelo vértice que possui o maior número de saídas dele. 1) No exemplo 1 (da página 04), que observação pode ser feita em linguagem de grafos, com a pessoa mais popular da classe? E o que pode ser dito sobre um aluno que acabou de ser matriculado?\n\n2) Suponha que associamos um gráfico G com um curso ida seguinte maneira: os vértices correspondem aos alunos e dois vértices são adjacentes se o comenta se os alunos correspondentes têm o mesmo orientador. O que pode ser dito sobre este gráfico? Suponha que todos os alunos têm um orientador.\n\n3) Qual seria uma questão importante a ser perguntada sobre a situação do exemplo 2? Esta questão poderiam ser respondida com a ajuda do gráfico correspondente?\n\n4) Dê uma situação da vida real que pode ser representada por meio de um gráfico.\n\n5) Compare o exemplo 4 (pg 04) com o exercício 8 (pg 05).\n\n6) Como seria um gráfico que modela o exemplo 5? Desenhe os tabuleiros 3x3, 4x4 e 5x5 e seus gráficos equivalentes. Em algum deles é possível o passeio do cavalo?\n\n7) No modelo do torneio de basquete do exemplo 6, o que acontece quando os times empatam em uma partida? Dê uma sugestão para modelar este caso.\n\n8) No modelo do torneio de basquete do exemplo 6, pode acontecer de dois times empatarem no final do torneio? 5. Conexões elementares de teoria dos grafos.\nTeorema 1: Para todo grafo G, a soma dos graus de seus vértices é duas vezes o número de suas arestas.\nEm símbolos:\n∑_{v∈V} g(v) = 2|E|.\n\nprova: por indução em |V|.\n(base): Se |V|=0, então o grafo é totalmente desconexo e portanto ∑_{v∈V} g(v) = 0 e |E| = 0.\n(hipótese): Se |V|=m, então o grafo G é tal que ∑_{v∈G} g(v) = 2m.\n\n(passo): Seja G_{m} = (V,E) um grafo tal que |V|=m+1, m>0, e seja e ∈ E sendo u e v os extremos de e.\nConsidere o grafo G' = (V \ {e}, E \ {e}). Logo G' é um grafo com m arestas e, pela H.I., temos:\n∑_{v∈G} g(v) - ∑_{v∈G'} g(v) = g(u) + g(v) = ∑_{v∈G} g(v) - 2.\n\nE, substituindo em (1), temos:\n∑_{v∈G} g(v) - 2 = 2 (|V| - 1) - 2.|E| = 2|E|. ∎\n\nTeorema 2: Todo grafo contém um número par de vértices de grau ímpar.\nprova: Seja G um grafo. Se G não contém vértices de grau ímpar, então o resultado segue imediatamente. Caso contrário, suponha que G tem k vértices de grau ímpar (k>0). denote-os por a_1, a_2, ..., a_k , sendo {a_1, a_2, ..., a_k = V}, 1 < n.\nPelo teorema 1,\ng(a_1) + g(a_2) + ... + g(a_k) = 2|E|.\n\nComo cada um dos números g(a_i), g(a_i+1), ..., g(a_k) é par,\n{g(a_i+1) + ... + g(a_k)} também é par. E portanto,\ng(a_1) + ... + g(a_k) = 2|E| - (g(a_i) + ... + g(a_k)) também é par.\n\nNo entanto, cada um dos números g(a_i), g(a_i+1) é ímpar,\no que implica em que lhe deve ser par; isto é, g tem um número par de vértices de grau ímpar.\n\nExercícios:\n1) Determine g(a_1), 16 < 8.\nQuantos vértices e quantas arestas tem o grafo?\nNote que o teorema 1 vale neste caso.\n\n2) Mostre que não existe grafo com vértices cujos graus são:\na) 2,3,3,4,4, 4 = 5\nb) 2,3,3,4,4 = 5\nc) 4,3,3,3\nd) 2,2,2,2,2,3\n\n3) Suponha que conhecemos os graus de todos os vértices de um grafo G. É possível determinar a ordem de G e seu número de arestas?\n\n4) Suponha que conhecemos a ordem e o número de arestas de um grafo G. É possível determinar o grau de seus vértices?\n\n5) Prove ou dê contra-exemplo para cada uma das seguintes afirmações:\n(a) Não existem grafos que só tenham vértices de grau ímpar. (b) Não existem grafos que só tenham vértices de grau par.\n(c) Se um grafo tem ordem ímpar, então ele tem um número ímpar de vértices de grau par.\n\nCOMPLEMENTO DE UM GRAFO\n\nDado um grafo (simples) G = (V, E), definimos o complemento do grafo G como sendo o grafo G̅ = (V, E̅) onde\nu e v são adjacentes em G̅ se e somente se u e v não são adjacentes em G.\n\nExemplo:\na_1\na_2 a_3\n\nExercícios:\n1) Se um grafo G tem n vértices, somente um não tendo grau ímpar, quantos vértices de grau ímpar existem no complemento de G?\n\n2) Prove que um grafo e seu complemento não podem ser ambos desconexos. [A definição de desconexo estará nas próximas páginas.]\n\n3) Se G é um grafo completo, o que pode ser dito sobre G?\n\n4) Se G é bipartido, o que pode ser dito sobre G?\n\n5) Dê o complemento do grafo de Petersen. 6. Grafos Conexos\n\nPara discutir o conceito de connected de grafos, vamos primeiramente discutir alguns conceitos relacionados.\n\nSeja G = (V, E) um grafo. Um grafo H é um subgrafo de G se V(H) ⊆ V(G) e E(H) ⊆ E(G).\nA figura abaixo ilustra um grafo G e um subgrafo H de G.\n\na_1 a_2\n\na_3 a_4\n\nSeja G um grafo u e v dois vértices de G. Um u-v passeio em G é uma sequência alternada de vértices e arestas de G, começando em u e terminando em v, de forma que os extremos de cada aresta são exatamente os vértices que a cercam no passeio.\n\nPor exemplo, u_1, u_2, v_3, u_2, v_1, v_2, u_1 é um u-v passeio em G, da figura acima.\nObserve que a aresta u_2 v_3 aparece duas vezes no passeio.\nUm u-v passeio também é chamado de passeio de u a v.\n\nObserve também que, em um grafo simples, basta listar os vértices de um passeio, porque as arestas ficam subentendidas. No exemplo acima, o passeio dado pode ser escrito simplesmente como u_1, u_2, v_1, v_2.\n\nUma u-v trilha em um grafo é um u-v passeio que não repete arestas. O u-v passeio dado anteriormente não é uma u-v trilha. No entanto, u_2, v_3, u_3, v_1 é uma u-v trilha no grafo G. um u-v caminho é um u-v passeio (ou uma u-v trilha) que não tem vértices repetidos. No exemplo dado, v0, v1, v3, v4 é um v0-v4 caminho. Observe que, se não tem vértices repetidos, não pode ter arestas repetidas.\n\nUm grafo G é conexo se existe um u-v caminho para todo par u,v de vértices de G. Caso contrário, G é desconexo. O grafo da figura abaixo é desconexo pois não existe um 1-4 caminho.\n\nUm subgrafo H de um grafo G é chamado de componente conexo de G se H é conexo e não é subgrafo de nenhum outro subgrafo conexo de G com mais arestas ou vértices que H. No grafo da figura acima, existem dois componentes conexos, a saber\n\nSe um grafo tem somente um componente conexo, então G é conexo. E, se é conexo, tem um único componente conexo.\n\nUma u-v trilha em que u = v* e que contém pelo menos três arestas é chamada de circuito ou trilha fechada. Um circuito que não tem vértices repetidos é chamado de ciclo. Por exemplo, no grafo G1, v1, v2, v3, v5, v4, v1 é um circuito mas não é um ciclo, enquanto que v1, v2, v3, v4, v1 é um ciclo (e também um circuito).\n\nO comprimento de um passeio (trilha, caminho) é o número de arestas que ele contém. Os conjuntos de vértices e arestas determinados por um passeio produzem um subgrafo. É comum fazermos referência a este subgrafo como passeio. Por exemplo, v1, v2, v3, v4, v5 é uma trilha no grafo G da página anterior. Definimos o subgrafo H de G, por V(H) = {v1, v2, v3, v4, v5} e E(H) = {v1, v2, v3, v4, v5}, Asim, H também é chamado de trilha em G.\n\nO mesmo vale para caminhos, circuitos ou ciclos.\n\nExercícios:\n\n1) Seja G um grafo. Se existe um u-v passeio em G, então existe um u-v caminho em G?\n\n2) Dê exemplo, se for possível, de um grafo com quatro componentes conexos onde cada componente é um grafo completo.\n\n3) Sejam n e p inteiros, tais que 1 <= p < n. Dê um exemplo de um grafo de ordem n e p componentes conexos.\n\n4) Seja G um grafo de ordem 13 contendo 3 componentes conexos. Mostre que pelo menos um componente de G tem pelo menos cinco vértices.\n\n5) Seja G um grafo de ordem n (n>2) e suponha que para todo vértice v de G, g(v) > n-1/2. Prove que G é conexo.\n\n6) No grafo ao lado, dê um exemplo de um circuito C que não é um ciclo. Desenhe o subgrafo de G cujos vértices e arestas pertencem a C.\n\nDe um exemplo de:\n(a) Uma trilha que não é um caminho, (b) um caminho (c) um ciclo.\n\n7) Mostre que se G é um gráfico tal que g(v) >= 2 para todo v ∈ V(G), então G contém um ciclo. § 7. Grafos Eulerianos\nO problema mais antigo de que se tem notícia que foi modelado em teoria de grafos (ou conceitos relacionados) é o problema das sete pontes de Königsberg, de 1736.\n\nNa cidade de Königsberg havia, no século 18, sete pontes que cruzavam o rio Pregel. Elas ligavam duas ilhas no rio entre si e com as margens. Os moradores de Königsberg preocupavam-se com o seguinte problema: É possível passear pelas sete pontes, em um passeio contínuo, sem repetir nenhuma ponte?\n\nA figura abaixo mostra um esquema de Königsberg, com as porções de terra denominadas por A, B, C e D.\n\nA situação em Königsberg pode ser convenientemente representada por um multigrafo, cujos vértices correspondem às áreas de terra e cujas arestas correspondem às pontes. O problema das pontes de Königsberg é essencialmente o problema de determinar se o multigrafo M1 tem uma trilha (possivelmente um circuito) que contém todas as arestas de M.\n\nVocê pode tentar um método de tentativa-e-erro e, provavelmente, você concluirá que tal trilha não existe em M. No entanto, como provar que tal trilha não existe?\n\nLeonhard Euler foi o primeiro a fazer tal prova. Em sua homenagem, trilhas feitas que contêm todas as arestas e vértices de um grafo são chamadas de trilhas eulerianas e grafos que admitem uma trilha euleriana são chamados de grafos eulerianos.\n\nO grafo da figura abaixo é euleriano, pois a trilha 3, 2, 1, 7, 6, 3, 7, 2, 6, 1, 5, 4, 3 é euleriana.\n\nObserve que grafos desconexos não são eulerianos. O teorema a seguir dá uma solução muito simples para o problema de determinar quais grafos (e multigrafos) são eulerianos.\n\nTEOREMA 1: Um multigrafo G é euleriano se e somente se G é conexo e todo vértice de G tem grau par.\n\nprova:\nSeja G um multigrafo euleriano, e seja T uma trilha euleriana em G. Por definição, T contém todos os vértices de G, logo existe um u-v caminho para todo par de vértices de G e G é conexo. Faz falta mostrar que todo vértice de G tem grau par. Vamos supor que T começa e termina em um vértice u. Primeiro considera um vértice diferente de u. Como u não é nem o primeiro e nem o último vértice de T, cada vez que u é encontrado, alguma aresta de T inicia em u e entra em outra aresta de T incide em u saindo, logo, cada ocorrência de u em T aumenta o grau de u de duas unidades. Logo u tem grau par em G.\n\nNo caso do vértice u, cada ocorrência de u em T (exceto a primeira e a última) contribui com duas unidades no grau de u, enquanto que as ocorrências antes e a final contribuem uma unidade de cada. Portanto, todo vértice de G tem grau par.\n\nAgora, vamos considerar a recíproca. Seja G um multigrafo conexo em que todo vértice tem grau par. Vamos mostrar que G é euleriano. Para isto, vamos mostrar que é possível particionar as arestas de G em um conjunto \u03a6 de ciclos, do seguinte modo. Como cada vértice de G possui grau maior ou igual a 2, pelo ex. 7 pg. 16, G contém necessariamente algum ciclo C1. Se C1 contém todas as arestas de G1, o particionamento \u03a6 está terminado. Caso contrário, remove-se de G as arestas do ciclo C1 e os vértices isolados, porventura formados após esta operação. No novo grafo assim obtido, cada vértice possui ainda grau par. \nDetermina-se assim um novo ciclo e assim por diante. Para determinar a trilha euleriana, considera-se um ciclo, por exemplo C1, do particionamento \u03a6. Se não há mais ciclos de \u03a6 a serem. considerados, a prova está concluída. Caso contrário, como G é conexo, existe um ciclo C1 \u2208 \u03a6 tal que C1 e C2 possuem um vértice comum u. Então a trilha formada pela união das arestas de C1 e de C2 (e dos vértices de C1 e de C2) contém cada uma dessas arestas exatamente uma vez. Repete-se o processo, considerando um novo ciclo C3 \u2208 \u03a6 ainda não considerado e assim por diante.\n\nObserve que na prova do Teorema 1 temos um processo construtivo para determinar uma trilha euleriana em um multigrafo euleriano.\n\nVamos considerar agora um conceito análogo. Se um grafo G tem uma trilha, que não é um circuito, contendo todos os vértices e arestas de G, então dizemos que G é um grafo traçável. A figura abaixo ilustra um grafo traçável e P: 1, 2, 3, 4, 5, 4 é uma trilha euleriana aberta.\n\nO teorema seguinte indica precisamente quais grafos são traçáveis.\n\nTEOREMA 2: Um multigrafo G é traçável se e somente se G é conexo e tem exatamente dois vértices de grau ímpar. E mais, qualquer trilha euleriana aberta de G começa em um e termina em outro vértice de grau ímpar.\n\nPodemos agora observar que o grafo M (pg. 17) não é nem euleriano e nem traçável. Este fato nos dá uma solução para o problema de Königsberg. Uma propriedade interessante dos multigrafos eulerianos e triáveis é que uma vez que os vértices são desenhados, é possível desenhar as arestas como uma linha acontinuada. Em outras palavras, as arestas podem ser desenhadas 'sem tirar o lápis do papel' e sem repetir isso.\nSabemos agora decidir se os desenhos abaixo podem ou não ser desenhados sem tirar o lápis do papel sem repetir isso. EXEMPLO 1:\nA figura abaixo ilustra a planta baixa de uma casa com várias salas, portas entre as salas e entre as salas e o exterior. É possível começar em algum lugar (ou em uma sala ou no exterior) e passar por cada uma das portas exatamente uma vez?\n\nUsamos um multigrafo como o modelo matemático desta situação. Primeiro, associamos um vértice a cada sala e um vértice ao exterior. Dois vértices adjacentes se existe uma porta ligando os dois am- bientes correspondentes. A resposta ao problema original depende do multigrafo ser euleriano, triável ou nenhum dos dois.\nObservamos que os vértices B, D, E, F têm grau ímpar, logo, o multigrafo não é triável nem euleriano e, portanto, não é possível percorrer a casa passando exatamente uma vez por cada porta. Exercícios:\n1) Classifique os grafos abaixo como euleriano, triável ou nenhum dos dois:\n\n2) Dê um exemplo de um grafo de ordem 10 que é:\n(a) euleriano\n(b) triável\n(c) nem euleriano nem triável.\n\n3) Sejam G1 e G2 dois grafos eulerianos sem vértices em comum. Seja u ∈ V(G1) e v ∈ V(G2). Construa o grafo G formado por G1 e G2 mais a aresta u, v, isto é, V(G) = V(G1) ∪ V(G2) e E(G) = E(G1) ∪ E(G2) ∪ {u, v}.\n\n4) Mostre que se M é um multigrafo triável, é possível cons- truir um multigrafo euleriano a partir de M com a adição de uma única aresta.\n\n5) E se, no exercício 4, M fosse um grafo simples?\n\n6) Tente determinar que propriedade especial tem um multigrafo conexo com exatamente quatro vértices de grau ímpar.\n\n7) Prove o teorema 2 (página 20). a) O grafo poliedrico bola de futebol B = (V, E) está representado na figura abaixo.\n\n(b) Qual é a ordem de B?\n(c) B é bipartido?\n(d) B é regular?\n(e) B é euleriano?\n\nModele em teoria dos gráficos e responda a seguinte pergunta:\nÉ possível construir uma bola de futebol, começando e terminando no mesmo ponto e não construindo duas vezes o mesmo local? a) O diagrama abaixo mostra a cidade de Libb. É possível caminhar pela cidade de Libb e cruzar cada ponto exatamente uma vez? Se sim, como isso pode ser feito?\n\nb) Suponha que existe um arquipélago com 4 ilhas onde há uma linha de barco entre cada duas ilhas. É possível dar um passeio, não necessariamente um passeio fechado, que usa cada linha de barcos exatamente uma vez? Se sim, como isto pode ser feito?\n\nc) A figura abaixo ilustra a planta baixa de uma casa. Uma pessoa pode andar pela casa de forma a passar por todas as portas exatamente uma vez? Se sim, como ser feito?\n\n12) Um carteiro entrega cartas na região ao lado. É possível que ele ande exatamente uma vez de cada lado de cada uma das ruas? Se sim, como? ISOMORFISMO DE GRAFOS\n\nDois gráficos G₁ = (V₁, E₁) e G₂ = (V₂, E₂) são iguais se V₁ = V₂ e E₁ = E₂.\n\nDesta forma, os gráficos a b\n G₁ e b não são iguais, dado que V(G₁) = {a,b} e V(G₂) = {b,e,b}.\n\nDois gráficos G₁ = (V₁, E₁) e G₂ = (V₂, E₂) são isomorfos se existe uma função bijetora f: V₁ → V₂ tal que {u,v} ∈ E₁ se, e somente se, {f(u),f(v)} ∈ E₂.\n\nUma função f: V₁ → V₂ que é bijetora e satisfaz (*) é chamada de isomorfismo de gráficos.\n\nA existência de um isomorfismo de grafos entre os gráficos G e H implica, portanto que G e H são iguais de menos dos nomes dos seus vértices.\n\nNa figura abaixo temos que G₄ e G₁ são isomorfos, denotado G₂ ≅ G₂, mas G₁ ≠ G₃ e G₂ ≠ G₃.\n\nObserve que para garantir que G₁ e G₃ não são isomorfos, todas as possibilidades de nomear os vértices de G₃ levam a uma contradição em (*). ISOMORFISMO DE GRAFOS - Exercícios\n1) Verifique que os grafos G_1 e G_2 abaixo são, de fato, isomorfos, e a função dada é, de fato um isomorfismo.\n\n{:\n v(G_1) -> v(G_2)\n f(1) = a\n f(2) = e\n f(3) = c\n f(4) = b\n f(5) = d\n f(6) = f\n}\n\n2) Mostre que os grafos abaixo não são isomorfos:\n\nList e todos as propriedades que H_1 e H_2 têm em comum.\n\n3) Dos grafos abaixo determine quais são isomorfos a G_1 e quais são isomorfos entre si.\n\n4) Dos grafos desta página, quais são:\n(a) bipartidos?\n(b) conexos?\n(c) eulerianos? Exercícios extras\n1. (Liu, Tao 6.1, pg 179 T18) Prove que, em um grafo de ordem n, se existe um passeio entre dois vértices, então existe um passeio de comprimento no máximo n - 1 entre eles.\n\n2. Prove que, um grafo G é conexo se e somente se em qualquer partição de V(G) em dois subconjuntos X e Y existe uma aresta com um extremo em X e outro em Y.\n\n3. Desenhe todos os grafos eulerianos de ordem 6. Quantos são? E de ordem 8? E de ordem 7?\n\n4. Existe algum grafo euleriano de ordem par e um número ímpar de arestas?\n\n5. Modele em teoria de grafos e resolva os seguintes problemas:\n(a) É possível, com a peças de um jogo de dominó, fazer um ciclo contendo todas as peças, obedecendo as regras do jogo?\n(b) É possível mover uma torre em um tabuleiro de xadrez 8 x 8 de forma que todo movimento positivo seja executado exatamente uma vez? Um movimento entre duas casas de um tabuleiro deve ser completado quando ele é feito em um turno.\n\n6. Para que valores de k o grafo k-cubo é euleriano? grafo dodecaedro\ngrafo icosaedro