grafos aplicados à computação AVA 2 veiga de almeida

Prévia do material em texto

1 
 
 
UNIVERSIDADE VEIGA DE ALMEIDA 
SISTEMAS DE INFORMAÇÃO 
 
 
 
 
 
 
 
NATHALIA DA COSTA MARTINS 
TRABALHO DA DISCIPLINA (AVA2) 
GRAFOS APLICADOS À COMPUTAÇÃO 
 
 
 
 
 
 
 
 
 
 
 
 
RIO DE JANEIRO – RJ 
2024 
2 
 
A teoria dos grafos possui uma relevância significativa no âmbito matemático, 
pois oferece uma forma visualmente acessível de representar as conexões entre 
pontos específicos. Por meio dos grafos, é viável converter questões cotidianas em 
problemas matemáticos, permitindo sua análise detalhada. 
 
É possível encontrar um caminho de um vértice para outro vértice em um grafo 
usando vários algoritmos estudados na disciplina de teoria dos grafos. Alguns dos 
algoritmos mais comuns incluem: 
 
1. Busca em largura (BFS - Breadth-First Search): Este algoritmo visita todos 
os vértices em uma distância específica do vértice de origem antes de se mover 
para os vértices mais distantes. Ele pode ser usado para encontrar o caminho 
mais curto entre dois vértices em um grafo não ponderado. 
 A -- B -- C 
 \ | / 
 \ | / 
 D 
 | 
 E -- F 
 
2. Busca em profundidade (DFS - Depth-First Search): Este algoritmo explora 
o máximo possível ao longo de um ramo antes de retroceder. Embora não seja 
tão eficiente quanto o BFS para encontrar o caminho mais curto, o DFS pode 
ser adaptado para encontrar um caminho entre dois vértices em um grafo. 
 
3. Algoritmo de Dijkstra: Este algoritmo é usado para encontrar o caminho mais 
curto entre um vértice de origem e todos os outros vértices em um grafo 
ponderado não negativo. Ele é eficiente e pode ser adaptado para encontrar o 
caminho mais curto entre dois vértices específicos. 
 
 A --(5)--> B --(2)--> C 
 \ ^ / 
 \ | / 
3 
 
 (3) (1) (4) 
 \ | / 
 v v v 
 D -- E 
 
4. Algoritmo de Bellman-Ford: Similar ao algoritmo de Dijkstra, o Bellman-Ford 
encontra o caminho mais curto entre um vértice de origem e todos os outros 
vértices em um grafo ponderado, mas ele pode lidar com grafos que têm 
arestas com pesos negativos (desde que não haja ciclos negativos). 
 A --(-1)--> B --(-2)--> C 
 \ ^ / 
 \ | / 
 (-3) (4) (5) 
 \ | / 
 v v v 
 D -- E 
 
5. Algoritmo de Ford-Fulkerson e Algoritmo de Edmonds-Karp: Esses 
algoritmos são usados para encontrar o fluxo máximo em uma rede de fluxo, 
onde os vértices representam pontos de armazenamento ou consumo e as 
arestas representam canais de comunicação ou transporte. Eles são usados 
em problemas de transporte, design de redes, e fluxo de dados em redes de 
computadores. 
 
6. Algoritmos de Emparelhamento de Grafos: Esses algoritmos são usados 
para encontrar pares de vértices em um grafo de modo que cada vértice seja 
emparelhado com exatamente um outro vértice, sem compartilhar arestas com 
outros pares. Eles são usados em problemas de alocação de recursos, como 
emparelhamento de estudantes com escolas, doadores de órgãos com 
receptores etc. 
 
4 
 
Estes são apenas alguns exemplos de algoritmos que podem ser usados para 
encontrar caminhos entre vértices em grafos, e a escolha do algoritmo depende das 
características específicas do grafo e do problema em questão. 
 
No campo da computação os grafos têm ampla utilização, aplicação e extrema 
relevância como, por exemplo: 
 
