Trabalho de Matematica 2 Teoria dos Grafos_Cleuma

Prévia do material em texto

FAETERJ – Unidade Barra Mansa 
Tecnologia em Sistemas para a Internet com foco em Empreendedorismo Digital 
 
 
 
 
 
CLEUMA MOREIRA 
 
 
 
 
 
 
 
 
 
 
 
 
TRABALHO DO 2º BIMESTRE 
TEORIA DOS GRAFOS 
 
 
 
 
 
 
 
 
 
RIO DE JANEIRO – RJ 
2021 
 
 
 
 
 
 
 
 
 
CLEUMA MOREIRA 
 
 
 
 
 
 
 
 
 
 
TRABALHO DO 2º BIMESTRE 
TEORIA DOS GRAFOS 
 
 
 
 
 
 
Trabalho apresentado no curso de 
Tecnologia em Sistemas para a Internet com 
foco em Empreendedorismo Digital, 
disciplina de Matemática Aplicada para 
compor a nota do 2º bimestre. 
 
Professora: AEB. 
 
 
 
 
RIO DE JANEIRO - RJ 
2021 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
O importante é o ser e não o vir a ser; um não é o oposto do outro, havendo 
o oposto ou a oposição, cessa o ser. Ao findar o esforço para vira-se, surge 
a plenitude do ser, que não é estático; não se trata de aceitação; o vira-se 
depende do tempo e do espaço. O esforço deve cessar; disso nasce o ser que 
transcende os limites da moral e da virtude social, e abala os alicerces da 
sociedade. Esta maneira de ser é a própria vida, não mero padrão social. 
Lá, onde existe vida, não existe perfeição; a perfeição é uma ideia, uma 
palavra; o próprio ato de viver e existir transcende toda forma de 
pensamento e surge do aniquilamento da palavra, do modelo, do padrão. 
Jiddu Krishnamurti (1895-1986) 
 
 
 
 
 
SUMÁRIO 
 
 
1 INTRODUÇÃO ................................................................................................ 5 
 
2 TEORIA DOS GRAFOS................................................................................... 7 
 
2.1 DEFINIÇÃO ..................................................................................................... 9 
 
2.2 VÉRTICES E ARESTAS ................................................................................ 10 
 
3 EXEMPLOS DE REAPRESENTAÇÃO GRÁFICA ........................................ 11 
 
4 O QUE É UM DÍGRAFO ................................................................................. 13 
 
5 DESAFIO E CURIOSIDADE .......................................................................... 16 
 
REFERÊNCIAS E FONTES BIBLIOGRÁFICAS.................................................. 17 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
1. INTRODUÇÃO 
 
O objetivo desta pesquisa é elaboração de um texto introdutório sobre a Teoria 
de Grafos, de modo que possa ser utilizado pelos alunos do curso de graduação em 
Tecnologia em Sistemas para a Internet, com foco em Empreendedorismo Digital. 
Ramo da matemática que se utiliza de modelos (os grafos) para estudar as 
relações entre os objetos de um conjunto. 
O primeiro artigo relacionado a grafos foi um marco na matemática, escrito pelo 
matemático suíço Leonhard Euyler (1707-1783) no ano de 1736. Euler iniciou seus 
estudos em grafos discutindo enigma, hoje conhecido como O Problema das Pontes 
de Königsberg, o qual ele resolveu e determinou um método geral para problemas do 
mesmo tipo. 
 
 
 
Por muito tempo os habitantes daquela cidade perguntavam-se se era possível 
cruzar as sete pontes numa caminhada contínua sem passar duas vezes por qualquer 
uma delas. 
 
 
No século 18 havia na cidade de Königsberg um conjunto de sete pontes 
(identificadas pelas letras de a até f na figura abaixo) que cruzavam o rio Pregel . Elas 
conectavam duas ilhas entre si e as ilhas com as margens. 
 
 
 
Euler pensou: “este é um tipo de problema no qual as distâncias 
envolvidas são irrelevantes, o que importa é como as várias 
porções de terra estão interligadas entre si.” 
Modelo do Problema 
O Grafo utilizado como modelo é definido como segue: 
 
V = { m | m é uma ilha ou uma margem } 
A = { (m1,m2, p} | existe uma ponte p unindo as margens ou ilhas m1 e m2 } 
 
Os conjuntos acima são apresentados, a seguir, na forma extensiva, contendo todos 
seus elementos, extraídos do problema: 
 
V = { A, B, C, D } 
A = { (A,C,c), (A,C,d), (A,B,a), (A,B,b), (A,D,e), (B,D,f), (C,D,g) } 
 
O Grafo, construído a partir dessas definições pode se apresentar como: 
 
Observação sobre o Grafo: 
Não orientado 
Multigrafo 
Conexo 
 
