{"id":10071,"date":"2023-06-22T08:00:46","date_gmt":"2023-06-22T11:00:46","guid":{"rendered":"https:\/\/www3.unicentro.br\/petfisica\/?p=10071"},"modified":"2023-06-22T17:02:07","modified_gmt":"2023-06-22T20:02:07","slug":"teoria-dos-grafos","status":"publish","type":"post","link":"https:\/\/www3.unicentro.br\/petfisica\/2023\/06\/22\/teoria-dos-grafos\/","title":{"rendered":"Teoria dos Grafos"},"content":{"rendered":"

[vc_row][vc_column][vc_column_text]<\/p>\n

\u00a0 \u00a0No s\u00e9culo XVIII moradores de K\u00f6nigsberg, se desafiaram com o seguinte problema: como seria poss\u00edvel dar um passeio pela cidade, passando apenas uma vez por cada uma das sete pontes que ligavam a regi\u00e3o. Essa cidade tinha duas ilhas, com sete pontes ligando quatro por\u00e7\u00f5es de terra. Uma por\u00e7\u00e3o era conectada por cinco pontes e as demais eram conectadas por tr\u00eas pontes[1].<\/span><\/p>\n

\u00a0 \u00a0Esse enigma foi solucionado por Leonhard Euler. Ele provou de forma matem\u00e1tica que era imposs\u00edvel dar o passeio a p\u00e9 passando apenas uma vez por cada uma das pontes. Sua solu\u00e7\u00e3o pode ser vista como um diagrama que tem quatro pontos representando as por\u00e7\u00f5es de terra e sete liga\u00e7\u00f5es representando as pontes[1][2].<\/span><\/p>\n

Representa\u00e7\u00e3o do m\u00e9todo<\/strong><\/span><\/span><\/span><\/p>\n

Fonte: Wikipedia – Graph Theory<\/span><\/p>\n

\u00a0 \u00a0Nesse modelo podemos chamar cada ponto de v\u00e9rtice, cada liga\u00e7\u00e3o entre os pontos de aresta, dessa forma racioc\u00ednio foi: para visitar um v\u00e9rtice \u00e9 preciso de duas arestas, uma para entrar e outra para sair, isso significa que cada v\u00e9rtice diferente do in\u00edcio e fim precisaria ter um n\u00famero par de arestas, o que n\u00e3o \u00e9 o caso, j\u00e1 que todos os cinco v\u00e9rtices tem um n\u00famero \u00edmpar de arestas.<\/span><\/p>\n

\u00a0 \u00a0O nome da representa\u00e7\u00e3o feita por Euler \u00e9 denominado atualmente como Grafo. Um grafo G= (V, E)<\/em> \u00e9 um conjunto de v\u00e9rtices V<\/em> e arestas E<\/em>. O racioc\u00ednio descrito por Euler tem imensa import\u00e2ncia, pois atrav\u00e9s dele diversos outros problemas envolvendo esse tipo de representa\u00e7\u00e3o puderam ser solucionados[3].<\/span><\/p>\n

\u00a0 \u00a0Pode-se representar com grafos in\u00fameras coisas do mundo real, desde uma sequ\u00eancia de DNA, at\u00e9 a representa\u00e7\u00e3o de malha vi\u00e1ria, para fazer essas representa\u00e7\u00f5es podemos tamb\u00e9m utilizar grafos com arestas direcionadas [4].\u00a0<\/span><\/p>\n

\u00a0 \u00a0Um exemplo seria sua aplica\u00e7\u00e3o em redes sociais: Alice\u00a0 tem uma conta no Instagram, cada perfil nessa rede social \u00e9 um v\u00e9rtice.\u00a0 Alice \u00e9 uma pessoa que tem v\u00e1rios seguidores, B\u00e1rbara \u00e9 um de seus seguidores, podemos representar essa situa\u00e7\u00e3o como A\u2192B, ou seja, um perfil A segue o perfil B, em grafos podemos dizer que B \u00e9 adjacente de A. Dentre esses seguidores Malu segue de volta alguns, o que em teoria dos Grafos pode ser representado da seguinte forma: A\u2194B, agora temos uma seta indo e voltando.<\/span><\/p>\n

\u00a0 \u00a0A partir do modelo desenvolvido por Euler, foi poss\u00edvel solucionar v\u00e1rios problemas pr\u00e1ticos em diversas \u00e1reas: matem\u00e1tica, engenharias, computa\u00e7\u00e3o, etc.<\/span><\/p>\n

\u00a0 Sem os estudos nessa \u00e1rea de grafos est\u00e1 mundo presente no mundo atual. Na \u00e1rea de computa\u00e7\u00e3o foram desenvolvidos diversos algoritmos capazes de solucionar alguns problemas, entre esses, um dos mais difundidos \u00e9 o algoritmo de Dijkstra. Publicado em 1959, um artigo onde apresentava seu algoritmo capaz de encontrar o menor caminho entre dois pontos de um grafo.<\/span><\/p>\n

\u00a0 \u00a0O algoritmo desenvolvido por Dijkstra \u00e9 aplicado massivamente. Voc\u00ea j\u00e1 pediu um carro por aplicativo? Pois bem, o c\u00e1lculo da rota do motorista at\u00e9 voc\u00ea usa esse algoritmo. Voc\u00ea fez uma pesquisa na internet? Isso tamb\u00e9m usou esse algoritmo. Contudo existem muitos outros outros algoritmos aplicados em grafos<\/span>.<\/p>\n

Autor: <\/strong>Yorranan Costa.<\/span><\/p>\n

Refer\u00eancias.<\/span><\/p>\n

[1] Rede Globo. Entenda o enigma das pontes de K\u00f6nigsberg que instigou a geometria<\/strong>. 2011. Dispon\u00edvel em: http:\/\/redeglobo.globo.com\/globociencia\/noticia\/2011\/12\/entenda-o-enigma-das-pontes-de-konigsberg-que-instigou-geometria.html. Acesso em 22 de maio de 2023.<\/span><\/p>\n

[2] Wiki Computa\u00e7\u00e3o. Teoria dos Grafos<\/strong>. UTFPR. 2022. Dispon\u00edvel em: https:\/\/wiki.inf.ufpr.br\/computacao\/doku.php?id=t:teoria_dos_grafos. Acesso em: 21 de maio de 2023<\/span><\/p>\n

[3]WAKABAYASHI, Y; KOHAYAKAWA, Y; FEOFILOFF, P. Teoria dos Grafos<\/strong>. S\u00e3o Paulo: SBM, 2000. Dispon\u00edvel em: https:\/\/www.ime.usp.br\/~yw\/publications\/books\/TeoriaDosGrafos.pdf. Acesso em: 22 maio 2023.<\/span><\/p>\n

[4] AKITA, F\u00e1bio. Desbloqueando o “Algoritmo” do Twitter – Introdu\u00e7\u00e3o a Grafos<\/strong>. 2023. Dispon\u00edvel em: https:\/\/www.youtube.com\/watch?v=uIflMYQnp8A. Acesso em: 22 de abril de 2023<\/span><\/p>\n

[\/vc_column_text][\/vc_column][\/vc_row][vc_row][vc_column][vc_facebook][\/v<\/span>c_column][\/vc_row]<\/p>\n<\/div>","protected":false},"excerpt":{"rendered":"

[vc_row][vc_column][vc_column_text] \u00a0 \u00a0No s\u00e9culo XVIII moradores de K\u00f6nigsberg, se desafiaram com o seguinte problema: como seria poss\u00edvel dar um passeio pela cidade, passando apenas uma vez por cada uma das sete pontes que ligavam a regi\u00e3o. Essa cidade tinha duas ilhas, com sete pontes ligando quatro por\u00e7\u00f5es de terra. Uma por\u00e7\u00e3o era conectada por cinco […]<\/p>\n","protected":false},"author":550,"featured_media":10073,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_exactmetrics_skip_tracking":false,"_exactmetrics_sitenote_active":false,"_exactmetrics_sitenote_note":"","_exactmetrics_sitenote_category":0,"footnotes":"","_links_to":"","_links_to_target":""},"categories":[4],"tags":[1418,1425,1424],"class_list":["post-10071","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-geral","tag-blog-2023","tag-ciencia-da-computacao","tag-yorranan-alvez-de-almeida-costa"],"_links":{"self":[{"href":"https:\/\/www3.unicentro.br\/petfisica\/wp-json\/wp\/v2\/posts\/10071","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www3.unicentro.br\/petfisica\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www3.unicentro.br\/petfisica\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www3.unicentro.br\/petfisica\/wp-json\/wp\/v2\/users\/550"}],"replies":[{"embeddable":true,"href":"https:\/\/www3.unicentro.br\/petfisica\/wp-json\/wp\/v2\/comments?post=10071"}],"version-history":[{"count":0,"href":"https:\/\/www3.unicentro.br\/petfisica\/wp-json\/wp\/v2\/posts\/10071\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www3.unicentro.br\/petfisica\/wp-json\/wp\/v2\/media\/10073"}],"wp:attachment":[{"href":"https:\/\/www3.unicentro.br\/petfisica\/wp-json\/wp\/v2\/media?parent=10071"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www3.unicentro.br\/petfisica\/wp-json\/wp\/v2\/categories?post=10071"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www3.unicentro.br\/petfisica\/wp-json\/wp\/v2\/tags?post=10071"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}