o Redes de computadores: 
 
Modelagem de redes: Os dispositivos de rede (roteadores, switches 
etc.) e suas conexões podem ser modelados usando grafos, onde os 
vértices representam dispositivos e as arestas representam conexões 
entre eles. 
 
Roteamento de pacotes: Algoritmos de roteamento como o OSPF 
(Open Shortest Path First) usam grafos para calcular os caminhos mais 
curtos entre os dispositivos em uma rede. 
 
o Algoritmos de busca na web: 
 
Modelagem de Páginas da Web: Páginas da web e seus links podem 
ser representados como um grafo, onde as páginas são vértices e os 
links são arestas. 
 
PageRank: O algoritmo PageRank, usado pelo Google para classificar 
páginas da web em seus resultados de pesquisa, é baseado em 
conceitos de grafos. 
 
o Grafos sociais e de relacionamento: 
 
Redes sociais: Em plataformas como Facebook, Twitter e LinkedIn, os 
usuários e suas conexões podem ser representados como um grafo, 
5 
 
onde os usuários são vértices e as conexões de amizade ou seguidores 
são arestas. 
 
Recomendação de amigos ou conteúdo: Algoritmos de 
recomendação usam grafos sociais para sugerir novas conexões ou 
conteúdo com base nas conexões existentes. 
 
o Compiladores e análise de código: 
 
Árvore de sintaxe abstrata (AST): Em compiladores, os programas de 
código-fonte são convertidos em uma AST, que pode ser vista como um 
tipo de grafo onde os nós representam operações ou estruturas do 
código e as arestas representam dependências. 
 
Análise de dependências: Grafos são usados para representar 
dependências entre módulos, funções ou variáveis em um programa, 
auxiliando na otimização de código e detecção de erros. 
 
o Banco de dados e sistemas de informação: 
 
Modelagem de dados relacionais: Bancos de dados relacionais podem 
ser representados usando grafos, onde as tabelas são vértices e as 
relações entre elas são arestas. 
 
Redes de colaboração: Em sistemas de gerenciamento de informações 
acadêmicas ou científicas, como PubMed, os autores e suas 
colaborações podem ser modelados como um grafo. 
 
REFERÊNCIAS: 
 
“Conexões entre grafos e matrizes na modelagem de problemas 
matemáticos”, UFSM, 2018 : 
https://periodicos.ufsm.br/cienciaenatura/article/download/35519/19181/169091#:~:te
https://periodicos.ufsm.br/cienciaenatura/article/download/35519/19181/169091#:~:text=A%20teoria%20dos%20grafos%20%C3%A9,estudo%20exato%20em%20cada%20caso
6 
 
xt=A%20teoria%20dos%20grafos%20%C3%A9,estudo%20exato%20em%20cada%
20caso. 
“Grafos e Algoritmos”, Medium, 2020: https://medium.com/programadores-
ajudando-programadores/os-grafos-e-os-algoritmos-697c1fd4a416 
“Grafos. Introdução à Teoria dos Grafos. Programação, Matemática e 
Curiosidades.”, Youtube, 2021: https://www.youtube.com/watch?v=NNZ7jL1X2mI 
 
 
 
 
 
https://periodicos.ufsm.br/cienciaenatura/article/download/35519/19181/169091#:~:text=A%20teoria%20dos%20grafos%20%C3%A9,estudo%20exato%20em%20cada%20caso
https://periodicos.ufsm.br/cienciaenatura/article/download/35519/19181/169091#:~:text=A%20teoria%20dos%20grafos%20%C3%A9,estudo%20exato%20em%20cada%20caso
https://medium.com/programadores-ajudando-programadores/os-grafos-e-os-algoritmos-697c1fd4a416
https://medium.com/programadores-ajudando-programadores/os-grafos-e-os-algoritmos-697c1fd4a416
https://www.youtube.com/watch?v=NNZ7jL1X2mI