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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
Qual é o coeficiente de um termo na expansão de um binômio elevado à décima potência? O Binômio de Newton responde em uma linha, com os coeficientes do Triângulo de Pascal. Veremos o teorema e sua prova por indução, a fórmula do termo geral e as identidades que saem de casos particulares.
Um conjunto de 10 elementos tem 1.024 subconjuntos, e essa é a soma da linha 10 do Triângulo de Pascal. Veremos as identidades dos coeficientes binomiais: simetria, relação de Pascal (Stifel) e os teoremas das linhas, das colunas e das diagonais.
Numa sorveteria com 7 sabores, há 210 formas de pedir 4 bolas, podendo repetir sabor. Chegamos a esse número com o método das estrelas e barras, que mostra que escolher com repetição, distribuir bolas em caixas e resolver equações inteiras são o mesmo problema.
Uma senha de 4 dígitos aceita repetição, e por isso há 10.000 delas, dez opções em cada uma das quatro posições. O arranjo com repetição conta senhas, placas e cores RGB, e mostra quantos padrões cabem nos 32 bits de um float e nos registradores de uma calculadora HP-11C.
Quantos anagramas tem a palavra MAMBEMBE? Menos do que teria uma palavra de 8 letras distintas, porque trocar duas letras iguais não cria um anagrama novo. A fórmula desconta as repetições dividindo por fatoriais, e vale para sequências binárias e para caminhos mínimos em grades.
De 10 amigos, 3 vão comprar as pipocas. Importa só quem vai, e não a ordem da escolha, e por isso são 120 grupos possíveis. Veremos a fórmula da combinação simples, sua simetria, o método do complemento e a divisão de um conjunto em grupos.
Numa corrida com 10 atletas, o pódio pode ser preenchido de 720 formas. Esse é um arranjo simples, a seleção ordenada de alguns elementos de um conjunto. Resolvemos problemas de rotas, placas de veículos e números com algarismos distintos, com Python e SQL.
Quantos anagramas tem a palavra VIRUS? De quantas formas 5 amigos se sentam em volta de uma mesa? São 120 e 24, pela permutação simples e pela circular. Veremos também restrições de adjacência, o problema do caixeiro-viajante e os desarranjos.
Com 4 livros de matemática e 3 de português, há 7 formas de escolher um livro e 12 de escolher um de cada. A primeira conta é uma soma e a segunda, um produto: são os princípios aditivo e multiplicativo, aplicados aqui a senhas, bandeiras, gabaritos e contagem de divisores.
Quantas senhas de 8 caracteres existem? De quantas formas 10 pessoas se sentam ao redor de uma mesa? A combinatória responde sem enumerar caso a caso. Este é o roteiro da série: dos princípios de contagem a permutações, arranjos, combinações e Binômio de Newton.
Quantos movimentos resolvem a Torre de Hanói? A resposta sai de uma relação de recorrência, que escreve o problema em função dele mesmo com um disco a menos. Montamos recorrências e as resolvemos por substituição, pela equação característica e pelo Teorema Mestre, usado no merge sort.
E quando o passo depende de mais de um caso anterior, como em Fibonacci? A indução forte assume todos os casos anteriores. Veremos a técnica na decomposição em primos, na barra de chocolate, no franqueio postal e na fórmula de Binet, que em ponto flutuante erra a partir do 71º termo.
Se o primeiro dominó cai e cada dominó derruba o seguinte, todos caem. Essa é a lógica do Princípio de Indução Matemática. Veremos a estrutura da prova (base, hipótese e passo) em somas, divisibilidade e desigualdades, e a falsa prova de que todos os cavalos têm a mesma cor.
Como provar que uma fórmula vale para todos os números naturais, se eles são infinitos? Com a indução matemática. Esta apresentação mostra o caminho da série: indução clássica, indução forte e relações de recorrência, de Fibonacci à Torre de Hanói.
Somar o tamanho de dois conjuntos conta a interseção duas vezes. O Princípio da Inclusão-Exclusão corrige a conta, para dois, três ou qualquer número de conjuntos. Veremos também infinitos de tamanhos diferentes, desarranjos e o Crivo de Eratóstenes.
União, interseção, diferença e complemento são as operações básicas entre conjuntos, e aparecem no SQL como UNION, INTERSECT e EXCEPT. Vemos cada uma em diagramas de Venn, as leis de De Morgan e a distributividade, e a diferença entre diagrama de Venn e de Euler.
A coleção das pessoas altas não é um conjunto: falta um critério que decida, para qualquer pessoa, se ela pertence ou não. Definimos conjunto, pertinência, descrição por extensão e por compreensão, igualdade, inclusão e o conjunto das partes.
De quantas maneiras se escolhe uma senha válida? Qual o caminho mais curto entre duas cidades? São perguntas de matemática discreta. Este roteiro apresenta as quatro séries do site sobre o tema: conjuntos, indução e recorrência, combinatória e grafos, com 28 artigos.
