Material de Estudos - Unidade 1 - Intr Teoria dos Grafos

Prévia do material em texto

INTRODUÇÃO À TEORIA DOS GRAFOSINTRODUÇÃO À TEORIA DOS GRAFOS
INTRODUÇÃO À TEORIA DOSINTRODUÇÃO À TEORIA DOS
GRAFOSGRAFOS
Autor: Me. Sergio Eduardo Nunes
Revisor : Emerson dos Santos Paduan
IN IC IAR
introdução
Introdução
Há algumas atividades cotidianas que são carregadas de técnicas e conceitos,
porém, as pessoas não imaginam que estão utilizando-as para resolver
problemas do dia a dia. Os grafos são, com certeza, um desses casos, pois
permitem, por meio de suas aplicações, que pessoas que não tenham
habilidades matemáticas e/ou computacionais utilizem tais técnicas para
determinar o caminho mais curto para passar em mais de dois lugares, a rota
dentro de um supermercado, além de diversas outras aplicações.
Caro estudante, inicialmente, nesta unidade, você terá oportunidade de
compreender o surgimento da teoria dos grafos, reconhecer os elementos
dos grafos e as possíveis modelagens, por �m, relacionar e conceitos acerca
dos grafos de forma a utilizar as técnicas para resolução de problemas.
Pronto para mais um desa�o? Então vamos discutir alguns aspectos básicos
sobre a teoria dos grafos.
Para iniciarmos os estudos acerca da teoria dos grafos, vamos compreender
como ocorreu a necessidade de se criar uma técnica que utiliza os grafos para
resolver determinados problemas.
Segundo Cardoso (2005), a teoria dos grafos foi inicialmente discutida no
século XVIII por um matemático com diversas contribuições, o suíço Leonhard
Euler. Ele teorizou os grafos a �m de se propor uma solução para o problema
das sete pontes de Königsberg.
Tal problema se originou no século 18 na cidade de Königsberg (Kaliningrado),
onde existiam sete pontes que cruzavam o rio Pregel, conforme pode-se
observar na Figura 1.1, existia uma conexão entre as duas ilhas e as ilhas
também se conectavam com as margens.
Aspectos Históricos dosAspectos Históricos dos
GrafosGrafos
A pergunta que Euller gostaria de responder era “Seria possível fazer um
caminho que passe pelas sete pontes de forma que só se passe uma vez por
cada uma delas?”. Com esses estudos, Euller, no ano de 1736, procurava
solucionar um desa�o no ramo da matemática que mais tarde se tornou uma
solução para diversas outras áreas do conhecimento. Porém, Euller chegou à
conclusão deque não existia uma solução para o problema (mais tarde você
entenderá o motivo).
Com isso, alguns estudos foram sendo difundidos ao longo dos anos,
contribuindo com algumas áreas de conhecimentos. Cardoso (2005) a�rma
que por volta de 1962 Ford e Fulkerson utilizaram os conhecimentos
produzidos por Euller para desenvolver a teoria dos �uxos em redes com uma
grande contribuição no ramo de pesquisa operacional.
Figura 1.1 - As sete pontes de Königsberg 
Fonte: Adaptado de Problema [s.d.].
Já na área de tecnologia da informação, a teoria dos grafos contribuiu para o
surgimento/aprimoramento na criação de �uxogramas, no desenvolvimento
de protocolos de redes para cálculo do melhor caminho (exemplo do
protocolo Open Shortest Pathe First (OSPF)), nos algoritmos de escalonamento
e ordenação, nas máquinas de estados, circuitos elétricos, entre outros.
praticar
Vamos Praticar
Euller por meio de uma re�exão encontrou um problema de trajeto das sete pontes
na cidade de Konigsberg que mais tarde serviu de base para solução em diversas
áreas de conhecimento.
saiba mais
Saiba mais
O texto intitulado “Teoria dos Grafos ajuda
na resolução de problema cotidiano” discute
de forma interessante como podem ser
aplicados os conhecimentos acerca da teoria
dos grafos, na busca de situações que são
encontradas no cotidiano de pessoas e
empresas.
Fonte: Elaborado pelo autor.
ACESSAR
http://www.usp.br/agen/?p=183512
FREITAS, A.; BORGES, L. M. As pontes de Konigsberg . Disponível em:
http://www2.fc.unesp.br/revistacqd/index.jsp . Acesso em: 24 nov. 2019.
Para melhor compreensão do cenário analisado por Euller, observe na �gura
seguinte.
Com base no exposto, assinale a alternativa que descreve corretamente qual era o
objetivo de Euller na análise das pontes de Konigsberg.
a) Analisar se havia uma forma da população não utilizar todas as pontes,
sem que ocorresse prejuízo ao �uxo de transporte na cidade.
Feedback: alternativa incorreta , pois o objetivo não era eliminar a utilização
das pontes e sim fazer um trajeto pelas sete pontes, passando uma única vez
em cada uma.
b) O objetivo era numerar as pontes de 1 a 7 e utilizar o trajeto apenas das
pontes pares de forma que toda a cidade �casse acessível.
Feedback: alternativa incorreta , pois as pontes não foram numeradas e
separadas em pares e ímpares. A intenção era procurar uma forma de passar
por todas as pontes uma vez só.
c) O objetivo de Euller era diminuir o trânsito na cidade, propondo que
algumas pontes permitissem o trajeto em ambos os lados (mão dupla).
Feedback: alternativa in correta , pois a intenção não era de garantir �uidez
no trânsito da cidade, mas sim fazer um estudo de um trajeto que passando
por todas as pontes, porém, de uma única vez.
Figura - Mapa deKonigsberg 
Fonte: Google Maps (2019, on-line ).
http://www2.fc.unesp.br/revistacqd/index.jsp
d) O objetivo era encontrar um trajeto que passasse por todas as pontes,
porém uma única vez.
Feedback: alternativa correta , pois Euller tinha a intenção de promover um
estudo de um trajeto pelas sete pontes de Konigsberg de forma que o
caminho escolhido passasse apenas uma vez em cada uma das pontes da
cidade.
e) O objetivo era numerar as pontes de 1 a 7 e utilizar o trajeto apenas das
pontes ímpares. De forma que toda a cidade �casse acessível.
Feedback: alternativa incorreta , pois as pontes não foram numeradas por
Euller, como também não foram separadas em pares e ímpares. O objetivo
era ter uma análise de um trajeto que passasse por todas as pontes, sem que
houvesse repetição.
Embora os grafos estejam presentes em diversas aplicações em nosso
cotidiano, faz-se necessário construir exemplos para que posteriormente
permita a compreensão de seus conceitos em sua completude. Para tal,
vamos analisar a Figura 1.2. 
De�nição de GrafosDe�nição de Grafos
Figura 1.2 - Mapa de Rotas 
Fonte: Google Maps (2019b, on-line).
Esse exemplo poderia ser representado de forma textual, porém, não
forneceria respostas rápidas e e�cientes para perguntas como: existe um voo
direto do Rio de Janeiro para Brasília? É fácil perceber que os grafos podem
proporcionar uma característica informacional mais e�cientes que longos
textos.
Com base no exemplo apresentado, segundo Feo�lo�, Kohayakawa e
Wakabayashi (2004), os grafos podem ser de�nidos como pares ordenados
compostos por vértices e elementos não ordenados designados pelo conjunto
de arestas. Diversas são as literaturas que fazem uma de�nição formal acerca
da teoria dos grafos, porém, sua estrutura básica é de�nida tripla ordenada G
= (V, A, g), onde:
G (grafo): são as representações formais dos elementos que
compõem um grafo.
V (vértices): conjuntos de nós não vazio. Dado um grafo,
representado por G, onde os elementos do conjunto V:= V (G) são
chamados de vértices de G.
A (arestas): são os arcos encontrados entre os vértices. Dessa forma,
denota-se os elementos de E := E(G) são chamados de arestas de G.
g (relação V X A): são funções de associação para cada arco a um par
não ordenado entre os nós. Denomina-se V X A := (V X A)(G) como a
lei de incidência do grafo G.
Para que o conceito dos elementos encontrados em um grafo possa ser
contextualizado, retome o cenário descrito na Figura 1.2, onde é demonstrado
alguns planos de voos. Dessa forma:
Os vértices: seriam as representações das cidades onde partem os
voos, a saber: São Paulo, Rio de Janeiro, Belo Horizonte, Brasília,
Goiânia e Florianópolis.
As arestas: são as conexões entre as cidades (aeroportos), em que: A
= {(São Paulo X Rio de Janeiro), (São Paulo X Belo Horizonte), (São
Paulo X Florianópolis), (São Paulo X Brasília), (São Paulo X Goiânia),
(Rio de Janeiro X Belo Horizonte),(Florianópolis X Goiana)}. Dessa
forma, temos 7 arestas.
Observe ainda que quando uma aresta liga dois vértices, diz-se que esses são
adjacentes e que essa aresta incide sobre os vértices.
Função de associação: dado o cenário apresentado observe as
seguintes funções:
○ g (São Paulo): 5. Pois existe conexão com o Rio de Janeiro, Belo
Horizonte, Brasília, Goiânia e Florianópolis. 
reflita
Re�ita
Com uma base de conhecimento tão sólida acerca da teoria
dos grafos, porque tais conhecimentos não são utilizados para
forma como as pessoas se transportam diariamente? Será que
se for aplicado tais conhecimentos para resolver problemas
de deslocamento, entregas etc. não haveria uma economia
signi�cante? Ou ainda, não estaríamos aumentando a
qualidade de vida das pessoas?
Fonte: Elaborado pelo autor.
○ g (Rio de Janeiro): 2. Pois existe conexão com São Paulo e Belo
Horizonte. 
○ g (Belo Horizonte): 2. Pois existe conexão com São Paulo e Rio de
Janeiro. 
○ g (Brasília): 1. Pois existe conexão somente com São Paulo. 
○ g (Goiânia): 2. Pois existe conexão com São Paulo e Florianópolis. 
○ g (Florianópolis): 2. Pois existe conexão com São Paulo e Goiânia.
Essa função de associação encontrada em cada uma das cidades do exemplo
é conhecida por grau do vértice, que pode ser denotada por g(V). Uma
curiosidade é que se A é �nito, então a valência total é o dobro do número de
arestas. Com isso, no exemplo apresentado, temos que:
Contudo, os grafos podem apresentar diversos tipo de formatos, atendendo
assim, a vários tipos de aplicações.
Representação dos Grafos
Basicamente, a maioria dos grafos são representados gra�camente, embora
essa não seja a única forma de representação. Consiste em desenhar um
círculo, onde são representados os vértices. Uma linha que liga esses vértices
é conhecida como aresta. Esse formato está representado na Figura 1.3.
d(total) = A ∗ 2
A = 7
d(total) = 7 ∗ 2, portanto, d(total) = 14.
Porém, essa não é a única forma como os grafos podem ser representados.
Sendo possível utilizar:
Teoria dos conjuntos: a teoria dos grafos é representada por meio
dos conhecimentos acerca de conjuntos. Em que:
○ Os vértices: é representado pelo conjunto V = {A, B, C, D, E}, onde
cada letra no conjunto representa um vértice descrito na Figura
1.3. 
○ As arestas: é representado pelo conjunto A= {(A, B), (B, C), (C, D),
(D, E)}. Onde cada conjunto nas chaves representa o
relacionamento entre dois vértices.
Textuais: são representações por meio de textos verbais, podendo
ser uma narrativa, em forma de tópicos, entre outras formas.
Observe um exemplo em que uma empresa buscou entender o
relacionamento entre os colaboradores, a �m de conhecer as
potencialidades da equipe enquanto time. Com isso, foi observado as
comunicações enviadas por Mateus, Paulo, João e Pedro. Por meio
dessa análise, foi possível concluir que: Mateus se comunicou com
Paulo e Pedro duas vezes; Paulo se comunicou com João três vezes;
João não se comunicou com Pedro uma vez; Pedro se comunicou
com João quatro vezes.
Figura 1.3 - Exemplo de grafo representado gra�camente 
Fonte: Elaborada pelo autor.
Para melhor compreensão texto foi representado por conjuntos. Em que:
○ Vértices: representados por V = {Mateus, Paulo, João, Pedro}.
Sendo um conjunto com cada um dos colaboradores observados. 
○ Arestas: sendo representado pelo conjunto das relações A =
{(Mateus, Paulo), (Mateus, Paulo), (Mateus, Pedro), (Mateus, Pedro),
(Paulo, João), (Paulo, João), (Paulo, João), (João, Pedro), (Pedro, João),
(Pedro, João), (Pedro, João), (Pedro, João)}.
Matrizes ou tabelas: ainda é possível se apropriar dos
conhecimentos estudados por disiciplinas como geometria analítica e
álgebra vetorial e para representar os grafos. Essa técnica pode ser
observada a seguir pela matriz:
Para esse tipo de representação pode-se considerar que o 0 (zero) signi�ca
que não existe relacionamento entre os vértices V = {A, B, C, D}. E o número 1
(um) representa o relacionamento entre os vértices. Dessa forma, podemos
de�nir as arestas, para melhor compreensão, observe a representação da
matriz na Figura 1.4.
A B C D
A 0 1 1 1
B 1 0 0 0
C 1 0 0 1
D 1 0 1 0
Com isso, pode-se perceber que existem diversas formas de se representar os
grafos, seja ele por diagramas, conjuntos, textos ou tabelas/matrizes, o intuito
é poder desenvolver uma ferramenta que permita a compreensão dos
relacionamentos e assim auxiliar na tomada de decisões.
praticar
Vamos Praticar
Um aplicativo de comunicação permite que os usuários possam se comunicar via
chat, ou ainda, por videoconferência. Após algumas observações no grupo com os
componentes Salomão, Hércules, Aquiles, Zeus, Atlas e Netuno, foi gerado o
seguinte relatório: Salomão ligou para Aquiles e recebeu mensagem de Zeus e Atlas;
Hércules não fez comunicação com ninguém, porém recebeu mensagem de
Netuno. Aquiles ligou para todos os componentes, com exceção de Salomão. Com
base exposto, assinale a alternativa os vértices da situação analisada.
Figura 1.4 - Representação da matriz por diagrama 
Fonte: Elaborada pelo autor.
a) Hércules, Aquiles, Zeus, Atlas e Netuno.
Feedback: alternativa incorreta , pois nesse conjunto possui somente os
componentes que efetuaram ou receberem comunicação.
b) Salomão, Hércules, Aquiles, Zeus, Atlas e Netuno.
Feedback: alternativa correta , pois estão representados todos os
componentes, independente se houve alguma comunicação.
c) Salomão, Hércules e Aquiles.
Feedback: alternativa incorreta , pois está faltando alguns componentes.
d) Zeus, Atlas e Netuno.
Feedback: alternativa incorreta , pois está faltando alguns componentes.
e) Somente Aquiles.
Feedback: alternativa incorreta , pois está faltando alguns componentes.
Agora que você já pode compreender o que são grafos e de que forma esses
podem ser representados, conhecer os tipos grafos poderá auxiliar você no
futuro a entender alguns conceitos mais avançados acerca da teoria dos
grafos. Para isso, Boaventura e Jurkiewicz (2009) de�nem que os grafos estão
divididos conforme a sua estrutura, conforme abaixo:
Grafo simples: são representações de grafos que não possuem
direcionamento, apenas representação de vértice e arestas. 
Tipos de GrafosTipos de Grafos
Grafo completo: é um grafo que para cada vértice existente possui
uma aresta conectando essa aos demais. Em que todos os vértices
possuem o mesmo grau.
Grafo nulo: este grafo possui um conjunto vazio de arestas.
Figura 1.5 - Exemplo grafo simples 
Fonte: Elaborada pelo autor.
Figura 1.6 - Exemplo grafo completo 
Fonte: Elaborada pelo autor.
Grafo Trivial: é representado por aquele grafo que possui apenas
um vértice, e nenhuma aresta.
Grafo regular: é aquele que todos os vértices têm o mesmo grau.
Figura 1.7 - Exemplo grafo nulo 
Fonte: Elaborada pelo autor.
Figura 1.8 - Exemplo grafo trivial 
Fonte: Elaborada pelo autor.
Multigrafos: possuem múltiplas arestas ligando no mesmo vértice.
Esses são os grafos mais comuns de serem encontrados nas literaturas,
porém existem mais tipos que permitem algumas representações especí�cas.
No exemplo demonstrado na Figura 1.10, as arestas vermelhas são as
múltiplas.
Figura 1.9 - Exemplo grafo regular 
Fonte: Elaborada pelo autor.
Figura 1.10 - Exemplo de multigrafo 
Fonte: 0x24a537r9 / Commons Wikimedia.
praticar
Vamos Praticar
As portas automáticas encontradas em shoppings e aeroportos são passíveis de
representações dos grafos e permitem que sejam representados todos os estados
possíveis, para que assim que ler a entrada do sensor a porta tome determinada
ação na qual foi programada. Basicamente, esse modelo pode ter os seguintes
estados:
Frente: clientes entrando no estabelecimento. 
Loja: clientes saindo do estabelecimento. 
Ambos: clientes entrando e saindo do estabelecimento. 
Nenhum: nenhum cliente entrando e saindo do estabelecimento.
Quando não ocorre mudança de estado, a aresta aponta para o próprio vértice.
Para fazer a representaçãode um problema por meio de grafos é possível utilizar
diversos tipos. Com base nesse contexto assinale a alternativa que melhor
representa o cenário apresentado.
a) Grafo Nulo.
Feedback: alternativa incorreta , pois são necessárias arestas para
representar a mudança de estado aberto para fechado.
b) Grafo Trivial.
Feedback: alternativa incorreta , pois são necessários dois vértices para
representar os dois estados possíveis.
c) Grafo Regular.
Feedback: alternativa incorreta , pois o grafo regular não permite apontar
as arestas para o próprio vértice.
d) Multigrafo
Feedback: alternativa correta , pois quando não ocorre mudança de estado
a aresta deve apontar para o próprio vértice, con�gurando assim, um
multigrafo.
e) Não é possível representar por meio de grafos.
Feedback: alternativa incorreta , pois é possível representar com
multigrafos.
Caro aluno, agora que você já sabe que existem diversos tipos de grafos com
formatos e de�nições, é chegada a hora de compreender os conceitos
relacionados ao grau que os vértices possuem. Isso irá auxiliar você a
compreender o número de arestas incidentes nos vértices, facilitando, assim,
a busca por soluções por meio dos grafos.
Segundo Boaventura Netto e Jurkiewicz (2009), o grau de um vértice (V) é
denominado como grau(V), ou ainda, deg(V). Para calcular o grau de um
vértice, deve-se fazer a somatória do número de arestas incidentes nesse
vértice. Observe o exemplo demonstrado na Figura 1.11.
Grau de um VérticeGrau de um Vértice
Com isso, podemos de�nir que no exemplo o grau do vértice V1 é igual a 3,
pois temos três incidências sobre o vértice, partindo dos vértices A, B e C.
Quando o grafo é do tipo multigrafo, ou seja, existe um laço, esse deve ser
contado duas vezes. Observe o exemplo na Figura 1.12.
Com isso, podemos concluir que o grau do vértice V1 é igual a 5, pois incidem
sobre V1 os vértices A, B e C, e o laço que vale dois.
Figura 1.11 - Primeiro exemplo de grau de um vértice 
Fonte: Elaborada pelo autor.
Figura 1.12 - Grau de um multigrafo 
Fonte: Elaborada pelo autor.
Ainda que o grau total do grafo é a soma dos graus de todos os vértices. Para
compreender esse conceito, observe a Figura 1.13.
Com base no grafo apresentado, podemos concluir que:
Grau(A) = 2, pois as arestas ligadas em B e C incidem sobre o vértice
A.
Grau(B) = 2, pois as arestas ligadas em A e C incidem sobre o vértice
B.
Grau(C) = 2, pois as arestas ligadas em A e B incidem sobre o vértice
C.
Dessa forma, considerando o grafo analisado como G, temos que,
Quando se tem um grafo direcionado, a regra para determinar o seu grau é a
somatória de arestas que chegam ao vértice, com as arestas que saem do
Figura 1.13 - Exemplo de Grau de um grafo 
Fonte: Elaborada pelo autor.
Grau(G) = Grau(A) + Grau(B) + Grau(C)
portanto,
Grau(G) = 2 + 2 + 2
Grau(G) = 6
vértice. Compreendido como: arestas que chegam ao vértice, igual a indeg(V);
e as arestas que saem do vértice: outdeg(V). Para a compreensão desse
conceito, observe a Figura 1.14.
Para determinar o Grau(C) temos que:
Chegam ao vértice C as arestas 3 e 4, portanto, grau 2. Saem do vértice C a
aresta 5, portanto grau 1. Dessa forma, o .
O Brasil é dividido em Estados e existe uma subdivisão para agrupar esses
estados por região do país (sul, sudeste, norte etc.). Para viabilizar o
transporte, foram construídas vias como estradas, pontes, rodovias e demais
estruturas, para que permitisse o caminho de ida e volta, entre as capitais dos
estados. Analise:
Figura 1.14 - Exemplo de Grau em grafo direcionado 
Fonte: Elaborada pelo autor.
Grau(C) = 2 + 1 = 3
Conforme podemos perceber, os grafos são ferramentas matemáticas que
permitem que possamos analisar determinados sistemas, nos possibilitando
extrair informações importantes na tomada de decisão. Mas, para tal, saber
identi�car os seus componentes é de extrema importância para que
possibilite a compreensão das técnicas mais complexas acerca de teoria dos
grafos.
praticar
Vamos Praticar
Existe um teorema conhecido como: teorema do handshaking , em português
teorema do aperto de mãos, que dita que a soma do grau de todos os vértices é
duas vezes o número de arestas de determinado Grafo.
1 2 3
Com base no exposto, observe anterior e assinale a alternativa que corresponda ao
grau do grafo.
a) 15.
Feedback: alternativa incorreta , pois no grafo temos oito arestas, com isso 
. Dessa forma, o grau do grafo, .
b) 16.
Feedback: alternativa correta , pois no grafo temos oito arestas, com isso 
. Dessa forma, o grau do grafo, .
c) 17.
Feedback: alternativa incorreta , pois no grafo temos oito arestas, com isso 
. Dessa forma, o grau do grafo, .
d) 18.
Feedback: alternativa incorreta , pois no grafo temos oito arestas, com isso 
. Dessa forma, o grau do grafo, .
e) 19.
Feedback: alternativa incorreta , pois no grafo temos oito arestas, com isso 
. Dessa forma, o grau do grafo, .
Figura - Grau por teorema do aperto de mãos 
Fonte: Elaborada pelo autor
2X8 = 16 Grau(G) = 16
2X8 = 16 Grau(G) = 16
2X8 = 16 Grau(G) = 16
2X8 = 16 Grau(G) = 16
2X8 = 16 Grau(G) = 16
indicações
Material
Complementar
FILME
História da Matemática: Além do in�inito.
Ano: 1990
Comentário: Esse episódio da série produzida pela
BBC é interessante, pois faz um passeio em diversos
lugares, demonstrando e discutindo as descobertas
matemáticas, entre elas os grafos.
TRA ILER
LIVRO
Elementos de Teoria da Computação
Harry R. Lewis & Christos H. Papadimitrion
Editora: Bookman
ISBN: 9788573075342
Comentário: Esse título é voltado para os estudos das
linguagens formais e autômatos, porém, para explicar
se apropria da teoria dos conjuntos, já para demonstrar
a aplicação dos conceitos o autor utiliza os grafos.
conclusão
Conclusão
Com o exposto nesta unidade você pode compreender os aspectos básicos
acerca de teoria dos grafos. Com os assuntos discutidos até o momento, é
possível compreender o surgimento da teoria dos grafos, identi�car os
elementos que compõem um grafo, as formas de representação, os tipos
possíveis, e calcular o grau dos grafos. Com os conhecimentos adquiridos até
o momento, já é possível resolver pequenos problemas por meio dos grafos e
suas respectivas representações.
referências
Referências
Bibliográ�cas
BOAVENTURA NETTO, P. O.; JURKIEWICZ, S. Grafos - Uma introdução. Rio de
Janeiro: UFRJ, 2009.
CARDOSO, D. M. Teoria dos Grafos e Aplicações . Aveiro: Universidade de
Aveiro, 2005.
FEOFILOFF, P.; KOHAYAKAWA, Y.; WAKABAYASHI, Y. Uma Introdução Sucinta
à Teoria dos Grafos , 2004.
GOOGLE MAPS. Mapa de rotas de parte do Brasil . 2019a. Disponível em:
https://bit.ly/30XQL8B . Acesso em: 15 dez. 2019a.
GOOGLE MAPS. Mapa de Konigsberg . 2019b. Disponível em:
https://bit.ly/36xrG5s . Acesso em: 15 dez. 2019b.
PROBLEMA das Pontes de Königsberg. UFSC . [s.d.]. Disponível em:
http://www.inf.ufsc.br/grafos/problema/pontes/grafos.html . Acesso em: 24
nov. 2019.
https://www.google.com.br/maps/place/S%C3%A3o+Paulo/@-19.1583924,-56.549382,5z/data=!4m5!3m4!1s0x94ce597d462f58ad:0x1e5241e2e17b7c17!8m2!3d-23.5431786!4d-46.6291845
https://www.google.com.br/maps/place/Kaliningrado,+Oblast+de+Kaliningrado,+R%C3%BAssia/@54.7117271,20.3244458,11z/data=!3m1!4b1!4m5!3m4!1s0x46e33d8d4b7c21a9:0x5050960016126ed3!8m2!3d54.7104264!4d20.4522144
http://www.inf.ufsc.br/grafos/problema/pontes/grafos.html