O que é um grafo: nós, arestas e graus
Monte um grafo com o mouse e veja ao vivo nós, arestas, graus, conexidade, ciclos e bipartição. Base para as demais aulas de grafos.
Trilha: Grafos
13 aulas e ferramentas, na ordem sugerida de estudo. Cada aula aparece depois dos seus pré-requisitos.
Comece por aqui
Ordem sugerida
O que é um grafo: nós, arestas e graus
Monte um grafo com o mouse e veja ao vivo nós, arestas, graus, conexidade, ciclos e bipartição. Base para as demais aulas de grafos.
A rede de conceitos deste site
O mapa de aulas como grafo real: aulas ligadas por conceitos em comum, com grau, proximidade e intermediação calculados a partir do índice do próprio build.
As pontes de Königsberg: grafos e o passeio de Euler
Ligue e desligue pontes, veja o grau de cada região e a classificação de Euler; construa um passeio clicando e descubra quando ele existe.
Busca em largura e em profundidade
Anime a busca em largura (BFS) e a busca em profundidade (DFS) passo a passo: fila ou pilha, níveis, árvore da busca e tempos de entrada e saída.
Árvore geradora mínima: Kruskal e Prim lado a lado
Compare Kruskal e Prim no mesmo grafo ponderado: as duas animações andam lado a lado e chegam ao mesmo peso total.
Caminho mínimo: Dijkstra com fila de prioridade
Anime o algoritmo de Dijkstra com a fila de prioridade visível, compare com Bellman-Ford e veja por que pesos negativos mudam o método.
Coloração de grafos: do mapa ao número cromático
Transforme um mapa de regiões em grafo, pinte os vértices com a coloração gulosa passo a passo e compare com o número cromático exato.
Editor de grafos com propriedades ao vivo
Crie grafos com o mouse ou pela matriz de adjacência, gere famílias clássicas e veja ao vivo ordem, graus, conexidade, bipartição, árvore, Euler e número cromático.
Grafos e matrizes: contando passeios
Veja como as potências da matriz de adjacência contam passeios entre vértices, e como os autovalores revelam a estrutura do grafo.
Caminhos de Euler e de Hamilton
Decida se existe percurso que passa por todas as arestas uma vez (Euler) ou por todos os vértices uma vez (Hamilton), e anime como Hierholzer e a busca constroem o caminho.
Fluxo máximo e corte mínimo
Anime o algoritmo de Edmonds-Karp numa rede com capacidades: caminhos aumentantes, gargalos e o corte mínimo que prova que o fluxo é máximo.
Grafos aleatórios G(n, p) e o limiar de conexidade
Sorteie grafos G(n, p) e veja ao vivo a probabilidade de ser conexo, o limiar ln(n)/n e a distribuição de graus comparada com a binomial.
O problema das quatro cores
Colorir mapas com vizinhos de cores diferentes: clique nas regiões, detecte conflitos e descubra o número cromático de mapas e grafos como K4 e K5.