SOLUÇÃO 
 A solução consiste em, partindo de qualquer vértice, tentar atravessar todas as 
arestas uma única vez e retornar ao vértice de origem. 
Euler, ao propor a solução para este problema, se preocupou em descobrir em que 
tipos de grafos se pode fazer esse caminhamento fechado, passando por todas as 
arestas uma única vez. Esse tipo de caminhamento foi chamado ‘caminho de Euler’, 
e um grafo que consiste de um caminho de Euler foi denominado ‘grafo de Euler’. 
Como todo grafo de Euler possui um caminho de Euler, como o proposto no problema 
das pontes de Königsberg, para sabermos se existe solução, basta sabermos se o 
grafo modelo do problema é um grafo de Euler ou não. 
 
 Pela análise do grafo modelo G para o problema das pontes de Königsberg, 
observa-se que Para Todo v E V, gr(v) é ímpar. Logo, o grafo G não é um grafo de 
Euler. Isso significa que o problema não possui solução. Note que não é necessário 
que tenhamos Para Todo v E V, gr(v) é ímpar, basta que Exista Pelo Menos Um v E 
V | gr(v) é ímpar para concluirmos que o grafo em questão não é um grafo de Euler. 
 
 
 
 
2. TEORIA DOS GRAFOS 
 
A Teoria dos Grafos é muito relevante como modelo matemático para alguns 
problemas mais importantes e difíceis da computação. Essa teoria possui aplicação 
direta em áreas como: 
 Física; 
 Química; 
 Psicologia; 
 Engenharia e etc. 
Convém ressaltar que a Teoria dos Grafos é de fundamental importância aos 
cursos de Engenharia da Computação e Ciências. 
É impossível traçar um caminho que passe só uma vez cada ponte e, no 
final, tenha atravessado todas elas!! ☹☹ 
 
 
Diversos problemas podem ser representados por grafos: 
 Trajetos entre cidades 
 Roteamento de veículos 
 Mapa de páginas de um site 
 Redes de computadores 
 Representação de máquinas de estados finitos 
Uma área de grande interesse da ciência da computação é a obtenção de 
estruturas de dados e de algoritmos eficientes para manipulação de grafos. 
No século XIX, grafos foram usados em circuitos elétricos e diagramas 
moleculares. A Teoria de Grafos é classificada como um ramo da Topologia, mas está 
fortemente ligada à Álgebra e à Teoria de Matrizes. 
 
USO DA TEORIA DOS GRAFOS X PROBLEMAS REAL
Escalonamento de processos
• Aplicação direta do problema de coloração de 
grafos.
Reconhecimentos de padrões
• Instância do problema de isomorfismo em grafos.
Problema de roteamento
• Verificar se um grafo é Hamiltoniano ou não.
2.1 DEFINIÇÃO 
 
 Grafo é uma entidade composta de duas partes: 
 
 Vértices (nós) Os nós são as “bolinhas” (entidades que você quer 
modelar). 
 Arestas (linhas) As arestas são as relações dessas entidades. 
 
Um grafo G(V,A) é definido pelo par de conjuntos V e A, onde: 
 
V - conjunto não vazio: os vértices ou nodos do grafo; 
A - conjunto de pares ordenados a=(v,w), v e w ∈ V: as arestas do grafo. 
Seja, por exemplo, o grafo G(V,A) dado por: 
V = { p | p é uma pessoa } 
A = { (v,w) | < v é amigo de w > } 
 
Esta definição representa toda uma família de grafos. Um exemplo de elemento 
desta família (ver G1) é dado por: 
V = { Maria, Pedro, Joana, Luiz } 
A = { (Maria, Pedro), (Pedro, Maria), (Joana, Maria), (Maria, Joana), (Pedro, Luiz), 
(Luiz, Pedro), (Joana, Pedro) , (Pedro, Joana) } 
 
 
 
 
 
2.2 VÉRTICES E ARESTAS 
 
A vértice é denominada V e aresta é denominada de A. 
Os vértices constituem o ponto de encontro de dois segmentos laterais. Os 
lados são as linhas poligonais que se encontram dois a dois em cada vértice. Os 
ângulos internos e externos são formados pelo encontro de dois lados consecutivos. 
Grau dos vértices  o grau d
G
(V) de um vértice v em G é o número de arestas 
de G incidentesa v. 
 Cada loop conta como duas arestas 
 
Grau mínimo de G 
Grau máximo de G 
 
 
 
Vértices Adjacentes – dois vértices são adjacentes se estão ligados por uma 
aresta. 
Vértice isolado – Um vértice é dito isolado se não existe aresta incidente sobre 
ele. 
 
Vértice 
(nós)
Aresta 
(arco)
 
