docA Matemática dos Labirintos
download 
Denúncia Transcrição
A Matemática dos Labirintos
Escola de Verão de Matemática, Estatı́stica e Computação A Matemática dos Labirintos José Félix Costa1 1 Departamento de Matemática, Instituto Superior Técnico, Universidade de Lisboa 14 – 16 de julho 1/ 113 As Pontes de Königsberg 1. As Pontes de Königsberg 2/ 113 As Pontes de Königsberg Leonhard Euler 3/ 113 As Pontes de Königsberg Leonhard Euler 4/ 113 As Pontes de Königsberg Leonhard Euler 5/ 113 As Pontes de Königsberg Problema das pontes de Königsberg 6/ 113 As Pontes de Königsberg Problema das pontes de Königsberg 7/ 113 As Pontes de Königsberg Problema das pontes de Königsberg C A D B Figura: Problema das pontes de Königsberg. O problema concreto (à esquerda) é resolvido depois de interpretado por grafo modelo (à direita). 8/ 113 As Pontes de Königsberg Poema de William Thomas Tutte (1917 – 2002) Poema de homenagem a Euler Some citizens of Koenigsberg Were walking on the strand Beside the river Pregel With its seven bridges spanned. “O, Euler come and walk with us” Those burghers did beseech “We’ll walk the seven bridges o’er And pass but once by each.” “It can’t be done” then Euler cried “Here comes the Q. E. D. Your islands are but vertices, And all of odd degree.” 9/ 113 As Pontes de Königsberg Poema de William Thomas Tutte (1917 – 2002) Poema de homenagem a Euler Some citizens of Koenigsberg Were walking on the strand Beside the river Pregel With its seven bridges spanned. “O, Euler come and walk with us” Those burghers did beseech “We’ll walk the seven bridges o’er And pass but once by each.” “It can’t be done” then Euler cried “Here comes the Q. E. D. Your islands are but vertices, And all of odd degree.” 9/ 113 As Pontes de Königsberg Poema de William Thomas Tutte (1917 – 2002) Poema de homenagem a Euler Some citizens of Koenigsberg Were walking on the strand Beside the river Pregel With its seven bridges spanned. “O, Euler come and walk with us” Those burghers did beseech “We’ll walk the seven bridges o’er And pass but once by each.” “It can’t be done” then Euler cried “Here comes the Q. E. D. Your islands are but vertices, And all of odd degree.” 9/ 113 As Pontes de Königsberg Poema de William Thomas Tutte (1917 – 2002) Poema de homenagem a Euler Some citizens of Koenigsberg Were walking on the strand Beside the river Pregel With its seven bridges spanned. “O, Euler come and walk with us” Those burghers did beseech “We’ll walk the seven bridges o’er And pass but once by each.” “It can’t be done” then Euler cried “Here comes the Q. E. D. Your islands are but vertices, And all of odd degree.” 9/ 113 As Pontes de Königsberg Os teoremas de Euler Leonhard Euler, letter of April 1736 “... this type of solution bears little relationship to mathematics, and I do not understand why you expect a mathematician to produce it, rather than anyone else, for the solution is based on reason alone, and its discovery does not depend on any mathematical principle.” Leonhard Euler, letter of March 1736 “This question is so banal, but seemed to me worthy of attention in that neither geometry, nor algebra, nor even the art of counting was sufficient to solve it.” 10/ 113 As Pontes de Königsberg Os teoremas de Euler Leonhard Euler, letter of April 1736 “... this type of solution bears little relationship to mathematics, and I do not understand why you expect a mathematician to produce it, rather than anyone else, for the solution is based on reason alone, and its discovery does not depend on any mathematical principle.” Leonhard Euler, letter of March 1736 “This question is so banal, but seemed to me worthy of attention in that neither geometry, nor algebra, nor even the art of counting was sufficient to solve it.” 10/ 113 As Pontes de Königsberg Os teoremas de Euler Leonhard Euler, letter of April 1736 “... this type of solution bears little relationship to mathematics, and I do not understand why you expect a mathematician to produce it, rather than anyone else, for the solution is based on reason alone, and its discovery does not depend on any mathematical principle.” Leonhard Euler, letter of March 1736 “This question is so banal, but seemed to me worthy of attention in that neither geometry, nor algebra, nor even the art of counting was sufficient to solve it.” 10/ 113 As Pontes de Königsberg Os Teoremas de Euler Teorema (Teorema de Euler-Hierholzer) Um multigrafo G é euleriano se e só se G é conexo e todo o vértice de G é par. Teorema (Teorema de Euler-Hierholzer) Um multigrafo G é atravessável se e só se G é conexo e tem exatamente dois vértices ı́mpares. Nomeadamente, todo o atalho euleriano de G começa num dos vértices ı́mpares e termina no outro dos vértices ı́mpares. Teorema (Teorema de Euler-Hierholzer) Um multigrafo G com 2n vértices ı́mpares pode ser descrito por n atalhos disjuntos. (Note-se que o número de vértices ı́mpares é necessariamente par.) 11/ 113 As Pontes de Königsberg Os Teoremas de Euler Teorema (Teorema de Euler-Hierholzer) Um multigrafo G é euleriano se e só se G é conexo e todo o vértice de G é par. Teorema (Teorema de Euler-Hierholzer) Um multigrafo G é atravessável se e só se G é conexo e tem exatamente dois vértices ı́mpares. Nomeadamente, todo o atalho euleriano de G começa num dos vértices ı́mpares e termina no outro dos vértices ı́mpares. Teorema (Teorema de Euler-Hierholzer) Um multigrafo G com 2n vértices ı́mpares pode ser descrito por n atalhos disjuntos. (Note-se que o número de vértices ı́mpares é necessariamente par.) 11/ 113 As Pontes de Königsberg Os Teoremas de Euler Teorema (Teorema de Euler-Hierholzer) Um multigrafo G é euleriano se e só se G é conexo e todo o vértice de G é par. Teorema (Teorema de Euler-Hierholzer) Um multigrafo G é atravessável se e só se G é conexo e tem exatamente dois vértices ı́mpares. Nomeadamente, todo o atalho euleriano de G começa num dos vértices ı́mpares e termina no outro dos vértices ı́mpares. Teorema (Teorema de Euler-Hierholzer) Um multigrafo G com 2n vértices ı́mpares pode ser descrito por n atalhos disjuntos. (Note-se que o número de vértices ı́mpares é necessariamente par.) 11/ 113 As Pontes de Königsberg Os Teoremas de Euler Teorema (Teorema de Euler-Hierholzer) Um multigrafo G é euleriano se e só se G é conexo e todo o vértice de G é par. Teorema (Teorema de Euler-Hierholzer) Um multigrafo G é atravessável se e só se G é conexo e tem exatamente dois vértices ı́mpares. Nomeadamente, todo o atalho euleriano de G começa num dos vértices ı́mpares e termina no outro dos vértices ı́mpares. Teorema (Teorema de Euler-Hierholzer) Um multigrafo G com 2n vértices ı́mpares pode ser descrito por n atalhos disjuntos. (Note-se que o número de vértices ı́mpares é necessariamente par.) 11/ 113 As Pontes de Königsberg Os teoremas de Euler v0 C v1 u1 = vi u0 un v2 C1 u2 u3 u` 12/ 113 As Pontes de Königsberg Os teoremas de Euler v0 C v1 u1 = vi u0 un v2 C1 u2 u3 u` 13/ 113 As Pontes de Königsberg Os teoremas de Euler v0 C v1 u1 = vi u0 un v2 C1 u2 u3 u` 14/ 113 As Pontes de Königsberg Os teoremas de Euler v0 C v1 u1 = vi u0 un v2 C1 u2 u3 u` 15/ 113 As Pontes de Königsberg Os teoremas de Euler v0 C v1 u1 = vi u0 un v2 C1 u2 u3 u` 16/ 113 As Pontes de Königsberg Os teoremas de Euler v0 C v1 u1 = vi u0 un v2 C1 u2 u3 u` 17/ 113 As Pontes de Königsberg Os teoremas de Euler v0 C v1 u1 = vi u0 un v2 C1 u2 u3 u` 18/ 113 As Pontes de Königsberg Os teoremas de Euler v0 C v1 u1 = vi u0 un v2 C1 u2 u3 u` 19/ 113 As Pontes de Königsberg Os teoremas de Euler v0 C v1 u1 = vi u0 un v2 C1 u2 u3 u` 20/ 113 As Pontes de Königsberg Os teoremas de Euler v0 C v1 u1 = vi u0 un v2 C1 u2 u3 u` 21/ 113 As Pontes de Königsberg Os teoremas de Euler v0 C v1 u1 = vi u0 un v2 C1 u2 u3 u` 22/ 113 As Pontes de Königsberg Os teoremas de Euler v0 C v1 u1 = vi u0 un v2 C1 u2 u3 u` 23/ 113 As Pontes de Königsberg Os teoremas de Euler v0 C v1 u1 = vi u0 un v2 C1 u2 u3 u` 24/ 113 As Pontes de Königsberg Os teoremas de Euler v0 C v1 u1 = vi u0 un v2 C1 u2 u3 u` 25/ 113 As Pontes de Königsberg Os teoremas de Euler v0 C v1 u1 = vi u0 un v2 C1 u2 u3 u` 26/ 113 As Pontes de Königsberg Os teoremas de Euler v0 C v1 u1 = vi u0 un v2 C1 u2 u3 u` 27/ 113 As Pontes de Königsberg Os teoremas de Euler v0 C v1 u1 = vi u0 un v2 C1 u2 u3 u` 28/ 113 As Pontes de Königsberg As pontes do rio Madison 29/ 113 Plantas e Redes 2. Plantas e Redes 30/ 113 Plantas e Redes Plantas, vide [Cha85] D E A B C R D E A B C R 31/ 113 Plantas e Redes Plantas, vide [Cha85] D E A B C R D E A B C R 32/ 113 Plantas e Redes Plantas, vide [Cha85] A B D C E F R 33/ 113 Plantas e Redes Plantas, vide [Cha85] A A 1 B 2 R 1 D 2 C E R F B 1 2 C E F D 34/ 113 Plantas e Redes Plantas R1 R2 R3 R4 R5 R6 R7 R8 R9 35/ 113 Plantas e Redes Plantas R1 R2 R3 R4 R5 R6 R7 R8 R9 36/ 113 Plantas e Redes Plantas R1 R2 R3 R4 R5 R6 R7 R8 R9 37/ 113 Plantas e Redes Plantas R1 R2 R3 R4 R5 R6 R7 R8 R9 38/ 113 Plantas e Redes Plantas R1 R2 R3 R4 R5 R6 R7 R8 R9 39/ 113 Plantas e Redes Plantas R1 R2 R3 R4 R5 R6 R7 R8 R9 40/ 113 Plantas e Redes Plantas R1 R2 R3 R4 R5 R6 R7 R8 R9 41/ 113 Plantas e Redes Plantas R1 R2 R3 R4 R5 R6 R7 R8 R9 42/ 113 Plantas e Redes Plantas R1 R2 R3 R4 R5 R6 R7 R8 R9 43/ 113 Plantas e Redes Plantas R1 R2 R3 R4 R5 R6 R7 R8 R9 44/ 113 Plantas e Redes Plantas R1 R2 R3 R4 R5 R6 R7 R8 R9 45/ 113 Plantas e Redes Plantas R1 R2 R3 R4 R5 R6 R7 R8 R9 46/ 113 Plantas e Redes Plantas R1 R2 R3 R4 R5 R6 R7 R8 R9 47/ 113 Plantas e Redes “Doodleling” Casa do Pai Natal Quais das seguintes figuras podem ser desenhadas sem levantar a caneta do papel, iniciando o desenho num dos vértices e sem repetir arestas? 48/ 113 Plantas e Redes “Doodleling” 49/ 113 Plantas e Redes Casa do Pai Natal 50/ 113 Plantas e Redes Casa do Pai Natal 51/ 113 Plantas e Redes Casa do Pai Natal 52/ 113 Plantas e Redes Casa do Pai Natal 53/ 113 Plantas e Redes Casa do Pai Natal 54/ 113 Plantas e Redes Casa do Pai Natal 55/ 113 Plantas e Redes Casa do Pai Natal 56/ 113 Plantas e Redes Casa do Pai Natal 57/ 113 Plantas e Redes Casa do Pai Natal 58/ 113 Plantas e Redes Casa do Pai Natal 59/ 113 Plantas e Redes Casa do Pai Natal 60/ 113 Plantas e Redes Casa do Pai Natal 61/ 113 Plantas e Redes Casa do Pai Natal 62/ 113 Plantas e Redes “Doodling a lot”: Pitágoras, Maomé e Tutte (vide [BC87]) 63/ 113 Plantas e Redes Quantas vezes é necessário levantar a caneta do papel? (Vide [BC87]) 64/ 113 Labirintos 2. Labirintos 65/ 113 Labirintos Catedral de Notre Dame d’Amiens 66/ 113 Labirintos Catedral de Notre Dame d’Amiens 67/ 113 Labirintos Catedral de Notre Dame de Chartres 68/ 113 Labirintos Labirinto de Hever Castle 69/ 113 Labirintos Labirinto de New Hampton 70/ 113 Labirintos Labirinto de Wiltshire (Somerset) 71/ 113 Labirintos Labirinto de Reignac sur Indre (França) 72/ 113 Labirintos Labirinto de New Hampton 73/ 113 Labirintos Labirinto de New Hampton (vide [BLW06]) 74/ 113 O Labirinto de Dédalo 4. O Labirinto de Dédalo 75/ 113 O Labirinto de Dédalo O labirinto de Dédalo 76/ 113 O Labirinto de Dédalo O Labirinto de Dédalo 77/ 113 O Labirinto de Dédalo O labirinto de Dédalo 78/ 113 O Labirinto de Dédalo Labirinto de Creta 79/ 113 O Labirinto de Dédalo O labirinto de Dédalo 80/ 113 O Labirinto de Dédalo O labirinto de Dédalo 81/ 113 O Labirinto de Dédalo O labirinto de Dédalo 82/ 113 O Labirinto de Dédalo O labirinto de Dédalo 83/ 113 O Labirinto de Dédalo O labirinto de Dédalo 84/ 113 O Labirinto de Dédalo O labirinto de Dédalo na Eneida de Virgı́lio Eneida, Livro V, trad. João Franco Barreto Como já na alta Creta o monstruoso Labirinto se diz teve tecido Um caminho tão cego, e portentoso, Com outros mil caminhos dividido; Que era assaz intrincado e duvidoso Error, e tão confuso e incompreendido, Que aos que entravam nele era impossı́vel Sair daquela confusão terrı́vel: 85/ 113 O Labirinto de Dédalo Labirinto da Quinta da Regaleira em Sintra 86/ 113 O Labirinto de Dédalo O labirinto de Dédalo nas Metamorfoses de Ovı́dio Metamorfoses, Livro VIII, trad. Paulo Farmhouse Alberto Celebérrimo pelo seu talento na arte da arquitetura, Dédalo encarrega-se da obra, baralha os sinais e faz o olhar enganar-se em retorcidas curvas e contracurvas de corredores sem conta. Tal como na Frı́gia o Meandro nas lı́mpidas águas se diverte fluindo e refluindo num deslizar que confunde, e, correndo ao encontro de si próprio, contempla a água que há-de vir, e, voltando-se ora para nascente, ora para o mar aberto, empurra a sua corrente sem rumo certo, assim enche Dédalo os inumeráveis corredores de equı́vocos. A custo ele próprio logrou voltar à entrada: de tal modo enganador era o edifı́cio. 87/ 113 O Labirinto de Dédalo Labirinto de Avaris 88/ 113 O Labirinto de Dédalo Labirinto romano 89/ 113 O Labirinto de Dédalo Labirinto romano 90/ 113 O Labirinto de Dédalo Labirinto moderno (vide [BC87]) 91/ 113 O Labirinto de Dédalo Pesquisa em profundidade Pesquisa em profundidade Seja G um grafo conexo e v0 um vértice de G. A árvore de cobertura de G obtida por pesquisa em profundidade constrói-se da seguinte maneira: 1 Toma-se u = v0 como vértice corrente da pesquisa e n = 0. T0 é a árvore que contém somente o vértice v0 . 2 Escolhe-se, caso exista, um vértice vn+1 ainda não incluı́do em Tn adjacente a u; toma-se para Tn+1 a árvore que expande Tn com a nova aresta vn vn+1 ; toma-se u := vn+1 e n := n + 1. 3 Repete-se o passo 2 até que o vértice corrente u não seja adjacente a nenhum vértice de G ainda não visitado. Se a árvore obtida Tn cobre todo o grafo, então a pesquisa termina; se não, retrocede-se para o vértice corrente anterior, i.e. toma-se u = vn−1 e n := n + 1; repete-se o passo 2. 92/ 113 O Labirinto de Dédalo Pesquisa em profundidade v0 93/ 113 O Labirinto de Dédalo Pesquisa em profundidade v0 e0 v1 94/ 113 O Labirinto de Dédalo Pesquisa em profundidade v2 e2 v3 e1 v0 e0 v1 95/ 113 O Labirinto de Dédalo Pesquisa em profundidade v4 e4 v6 e5 v5 e3 v2 e2 v3 e1 v0 e0 v1 e6 v7 96/ 113 O Labirinto de Dédalo Pesquisa em profundidade v4 e4 v6 e5 e6 v5 e3 v2 e2 v3 e1 v0 e0 v1 e7 v7 v8 e8 v9 97/ 113 O Labirinto de Dédalo Pesquisa em profundidade v4 e3 e4 v6 e5 e6 e2 v3 e1 v5 v0 e0 v1 e7 v7 v8 e8 v9 v2 v12 e9 v10 e11 e10 v11 98/ 113 O Labirinto de Dédalo Pesquisa em profundidade v4 e3 e4 v6 e5 e6 e2 v3 e1 v5 v0 e0 v1 e7 v7 v8 e8 v9 v2 v13 e9 v10 e12 e10 v12 e11 v11 99/ 113 O Labirinto de Dédalo Pesquisa em largura Pesquisa em largura Seja G um grafo conexo e v0 um vértice de G. A árvore de cobertura de G obtida por pesquisa em largura constrói-se da seguinte maneira: 1 Toma-se u = v0 como vértice corrente da pesquisa, n = 0 e m = 1. T0 é a árvore que contém somente o vértice v0 . 2 Escolhe-se, caso exista, um vértice vn+1 ainda não incluı́do em Tn adjacente a u; toma-se para Tn+1 a árvore que expande Tn com a nova aresta vn vn+1 ; toma-se n := n + 1. 3 Repete-se o passo 2 até que não existam mais vértices não visitados adjacentes a u. Se a árvore obtida Tn cobre já todo o grafo, então a pesquisa termina; se não, toma-se o primeiro dos vértices vm que ainda não foi vértice corrente e toma-se m := m + 1; repete-se o passo 2. 100/ 113 O Labirinto de Dédalo Pesquisa em largura v0 101/ 113 O Labirinto de Dédalo Pesquisa em largura v3 e2 v4 e3 v0 v2 e1 e0 v1 e4 v5 102/ 113 O Labirinto de Dédalo Pesquisa em largura v6 e5 v3 e2 v4 e3 v0 v2 e1 e0 v1 e4 v5 103/ 113 O Labirinto de Dédalo Pesquisa em largura v6 e5 v3 e2 v7 e6 v4 e7 v8 e3 v0 v2 e1 e0 v1 e4 v5 104/ 113 O Labirinto de Dédalo Pesquisa em largura v6 e5 v3 e2 v7 e6 v4 e7 v8 e3 v0 v2 e1 e0 v1 e4 v5 e8 v9 105/ 113 O Labirinto de Dédalo Pesquisa em largura v6 e5 v3 e2 v7 e9 v10 e6 v4 e7 v8 e3 v0 v2 e1 e0 v1 e4 v5 e8 v9 106/ 113 O Labirinto de Dédalo Pesquisa em largura v6 e5 v3 e2 v7 e6 e9 v10 e7 v8 e10 v11 v4 e11 v12 e3 v0 v2 e1 e0 v1 e4 v5 e8 v9 107/ 113 O Labirinto de Dédalo Pesquisa em largura v6 e5 v3 e2 v7 e6 e9 v10 e7 v8 e10 v11 v4 e11 v12 e3 v0 v2 e1 e0 v1 e4 v5 e8 v13 e12 v9 108/ 113 O Labirinto de Dédalo Labirinto de Gopal S R K J D A U T L M E N P Q G F C H B 109/ 113 O Labirinto de Dédalo Labirinto de Gopal K R S U Q L J D M T G P A F E N C H B 110/ 113 O Labirinto de Dédalo Algoritmo dos labirintos Algoritmo dos labirintos 1 Sempre que chegar a um vértice não visitado, siga pela aresta ainda não percorrida nele incidente que lhe aprouver; 2 Sempre que, por aresta ainda não percorrida, chegar a vértice já visitado ou a vértice de grau 1 (beco sem saı́da), recue pela mesma aresta até ao vértice precedente; 3 Sempre que por aresta já percorrida chegar a vértice já visitado, siga por nova aresta, se esta existir; 4 Uma aresta já percorrida duas vezes não pode mais ser mais usada. 111/ 113 O Labirinto de Dédalo O tema do labirinto na poesia (vide compilação em [Fer08]) Miguel Torga, Diário VII Perdi-me nos teus braços, alamedas Onde o tempo caminha e descaminha. Pus a força que tinha Na instintiva defesa De encontrar a saı́da, a liberdade. Mas agora Teseu era um poeta, E Ariane a poesia, o labirinto. Desajudado, Só me resta cantar, deixar marcado O pânico que sinto. 112/ 113 O Labirinto de Dédalo Bibliography I [BC87] W. W. Rouse Ball and H. S. M. Coxeter. Mathematical Recreations and Essays. Dover Publications, Inc., New York, thirteenth edition, 1892, 1974, 1987. [BLW06] N. L. Biggs, E. K. Lloyd, and R. J. Wilson. Graph Theory 1736–1936. Clarendon Press, Oxford, 1976, 1986, 2006. [Cha85] Garry Chartrand. Introduction to Graph Theory. Dover Publications, Inc., New York, 1977, 1985. [Fer08] José Ribeiro Ferreira. Labirinto e Minotauro, Mito de Ontem e de Hoje. UI&D Centro de Estudos Clássicos e Humanísticos da Universidade de Coimbra, 2008. 113/ 113
