GRAFOS 1

Prévia do material em texto

INTRODUÇÃO À TEORIA DOS GRAFOSINTRODUÇÃO À TEORIA DOS GRAFOS
INTRODUÇÃO À TEORIA DOS GRAFOSINTRODUÇÃO À TEORIA DOS GRAFOS
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.
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
Aspectos Históricos dos GrafosAspectos Históricos dos Grafos
Figura 1.1 - As sete pontes de Königsberg
Fonte: Adaptado de Problema [s.d.].
conhecimentos produzidos por Euller para desenvolver a teoria dos �uxos em redes com uma
grande contribuição no ramo de pesquisa operacional.
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.
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.
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
Figura - Mapa deKonigsberg
Fonte: Google Maps (2019, on-line ).
http://www2.fc.unesp.br/revistacqd/index.jsp
http://www.usp.br/agen/?p=183512
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.
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).
d) O objetivo era encontrar um trajeto que passasse por todas as pontes, porém uma única vez.
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.
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.
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.
De�nição de GrafosDe�nição de Grafos
Figura 1.2 - Mapa de Rotas
Fonte: Google Maps (2019b, on-line).
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.
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.
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.
○ 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.
Figura 1.3 - Exemplo de grafo representado gra�camente
Fonte: Elaborada pelo autor.
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.
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.
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.
a) Hércules, Aquiles, Zeus, Atlas e Netuno.
A B C D
A 0 1 1 1
B 1 0 0 0
C 1 0 0 1
D 1 0 1 0
Figura 1.4 - Representação da matriz por diagrama
Fonte: Elaborada pelo autor.
b) Salomão, Hércules, Aquiles, Zeus, Atlas e Netuno.
c) Salomão, Hércules e Aquiles.
d) Zeus, Atlas e Netuno.
e) Somente Aquiles.
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.
Figura 1.5 - Exemplo grafo simples
Fonte: Elaborada pelo autor.
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.
Tipos de GrafosTipos de Grafos
Grafo nulo: este grafo possui um conjunto vazio de arestas.
Figura 1.7 - Exemplo grafo nulo
Fonte: Elaborada pelo autor.
Grafo Trivial: é representado por aquele grafo que possui apenas um vértice, e nenhuma
aresta.
Figura 1.8 - Exemplo grafo trivial
Fonte: Elaborada pelo autor.
Grafo regular: é aquele que todos os vértices têm o mesmo grau.
Figura 1.6 - Exemplo grafo completo
Fonte: Elaborada pelo autor.
Multigrafos: possuem múltiplas arestas ligando no mesmo vértice.
Figura 1.10 - Exemplo de multigrafo
Fonte: 0x24a537r9 / Commons Wikimedia.
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.
praticar
Vamos Praticar
Figura 1.9 - Exemplo grafo regular
Fonte: Elaborada pelo autor.
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ção de 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.
b) Grafo Trivial.
c) Grafo Regular.
d) Multigrafo
e) Não é possível representar por meio de grafos.
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.
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.
Grau de um VérticeGrau de um Vértice
Figura 1.11 - Primeiro exemplo de grau de um vértice
Fonte: Elaborada pelo autor.
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.
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,
Figura 1.12 - Grau de um multigrafo
Fonte: Elaborada pelo autor.
Figura 1.13 - Exemplo de Grau de um grafo
Fonte: Elaborada pelo autor.
Grau(G) = Grau(A) + Grau(B) + Grau(C)
portanto,
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 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:
Grau(G) = 2 + 2 + 2
Grau(G) = 6
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.
Com base no exposto, observe anterior e assinale a alternativa que corresponda ao grau do grafo.
a) 15.
b) 16.
1 2 3
Figura - Grau por teorema do aperto de mãos
Fonte: Elaborada pelo autor
c) 17.
d) 18.
e) 19.
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