Teoria dos Grafos
Professor(a): Diego Saqui
Mapa Conceitual
Resumo
"Teoria dos Grafos" é uma disciplina fundamental na Ciência da Computação que estuda as propriedades, representações e algoritmos relacionados a estruturas gráficas. Grafos são representações abstratas de conexões entre entidades, compostos por vértices (ou nós) conectados por arestas (ou conexões). Essa disciplina explora conceitos como tipos de grafos (dirigidos, não-direcionados, ponderados), algoritmos de busca (como busca em largura e busca em profundidade), algoritmos de caminho mínimo, algoritmos de árvore geradora mínima (como algoritmo de Prim e algoritmo de Kruskal), entre outros. A Teoria dos Grafos é amplamente aplicada em áreas como redes de computadores, análise de algoritmos, modelagem de sistemas, planejamento de rotas, e diversas outras áreas onde a relação entre elementos pode ser representada por meio de conexões.
Conceitos Importantes
Grafos
Estrutura matemática que consiste em um conjunto de vértices (pontos ou nós) conectados por arestas (linhas ou conexões). Essa representação abstrata é utilizada para modelar relacionamentos entre entidades, onde os vértices representam os elementos e as arestas indicam as relações entre esses elementos. Os grafos podem ser direcionados (quando as arestas têm uma direção) ou não-direcionados (quando as conexões são bidirecionais), e podem incluir pesos para representar custos ou valores associados às conexões. Essa estrutura é fundamental para a resolução de problemas de otimização, redes, algoritmos de caminho e diversas outras aplicações computacionais.
Exemplo de Grafo
Árvores
Tipo especial de grafo sem ciclos, formado por vértices conectados de modo que exista um único caminho entre quaisquer dois vértices. Ela é um grafo conexo, ou seja, todos os vértices estão interligados, e não possui ciclos, o que significa que não há caminhos fechados. Além disso, uma árvore com n vértices sempre terá n−1 arestas. As árvores são fundamentais na modelagem de hierarquias, estruturas de dados como árvores binárias, algoritmos de busca e na resolução de problemas em diversas áreas, como computação, biologia, redes e otimização.
Exemplo de Árvore
Materiais de Estudo
Vídeos:
- Aula 01 – Introdução e Propriedades
- Aula 02 – Classes de Grafos
- Aula 03 – Passeios, trilhas e caminhos
- Aula 04 – Representações computacionais de grafos
- Aula 05 – Manipulação de Grafos com Python e Networx
- Aula 06 – Isomorfismo
- Aula 07 – Conectividade em Grafos e Métricas
- Aula 08 – Passeios em Grafos Conexos, Random Walks e Cadeias de Markov –Parte 01
- Aula 09 – Passeios em Grafos Conexos, Random Walks e Cadeias de Markov – Parte 02
- Aula 10 – Page Rank
- Aula 11 – Árvores
- Aula 12 – Árvores Spanning e código de Prüfer
- Aula 13 – Algoritmo de Kruskal
- Aula 15 - Busca em Largura
- Aula 16 – Busca em Largura – Algoritmo Backtracking
- Aula 17 – Busca em Profundidade
- Aula 18 – Ordenação Topológica
- Aula 19 - Algoritmo de Dijkstra
- Aula 21- Heurística AStar
PDFs/Slides:
- Aula 01 – Introdução e Propriedades
- Aula 02 – Classes de Grafos
- Aula 03 – Passeios, trilhas e caminhos
- Aula 04 – Representações computacionais de grafos
- Aula 05 – Manipulação de Grafos com Python e Networx
- Aula 06 – Isomorfismo
- Aula 07 – Conectividade em Grafos e Métricas
- Aula 08 – Passeios em Grafos Conexos, Random Walks e Cadeias de Markov –Parte 01
- Aula 09 – Passeios em Grafos Conexos, Random Walks e Cadeias de Markov – Parte 02
- Aula 10 – Page Rank
- Aula 11 – Árvores
- Aula 12 – Árvores Spanning e código de Prüfer
- Aula 13 – Algoritmo de Kruskal
- Aula 15 - Busca em Largura
- Aula 16 – Busca em Largura – Algoritmo Backtracking
- Aula 17 – Busca em Profundidade
- Aula 18 – Ordenação Topológica
- Aula 19 - Algoritmo de Dijkstra
- Aula 21- Heurística AStar
Complementares:
Atividades
Lista de Exercícios:
Colab
Seção voltada para a colaboração entre os alunos.
Links abertos com resumos, anotações e materiais de revisão.