Aresta é a reta que se origina a partir da interseção de dois planos que formam 
um ângulo. Para a geometria, a aresta também pode caracterizar cada lado dos 
polígonos que formam um poliedro ou que formam o ângulo poliédrico. 
Arestas paralelas – Duas arestas incidentes nos mesmos vértices (não importa 
a orientação). 
 Uma aresta que une dois vértices diz-se aresta incidente em cada um dos 
seus vértices. 
 Quando duas arestas incidem num mesmo vértice elas são arestas 
adjacentes. 
 Arestas paralelas: São arestas que têm os extremos iguais. 
 
 
3. EXEMPLO DE REAPRESENTAÇÃO GRÁFICA 
 
Um mapa do metrô é um grafo: 
 
 
 
 
Na computação: Matriz de Adjacência 
 
Na computação: Matriz de Incidência 
4. O QUE É UM DÍGRAFO? 
 
Tipo especial de grafos nos quais todas as arestas são direcionadas. Caminhos 
em digrafos devem levar em consideração a direção das arestas. 
Dois tipos de graus de vértices: 
 Grau de entrada: número de arestas que “chegam” no vértice; 
 Grau de saída: números de arestas que “saem” do vértice. 
 
Chamado também de Grafo Orientado ou Dirigido, é um grafo cujas arestas (na 
sua totalidade ou parte delas) têm um sentido. 
 
Exemplo: 
 
Considere, agora, o grafo definido por: 
V = { p | p é uma pessoa da família Castro } 
A = { (v,w) | < v é pai/mãe de w > } 
Um exemplo de deste grafo (ver G2) é: 
V = { Emerson, Isadora, Renata, Antonio, 
Cecília, Alfredo } 
A = {(Isadora, Emerson), (Antonio, Renata), 
(Alfredo, Emerson), (Cecília, Antonio), 
(Alfredo, Antonio)} 
G2: 
 
 
A relação definida por A não é simétrica pois se <v é pai/mãe de w>, não é o caso 
de <w é pai/mãe de v>. Há, portanto, uma orientação na relação, com um 
correspondente efeito na representação gráfica de G. 
O grafo acima é dito ser um grafo orientado (ou digrafo), sendo que as conexões 
entre os vértices são chamadas de arcos. 
 
 
 
 
Exemplos: Representação de Grafos em Dígrafo. 
Esquemas de estruturas de grafo. 
 
 
 
 
 
 
Grafos em Recologia 
 
 DESAFIO E CURIOSIDADE 
 
 
 
 
 
 
 
DICA  Antes de programar, represente (desenhe) o grafo adequado para 
resolver o seu problema. Modele, desenhe, escreva! Você NÃO estará perdendo 
tempo, mas sim ganhando. 
 
 
 
REFERÊNCIAS BIBLIOGRÁFICAS: 
 BOAVENTURA, Netto, P. O. Grafos: Teoria, Modelos, Algoritmos. 4a edição. 
Edgar Blucher, 2012. 
 GOLDBARG, M.; GOLDBARG, E. Grafos: Conceitos, algoritmos e aplicações. 
1ª edição. Elsevier, 2012. 
 LUCCHESI, Cláudio Leonardo. Introdução à Teoria dos Grafos. Copyright. RJ. 
Unicamp 1979. 
 PRESTES, Edson. Introdução à Teoria dos Grafos. 2020. 
ARTIGOS E SITES DE PESQUISA: 
 
 COSTA, Polyanna Possani da. Teoria dos grafos e suas aplicações. 2011. 77 
p. Dissertação - (mestrado) - Universidade Estadual Paulista, Instituto de 
Geociências e Ciências Exatas, 2011. Disponível em: 
<http://hdl.handle.net/11449/94358>. Acesso em: 27/06/2021. 
 
 DALLAQUA, Caio. Origem da Teoria dos Grafos – As 7 Pontes de Königsberg. 
2016. Disponível em: < 
http://www.inf.ufsc.br/grafos/problema/pontes/grafos.html > Acesso em: 
28/06/2021. 
 
 SOUZA, Renato Ferreira. Resolução de problemas via teoria de grafos. 2014. 
48p. ICMC/USP. Disponível em: 
https://www.teses.usp.br/teses/disponiveis/55/55136/tde-06072015-
103319/publico/Dissertacao_RenatoFdeSouza_Revisada.pdf Acesso em: 
28/06/2021. 
 
 RECOLOGIA. Disponível em: < http://recologia.com.br/tag/grafos/ > Acesso 
em: 27/06/2021. 
 
 USP – Insituto de Matemática e Estatística Universidade de São Paulo. As 
pontes de Königsberg. Disponível em: < 
https://matemateca.ime.usp.br/acervo/pontes_konigsberg.html > Acesso em: 
28/06/2021.