univesp_labirinto-grafos

Prévia do material em texto

A TEORIA DOS GRAFOS
 
A solução proposta por Euler 
Após jogar O Labirinto de Konigsberg, você deve ter notado que é 
impossível atravessar todas as pontes do Rio Prega sem passar duas 
vezes pela mesma ponte, retornando ao ponto de partida. Euler 
percebeu isso e, além de provar que era impossível, tornou o problema 
das pontes de Konigsberg também um marco na Teoria dos Grafos. 
Vamos entender um pouco mais sobre ela?
Afinal, o que é um grafo?
Grafos são definidos como estruturas matemáticas que permitem 
codificar a relação entre pares de objetos, na qual os objetos são 
chamados de vértices e as relações são as arestas. No enigma de 
Konigsberg, os vértices são as ilhas e as margens, enquanto as arestas 
são as pontes.
As pontes de Konigsberg e sua representação em grafo.
Para que um grafo fique bem definido, temos, então, que ter dois 
conjuntos: 
• O conjunto V, dos vértices. 
• O conjunto A, das arestas.
São exemplos de grafos:
Exemplos de grafos.
Quem contribuiu notoriamente com a definição dos grafos foi Leonhard 
Euler (1707-1783), grande matemático suíço e autor do primeiro 
artigo sobre o tema. O texto de Euler surgiu a partir da análise de um 
complexo famoso da cidade de Konigsberg. 
Por volta do século XVI, esse complexo era formado por duas ilhas 
que continham sete pontes. As pessoas que por ali passeavam se 
questionavam se seria possível caminhar pelo complexo sem a 
necessidade de repetir as pontes. Foi então que Euler desenhou o 
primeiro grafo. Após a análise do desenho, ele percebeu que seria 
impossível fazer o passeio sem repetir alguma ponte; assim, o grafo não 
seria atravessável.
Estudando o caso, Euler elaborou algumas regras que explicam porque 
https://apps.univesp.br/labirinto-de-konigsberg/ 
o passeio é impossível. Para entendê-las, é preciso compreender alguns 
conceitos. Veja a seguir:
Vértices adjacentes e aresta incidente: quando existe uma 
aresta ligando dois vértices, dizemos que os vértices são 
adjacentes e que a aresta é incidente aos vértices.
Grau do vértice: o número de arestas que incidem sobre o vértice 
v é chamado grau do vértice v, simbolizado por d(v).
Grau do vértice a: d(a) = 3 
Grau do vértice b: d(b) = 3 
Grau do vértice c: d(c) = 3 
Grau do vértice d: d(d) = 5
Grafos conexos e desconexos: dizemos que um grafo é conexo 
se qualquer par de pontos é ligado por ao menos um caminho.
Exemplo de grafo conexo.
Se há pelo menos um par de vértices que não está ligado a nenhuma 
cadeia (caminho), o grafo é considerado desconexo.
Exemplo de grafo desconexo.
Analisando o grafo do problema de Konigsberg
Considerando o grafo formado pelas pontes de Konigsberg, Euler 
demonstrou que o fato de os graus dos vértices serem ímpares 
influencia decididamente na impossibilidade do passeio. A partir dessa 
análise, o matemático formula o seguinte teorema: 
 
Um grafo conexo G é dito atravessável se, e somente se, 
todos os seus vértices têm grau par.
 
Note que, no caso do enigma, os vértices (margens e ilhas) estão 
conectados por números ímpares de arestas (pontes). Por isso, ao 
retirar a ponte do meio, o passeio se torna possível: os graus tornam-se 
pares, conforme preconiza o teorema. Veja:
Observe o grafo representado na própria página inicial do Facebook!
Outro exemplo - não vinculado às tecnologias - foi o uso dos grafos 
pelo matemático britânico Arthur Cayley (1821-1895), que utilizou a 
ideia para a enumeração dos isômeros de hidrocarbonetos alifáticos 
saturados, em química orgânica. 
 
Os grafos também são reconhecíveis na representação 
das cadeias carbônicas.
Observe que, na figura da esquerda, todos os vértices são de grau ímpar; ao 
retirar uma aresta (ponte), todos passam a ter grau par.
A relevância do estudo dos grafos
Somente por volta do século XIX o estudo dos grafos teve maior 
atenção. O desenvolvimento da tecnologia, em especial, foi o grande 
responsável para a evolução da Teoria dos Grafos. Surgiram, também, 
importantes aplicações em química e engenharia.
Uma possibilidade de utilização dos grafos é a representação de 
relações pessoais, simbolizando as pessoas por vértices e a ligação 
entre elas por arestas - é o que acontece nas redes sociais.
As conexões do Facebook, por exemplo, e a maneira como as sugestões 
de amizade surgem podem ser facilmente representadas por um 
grafo. Usando-o, a plataforma consegue descobrir qual sugestão está 
mais conectada às pessoas que já fazem parte da sua rede de amizade 
e, assim, potencializar as chances de você aceitar essa sugestão, 
aumentando cada vez mais as arestas/conexões. 
Além disso, uma das clássicas utilizações dos grafos está em descobrir 
o menor trajeto de um ponto para o outro, utilizando as arestas como 
ruas ou trilhos, por exemplo, e os cruzamentos como os vértices. Dessa 
forma, através da observação do grafo desenhado, surge a possibilidade 
de redefinir malhas viárias, desenvolver rotas mais rápidas etc.
No mapa do metrô de São Paulo, podemos identificar grafos desconexos. 
Os grafos podem também auxiliar na criação de uma estratégia de 
controle de epidemias e vacinação. Nesse caso, usamos os vértices 
como os locais onde os casos foram notificados primeiramente, e 
as arestas representando a mobilidade urbana. Assim, retrata-se a 
circulação das pessoas infectadas, permitindo o controle da doença e 
indicando quais locais devem ser tratados primeiro.
Com tudo isso, podemos concluir que os grafos 
são muito úteis na busca de soluções para 
nossos problemas cotidianos em diversas áreas - 
daí a relevância de compreendê-los e estudá-los! 
Para saber mais a respeito desta teoria, acesse 
este link do Portal do Saber. 
https://portaldosaber.obmep.org.br/index.php/modulo/ver?modulo=84