{"id":1398,"date":"2020-03-20T10:33:28","date_gmt":"2020-03-20T13:33:28","guid":{"rendered":"https:\/\/www.blogs.unicamp.br\/zero\/?p=1398"},"modified":"2023-08-25T12:38:24","modified_gmt":"2023-08-25T15:38:24","slug":"pontes-de-konigsberg-destrui-las-e-a-solucao","status":"publish","type":"post","link":"https:\/\/www.blogs.unicamp.br\/zero\/1398\/","title":{"rendered":"Pontes de K\u00f6nigsberg: destru\u00ed-las \u00e9 a solu\u00e7\u00e3o"},"content":{"rendered":"\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t\t
\n\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t

(Translate)<\/a><\/h4>\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t\t
\n\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\t

As \u201cSete Pontes de K\u00f6nigsberg\u201d \u00e9 um problema historicamente not\u00e1vel em matem\u00e1tica:<\/p>

Na cidade de K\u00f6nigsberg temos uma curiosa regi\u00e3o com 4 \u00e1reas de terra firme (uma acima, uma abaixo e duas no meio) conectadas por 7 pontes como apresentada na figura abaixo.<\/i><\/p>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t

\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\"\"\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\t

Eis a conjectura:<\/p>

\u00c9 poss\u00edvel partir de uma das 4 \u00e1reas de terra firme, passar pelas 7 pontes retornando para a \u00e1rea inicial.<\/i><\/p>

Detalhes t\u00e9cnicos:<\/p>

1.<\/b> N\u00e3o vale sair desta regi\u00e3o do mapa;<\/p>

2.<\/b> N\u00e3o vale atravessar uma mesma ponte mais do que uma vez;<\/p>

3. <\/b>\u00c9 permitido cruzar o rio somente passando pelas pontes.<\/p>

Pense um pouco neste problema antes de discutirmos a resolu\u00e7\u00e3o. Lembre-se que conjecturas s\u00e3o afirma\u00e7\u00f5es que ainda n\u00e3o foram provadas nem como verdadeiras (no caso seriam teoremas) e nem como falsas (ou seja, refutada).<\/p>

Agora que voc\u00ea j\u00e1 pensou um pouco sobre este problema, saiba que o grande matem\u00e1tico Leonhard Euler passou por este mesmo dilema em 1736. Como resultado de sua an\u00e1lise chegou a uma resolu\u00e7\u00e3o que refuta esta conjectura (ou seja, passar pelas Sete Pontes de K\u00f6nigsberg e retornar \u00e0 posi\u00e7\u00e3o original \u00e9 imposs\u00edvel). Para isto, Euler prop\u00f4s o problema no seguinte modelo simplificado, no qual cada c\u00edrculo representa uma \u00e1rea de terra firme e cada linha representa uma ponte.<\/p>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t

\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\"\"\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\t

Para entendermos o argumento de Euler, chamemos de v\u00e9rtice cada \u00e1rea de terra firme e de aresta cada ponte. Assim, na representa\u00e7\u00e3o acima podemos perceber que todos os v\u00e9rtices est\u00e3o conectados por um n\u00famero \u00edmpar de arestas. Isso significa que se houvesse solu\u00e7\u00e3o, ela deveria partir de um v\u00e9rtice qualquer e passar pelas arestas que o conectam. Mas cada vez que ele passa por uma aresta conectada a este v\u00e9rtice, temos a seguinte situa\u00e7\u00e3o:<\/p>

1. <\/b>Se est\u00e1vamos no v\u00e9rtice, ent\u00e3o sa\u00edmos dele;<\/p>

2. <\/b>Se n\u00e3o est\u00e1vamos no v\u00e9rtice, ent\u00e3o entramos nele.<\/p>

Como sa\u00edmos de um v\u00e9rtice, temos que se o n\u00famero de vezes que passamos por arestas conectadas ao v\u00e9rtice for \u00edmpar, ent\u00e3o terminaremos fora deste v\u00e9rtice. Por outro lado, se o n\u00famero de vezes que passamos por arestas conectadas ao v\u00e9rtice for par, voltamos a este v\u00e9rtice.<\/p>

Observe ent\u00e3o que no problema proposto para as Pontes de K\u00f6nigsberg, todos os v\u00e9rtices possuem um n\u00famero \u00edmpar de arestas, e o problema pede que comece e termine no mesmo v\u00e9rtice. Desse modo, se passamos por todas as arestas, ent\u00e3o passamos por uma quantidade \u00edmpar de arestas conectadas \u00e0quele v\u00e9rtice, logo devemos estar fora do v\u00e9rtice. Com isto, temos demonstrado que n\u00e3o existe solu\u00e7\u00e3o para este problema.<\/p>

No caso, caminhos que viabilizam sair de um v\u00e9rtice, percorrer todas as arestas apenas uma vez cada e retornar para o v\u00e9rtice original, s\u00e3o chamados de grafos eulerianos. Um teorema que sucede desse conceito \u00e9 o seguinte:<\/p>

Um grafo ser\u00e1 euleriano se ele for conexo e todos os seus v\u00e9rtices tiverem um n\u00famero par de arestas conectadas a ele.<\/i><\/p>

Podemos entender a raz\u00e3o de terem um n\u00famero par de arestas, pois se passamos pelas arestas de um v\u00e9rtice um n\u00famero par de vezes, e n\u00e3o come\u00e7amos naquele v\u00e9rtice, ent\u00e3o terminaremos fora daquele v\u00e9rtice.<\/p>

Desse modo, para o famoso problema das \u201cSete Pontes de K\u00f6nigsberg\u201d n\u00e3o achar uma solu\u00e7\u00e3o \u00e9 diferente de provar que ela n\u00e3o existe. Mas como ela forma um grafo que n\u00e3o \u00e9 euleriano, ent\u00e3o de fato sua solu\u00e7\u00e3o n\u00e3o existe. Mas o que dizer de algumas varia\u00e7\u00f5es mais ca\u00f3ticas? Se por acaso destruirmos uma ou mais pontes, teremos solu\u00e7\u00e3o? A seguir analisaremos as varia\u00e7\u00f5es do problema destruindo suas pontes (ignorando varia\u00e7\u00f5es de simetria ou de permuta\u00e7\u00e3o por v\u00e9rtices isolados).<\/p>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t

\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\"\"\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\t

6-A.<\/b> N\u00e3o tem solu\u00e7\u00e3o, pois os v\u00e9rtices 2 e 3 possuem um n\u00famero \u00edmpar de arestas.<\/p>

6-B. <\/b>N\u00e3o tem solu\u00e7\u00e3o, pois os v\u00e9rtices 3 e 4 possuem um n\u00famero \u00edmpar de arestas.<\/p>

6-C.<\/b> N\u00e3o tem solu\u00e7\u00e3o, pois os v\u00e9rtices 1 e 3 possuem um n\u00famero \u00edmpar de arestas.<\/p>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t

\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\"\"\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\t

5-A. <\/b>N\u00e3o tem solu\u00e7\u00e3o, pois todos os v\u00e9rtices possuem um n\u00famero \u00edmpar de arestas.<\/p>

5-B. <\/b>N\u00e3o tem solu\u00e7\u00e3o, pois os v\u00e9rtices 3 e 4 possuem um n\u00famero \u00edmpar de arestas.<\/p>

5-C.<\/b> N\u00e3o tem solu\u00e7\u00e3o, pois os v\u00e9rtices 2 e 4 possuem um n\u00famero \u00edmpar de arestas.<\/p>

5-D. <\/b>N\u00e3o tem solu\u00e7\u00e3o, pois os v\u00e9rtices 1 e 3 possuem um n\u00famero \u00edmpar de arestas.<\/p>

5-E. <\/b>Tem solu\u00e7\u00e3o! Comece do v\u00e9rtice 1, v\u00e1 para o v\u00e9rtice 4, depois para o v\u00e9rtice 3, depois para o v\u00e9rtice 2, depois para o v\u00e9rtice 4, volte para o v\u00e9rtice 1.<\/p>

5-F. <\/b>N\u00e3o tem solu\u00e7\u00e3o, pois os v\u00e9rtices 2 e 3 possuem um n\u00famero \u00edmpar de arestas.<\/p>

5-G. <\/b>N\u00e3o tem solu\u00e7\u00e3o, pois os v\u00e9rtices 2 e 4 possuem um n\u00famero \u00edmpar de arestas.<\/p>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t

\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\"\"\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\t

4-A.<\/b> N\u00e3o tem solu\u00e7\u00e3o, pois os v\u00e9rtices 1 e 2 possuem um n\u00famero \u00edmpar de arestas.<\/p>

4-B.<\/b> N\u00e3o tem solu\u00e7\u00e3o, pois os v\u00e9rtices 1 e 4 possuem um n\u00famero \u00edmpar de arestas.<\/p>

4-C.<\/b> N\u00e3o tem solu\u00e7\u00e3o, pois os v\u00e9rtices 1 e 3 possuem um n\u00famero \u00edmpar de arestas.<\/p>

4-D. <\/b>Tem solu\u00e7\u00e3o! Comece do v\u00e9rtice 1, v\u00e1 para o v\u00e9rtice 2, depois para o v\u00e9rtice 3, depois para o v\u00e9rtice 4, volte para o v\u00e9rtice 1.<\/p>

4-E.<\/b> N\u00e3o tem solu\u00e7\u00e3o, pois os v\u00e9rtices 3 e 4 possuem um n\u00famero \u00edmpar de arestas.<\/p>

4-F. <\/b>Tem solu\u00e7\u00e3o! Comece do v\u00e9rtice 1, v\u00e1 para o v\u00e9rtice 4, depois para o v\u00e9rtice 3, depois para o v\u00e9rtice 4, volte para o v\u00e9rtice 1.<\/p>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t

\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\"\"\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\t

3-A.<\/b> N\u00e3o tem solu\u00e7\u00e3o, pois todos os v\u00e9rtices possuem um n\u00famero \u00edmpar de arestas.<\/p>

3-B.<\/b> N\u00e3o tem solu\u00e7\u00e3o, pois o v\u00e9rtice 2 possui um n\u00famero \u00edmpar de arestas.<\/p>

3-C.<\/b> N\u00e3o tem solu\u00e7\u00e3o, pois os v\u00e9rtices 3 e 4 possuem um n\u00famero \u00edmpar de arestas.<\/p>

3-D.<\/b> Tem solu\u00e7\u00e3o! Comece do v\u00e9rtice 1, v\u00e1 para o v\u00e9rtice 2, depois para o v\u00e9rtice 4, volte para o v\u00e9rtice 1.<\/p>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t

\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\"\"\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\t

2-A.<\/b> Tem solu\u00e7\u00e3o! Comece do v\u00e9rtice 4, v\u00e1 para o v\u00e9rtice 3, volte para o v\u00e9rtice 4.<\/p>

2-B.<\/b> N\u00e3o tem solu\u00e7\u00e3o, pois os v\u00e9rtices 1 e 3 possuem um n\u00famero \u00edmpar de arestas.<\/p>

O caso com 1 ponte \u00e9 desnecess\u00e1rio, pois se apenas existe uma aresta, haver\u00e1 um v\u00e9rtice com um n\u00famero \u00edmpar de arestas (no caso, 1).<\/p>

O caso com 0 pontes \u00e9 trivial, pois se n\u00e3o h\u00e1 pontes para atravessar, j\u00e1 come\u00e7amos no v\u00e9rtice que satisfaz o problema.<\/p>

Com isto podemos concluir que destruindo de duas a cinco pontes (ou todas) o problema insol\u00favel pode suportar solu\u00e7\u00f5es, ou seja, eliminando algumas arestas espec\u00edficas podemos transformar o grafo original em grafos eulerianos.<\/p>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t

\n\t\t\t\t\t\t
\n\t\t\t\t\t
\n\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t

Voltar para p\u00e1gina principal<\/a><\/h4>\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t\t
\n\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t

Quem escreve os posts?<\/a><\/h4>\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<\/div>\n\t\t","protected":false},"excerpt":{"rendered":"

Euler mostra que o problema das sete pontes n\u00e3o tem solu\u00e7\u00e3o, mas e se destru\u00edrmos algumas delas?<\/p>\n","protected":false},"author":434,"featured_media":1418,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"colormag_page_container_layout":"default_layout","colormag_page_sidebar_layout":"default_layout","_monsterinsights_skip_tracking":false,"_monsterinsights_sitenote_active":false,"_monsterinsights_sitenote_note":"","_monsterinsights_sitenote_category":0,"pgc_sgb_lightbox_settings":"","_vp_format_video_url":"","_vp_image_focal_point":[],"footnotes":""},"categories":[1210],"tags":[],"class_list":["post-1398","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-v-3-ed-1"],"jetpack_featured_media_url":"https:\/\/www.blogs.unicamp.br\/zero\/wp-content\/uploads\/sites\/187\/2020\/03\/capa-2.png","_links":{"self":[{"href":"https:\/\/www.blogs.unicamp.br\/zero\/wp-json\/wp\/v2\/posts\/1398","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.blogs.unicamp.br\/zero\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.blogs.unicamp.br\/zero\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.blogs.unicamp.br\/zero\/wp-json\/wp\/v2\/users\/434"}],"replies":[{"embeddable":true,"href":"https:\/\/www.blogs.unicamp.br\/zero\/wp-json\/wp\/v2\/comments?post=1398"}],"version-history":[{"count":21,"href":"https:\/\/www.blogs.unicamp.br\/zero\/wp-json\/wp\/v2\/posts\/1398\/revisions"}],"predecessor-version":[{"id":5233,"href":"https:\/\/www.blogs.unicamp.br\/zero\/wp-json\/wp\/v2\/posts\/1398\/revisions\/5233"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.blogs.unicamp.br\/zero\/wp-json\/wp\/v2\/media\/1418"}],"wp:attachment":[{"href":"https:\/\/www.blogs.unicamp.br\/zero\/wp-json\/wp\/v2\/media?parent=1398"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.blogs.unicamp.br\/zero\/wp-json\/wp\/v2\/categories?post=1398"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.blogs.unicamp.br\/zero\/wp-json\/wp\/v2\/tags?post=1398"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}