Uma introdução completa à Teoria dos Grafos: das Pontes de Königsberg aos grafos
direcionados. Aprenda a matemática que está por trás das redes, algoritmos e
conexões do mundo digital — grau, isomorfismo, caminhos, árvores, planaridade e mais.
Os artigos são listados abaixo, na ordem em que foram escritos.
Em 1736, Euler resolveu um quebra-cabeça sobre as pontes de uma cidade prussiana e fundou, sem querer, a teoria dos grafos. Esta série de 9 artigos vai das definições básicas ao Teorema de Kuratowski, passando por caminhos, árvores, planaridade e grafos direcionados.
Dá para cruzar as sete pontes de Königsberg passando uma única vez por cada uma? Euler mostrou que não, e criou a teoria dos grafos. Veremos o que é um grafo, o Teorema das Quatro Cores e o cálculo do PageRank numa mini-web de cinco páginas, em Python.
O vocabulário formal da teoria dos grafos: vértices, arestas, vizinhança, vértice isolado e universal, complemento, subgrafos induzidos e geradores, grafos completos e nulos, cliques e conjuntos independentes, com 14 exemplos e exercícios resolvidos.
A soma dos graus de um grafo é sempre o dobro do número de arestas: é o Teorema do Aperto de Mãos. Veremos grau, grafos regulares e sequência de graus, e conferimos o teorema no Karate Club de Zachary, uma rede real de 34 pessoas que se dividiu em duas.
Dois grafos com o mesmo número de vértices, de arestas e a mesma sequência de graus podem não ser isomorfos. Veremos o que é isomorfismo, como prová-lo com uma bijeção e como representar grafos por matrizes de adjacência e de incidência.
Como saber se dois pontos de uma rede estão conectados, e por qual caminho mais curto? Definimos passeio, trajeto, caminho e ciclo, conexidade e distância, calculamos distâncias com a busca em largura e Dijkstra e provamos que um grafo é bipartido se e só se não tem ciclo ímpar.
Um sistema de arquivos é uma árvore: um grafo conexo e sem ciclos. Provamos que toda árvore tem uma aresta a menos que o número de vértices e que seu centro tem um ou dois vértices, e vemos árvores geradoras e enraizadas, com a diferença entre uma árvore balanceada e uma degenerada.
Percorrer cada aresta uma única vez é fácil de decidir: basta olhar a paridade dos graus (Teorema de Euler). Decidir se dá para visitar cada vértice uma única vez é NP-completo. Veremos os dois problemas, os teoremas de Dirac e Ore e o Caixeiro Viajante, de Held-Karp a Christofides.
Tente ligar três casas a gás, água e luz sem cruzar linhas: é impossível. Veremos por quê, com a Fórmula de Euler, a prova de que o grafo das três casas e o completo de cinco vértices não são planares, o Teorema de Kuratowski e a coloração de grafos planares, das seis às quatro cores.
Rua de mão única, hyperlink e dependência entre tarefas são relações com sentido, e para elas existem os grafos direcionados. Veremos graus de entrada e saída, conexidade forte, unilateral e fraca, matrizes, DAGs e a ordenação topológica que o Apache Airflow usa.
