Matemática Discreta

Gancho: "A matemática discreta lida com valores separados e distintos. É a matemática da ciência da computação."

---

A Matemática dos Computadores

A combinatória tem raízes antigas. Matemáticos indianos estudaram permutações e combinações. Matemáticos chineses desenvolveram o Triângulo de Pascal (Triângulo de Yang Hui, 1303 d.C.) antes de Pascal. Jogos de areia africanos codificam pensamento combinatório.

---

Objetivos de Aprendizagem

Ao final desta lição, você será capaz de:

• Compreender conjuntos e lógica
• Aplicar princípios de contagem
• Explorar teoria dos grafos
• Conectar com ciência da computação

---

1. Conjuntos e Lógica

Notação de Conjunto

$$A = \{1, 2, 3\}$$

Elemento: 1 ∈ A Subconjunto: B ⊂ A

União e Interseção

$$A \cup B = \{x : x \in A \text{ ou } x \in B\}$$ $$A \cap B = \{x : x \in A \text{ e } x \in B\}$$

Operadores Lógicos

• E (∧): Verdadeiro se ambos verdadeiros
• Ou (∨): Verdadeiro se pelo menos um verdadeiro
• Não (¬): Inverte valor
• Se...então (→): Falso apenas se T → F

---

2. Combinatória

Permutações

Arranjos: Ordem importa

$$P(n,r) = \frac{n!}{(n-r)!}$$

Combinações

Combinações: Ordem não importa

$$C(n,r) = \binom{n}{r} = \frac{n!}{r!(n-r)!}$$

Teorema Binomial

$$(a+b)^n = \sum_{k=0}^{n} \binom{n}{k} a^{n-k} b^k$$

---

3. Teoria dos Grafos

Vértices e Arestas

Grafo: G = (V, E) onde V são vértices e E são arestas

Caminhos e Ciclos

Caminho: Sequência de vértices conectados Ciclo: Caminho que começa e termina no mesmo vértice

Pontes de Königsberg

Euler (1736) provou que não é possível cruzar todas as pontes uma única vez — nascimento da teoria dos grafos.

---

4. Exercícios Interativos

Calculadora de Conjuntos

Ferramenta de Contagem

Explorador de Grafos

---

Aplicação no Mundo Real

Ciência da Computação, Redes e Programação

Ciência da Computação:

• Algoritmos usam grafos
• Árvores de decisão
• Grafos de dependência

Redes:

• Roteamento (grafos)
• Topologia de redes
• Análise de redes sociais

Programação:

• Estruturas de dados (árvores, grafos)
• Lógica booleana
• Otimização

---

---

5. Exemplos Resolvidos: Permutacoes e Combinacoes

Exemplo 1 — Arranjos (Permutacoes)

Problema: De quantas maneiras 5 pessoas podem se sentar em uma fila de 5 cadeiras?

Passo 1: A ordem importa — e uma permutacao: $P(5,5) = \frac{5!}{(5-5)!} = \frac{5!}{0!} = \frac{120}{1} = 120$

Interpretacao: Existem 120 maneiras de ordenar 5 pessoas.

---

Exemplo 2 — Arranjos com Repeticao Proibida

Problema: Um comite de 3 pessoas deve ser escolhido de 8 candidatos, com cargos distintos (presidente, vice, secretario). Quantas escolhas sao possiveis?

Passo 1: A ordem importa (cargos sao diferentes): $P(8,3) = \frac{8!}{(8-3)!} = \frac{8!}{5!} = 8 \times 7 \times 6 = 336$

Interpretacao: Existem 336 maneiras de escolher e nomear o comite.

---

Exemplo 3 — Combinacoes

Problema: De quantas maneiras podemos escolher 4 frutas de um total de 10?

Passo 1: A ordem NAO importa — e uma combinacao: $C(10,4) = \binom{10}{4} = \frac{10!}{4! \cdot 6!}$

Passo 2: Calcule: $= \frac{10 \times 9 \times 8 \times 7}{4 \times 3 \times 2 \times 1} = \frac{5040}{24} = 210$

Interpretacao: Existem 210 maneiras de escolher 4 frutas de 10.

---

Exemplo 4 — Principio da Adicao vs. Multiplicacao

Problema: Um aluno tem 3 camisas, 2 calcas e 2 pares de sapatos. Quantos trajes diferentes pode usar?

Passo 1: Para cada escolha de camisa, pode combinar com qualquer calca e qualquer sapato — e o principio da multiplicacao: $3 \times 2 \times 2 = 12 \text{ trajes}$

Passo 2: Se o aluno pudesse usar camisa ou camiseta (3 + 2 = 5 opcoes de topo), ai seria o principio da adicao.

---

Exemplo 5 — Permutacoes com Elementos Repetidos

Problema: Quantas anagramas tem a palavra "BANANA"?

Passo 1: A palavra tem 6 letras, mas com repeticoes:

• B: 1 vez
• A: 3 vezes
• N: 2 vezes

Passo 2: Use a formula de permutacoes com repeticao: $\frac{n!}{n_1! \cdot n_2! \cdot n_3!} = \frac{6!}{1! \cdot 3! \cdot 2!} = \frac{720}{1 \times 6 \times 2} = \frac{720}{12} = 60$

Interpretacao: Existem 60 anagramas da palavra "BANANA".

---

Exemplo 6 — Teorema Binomial

Problema: Expanda $(x + 2)^4$ usando o Teorema Binomial.

Passo 1: Aplique a formula $(a+b)^n = \displaystyle\sum_{k=0}^{n} \binom{n}{k} a^{n-k} b^k$:

$(x+2)^4 = \binom{4}{0}x^4 \cdot 2^0 + \binom{4}{1}x^3 \cdot 2^1 + \binom{4}{2}x^2 \cdot 2^2 + \binom{4}{3}x^1 \cdot 2^3 + \binom{4}{4}x^0 \cdot 2^4$

Passo 2: Calcule cada termo: $= 1 \cdot x^4 + 4 \cdot x^3 \cdot 2 + 6 \cdot x^2 \cdot 4 + 4 \cdot x \cdot 8 + 1 \cdot 16$

$= x^4 + 8x^3 + 24x^2 + 32x + 16$

---

6. Matrizes de Adjacencia

O que e uma Matriz de Adjacencia

A matriz de adjacencia $A$ de um grafo $G = (V, E)$ e uma matriz $n \times n$ onde:

$A_{ij} = \begin{cases} 1 & \text{se existe aresta de } i \text{ para } j \\ 0 & \text{caso contrario} \end{cases}$

Exemplo 1 — Grafo Simples

Problema: Considere um grafo com 4 vertices (A, B, C, D) e arestas: A-B, A-C, B-C, C-D. Construa a matriz de adjacencia.

Solucao:

Propriedades:

• A matriz e simetrica para grafos nao-direcionados
• A diagonal principal e zero (sem lacos)
• A soma de cada linha e o grau do vertice

---

Exemplo 2 — Matriz de Adjacencia e Caminhos

Problema: Usando a matriz acima, quantos caminhos de comprimento 2 existem de A para C?

Solucao: O numero de caminhos de comprimento 2 de $i$ para $j$ e o elemento $(i,j)$ da matriz $A^2$:

$A^2 = A \times A$

Elemento $(A, C)$ de $A^2$: $(A^2)_{AC} = (A_{AA} \cdot A_{AC}) + (A_{AB} \cdot A_{BC}) + (A_{AC} \cdot A_{CC}) + (A_{AD} \cdot A_{DC})$ $= (0 \cdot 1) + (1 \cdot 1) + (1 \cdot 0) + (0 \cdot 1) = 1$

Existem 1 caminho de comprimento 2 de A para C (A -> B -> C). Note que A -> A -> C nao conta porque A nao tem laco.

---

7. Coloracao de Grafos

O que e Coloracao

Coloracao de vertices e atribuir cores aos vertices de um grafo de modo que vertices adjacentes tenham cores diferentes. O menor numero de cores necessario e chamado de numero cromatico, $\chi(G)$.

Exemplo 1 — Coloracao de um Ciclo

Problema: Qual e o numero cromatico de $C_4$ (ciclo em 4 vertices)?

Solucao:

• Vertices: A-B-C-D-A
• Precisamos de pelo menos 2 cores (pois ha arestas)
• Com 2 cores: A=vermelho, B=azul, C=vermelho, D=azul. Funciona!

$\chi(C_4) = 2$ (ciclos pares sao 2-coloriveis)

---

Exemplo 2 — Coloracao de $K_4$

Problema: Qual e o numero cromatico de $K_4$ (grafo completo em 4 vertices)?

Solucao: Em $K_4$, todos os vertices sao adjacentes entre si. Portanto, cada vertice precisa de uma cor diferente.

$\chi(K_4) = 4$

---

Exemplo 3 — Aplicacao: Mapas e o Teorema das 4 Cores

Problema: Por que 4 cores sao suficientes para colorir qualquer mapa plano?

O Teorema das 4 Cores (provado em 1976) afirma que qualquer mapa plano pode ser colorido com no maximo 4 cores. Isto e uma aplicacao direta de coloracao de grafos ao mundo real — cada pais e um vertice e fronteiras sao arestas.

---

8. Caminhos Eulerianos e Hamiltonianos

Caminho Euleriano

Um caminho euleriano passa por todas as arestas exatamente uma vez.

Teorema de Euler: Um grafo conexo tem caminho euleriano se e somente se tem exatamente 0 ou 2 vertices de grau impar.

Exemplo 1 — As Pontes de Konigsberg (Revisitado)

Problema: Por que nao existe caminho euleriano em Konigsberg?

Analise: O grafo de Konigsberg tem 4 vertices com graus 3, 3, 3, 3 (todos impares). Para existir caminho euleriano, precisamos de exatamente 0 ou 2 vertices de grau impar. Com 4 vertices impares, nao existe caminho euleriano.

---

Caminho Hamiltoniano

Um caminho hamiltoniano passa por todos os vertices exatamente uma vez.

Exemplo 2 — Problema do Caixeiro Viajante

Problema: Um caixeiro viajante deve visitar 4 cidades (A, B, C, D) retornando a origem. Se as distancias sao: AB=10, AC=15, AD=20, BC=35, BD=25, CD=30. Qual e o menor circuito?

Solucao: Teste todos os circuitos possiveis (existe um algoritmo):

• A->B->C->D->A: 10+35+30+20 = 95
• A->B->D->C->A: 10+25+30+15 = 80 <- menor
• A->C->B->D->A: 15+35+25+20 = 95

O menor circuito e A->B->D->C->A com comprimento 80.

---

Exemplo 3 — Diferencas entre Euleriano e Hamiltoniano

---

9. Erros Comuns em Matematica Discreta

---

10. Exercicios Interativos Adicionais

Arraste os Principios de Contagem

Preencha os Espacos: Conceitos de Grafos

---

11. Permutacoes e Combinacoes — Exemplos Detalhados

Permutacao: P(5,3) = 60

Problema: De quantas maneiras podemos ordenar 3 elementos escolhidos de um conjunto de 5?

Formula: $P(n,r) = \frac{n!}{(n-r)!}$

Passo 1: Substitua $n = 5$ e $r = 3$: $P(5,3) = \frac{5!}{(5-3)!} = \frac{5!}{2!}$

Passo 2: Calcule os fatoriais: $5! = 5 \times 4 \times 3 \times 2 \times 1 = 120$ $2! = 2 \times 1 = 2$

Passo 3: Divida: $P(5,3) = \frac{120}{2} = 60$

Interpretacao: Existem 60 maneiras de escolher e ordenar 3 itens de um conjunto de 5. Por exemplo, escolher presidente, vice e secretario de um grupo de 5 pessoas.

---

Combinacao: C(8,3) = 56

Problema: De quantas maneiras podemos escolher 3 elementos de um conjunto de 8, sem importar a ordem?

Formula: $C(n,r) = \binom{n}{r} = \frac{n!}{r!(n-r)!}$

Passo 1: Substitua $n = 8$ e $r = 3$: $C(8,3) = \frac{8!}{3!(8-3)!} = \frac{8!}{3! \cdot 5!}$

Passo 2: Calcule: $8! = 40320, \quad 3! = 6, \quad 5! = 120$

$C(8,3) = \frac{40320}{6 \times 120} = \frac{40320}{720} = 56$

Atalho: Tambem podemos calcular diretamente: $C(8,3) = \frac{8 \times 7 \times 6}{3 \times 2 \times 1} = \frac{336}{6} = 56$

Interpretacao: Existem 56 maneiras de escolher 3 itens de 8, onde a ordem nao importa. Por exemplo, escolher 3 livros de uma estante de 8.

---

12. Teorema Binomial — Exemplo Paso a Paso

Expansao de (x+2)³

Problema: Expanda $(x + 2)^3$ usando o Teorema Binomial.

Formula: $(a+b)^n = \sum_{k=0}^{n} \binom{n}{k} a^{n-k} b^k$

Passo 1: Identifique $a = x$, $b = 2$, $n = 3$. Calcule os coeficientes binomiais:

• $\binom{3}{0} = 1$
• $\binom{3}{1} = 3$
• $\binom{3}{2} = 3$
• $\binom{3}{3} = 1$

Passo 2: Escreva cada termo: $(x+2)^3 = \binom{3}{0}x^3 \cdot 2^0 + \binom{3}{1}x^2 \cdot 2^1 + \binom{3}{2}x^1 \cdot 2^2 + \binom{3}{3}x^0 \cdot 2^3$

Passo 3: Simplifique: $= 1 \cdot x^3 \cdot 1 + 3 \cdot x^2 \cdot 2 + 3 \cdot x \cdot 4 + 1 \cdot 1 \cdot 8$

$= x^3 + 6x^2 + 12x + 8$

Verificacao: $(x+2)^3 = (x+2)(x+2)(x+2) = (x^2+4x+4)(x+2) = x^3+2x^2+4x^2+8x+4x+8 = x^3+6x^2+12x+8$ ✓

---

13. Matriz de Adjacencia — Exemplo Completo

Construcao para um Grafo Simples

Problema: Considere um grafo com 4 vertices (A, B, C, D) e arestas: A-B, A-C, B-C, C-D. Construa a matriz de adjacencia e interprete.

Solucao:

Propriedades importantes:

• A matriz e simetrica ($A_{ij} = A_{ji}$) porque o grafo e nao-direcionado
• A diagonal principal e toda zero (sem lacos)
• A soma de cada linha indica o grau do vertice:
  • Grau(A) = 0+1+1+0 = 2
  • Grau(B) = 1+0+1+0 = 2
  • Grau(C) = 1+1+0+1 = 3
  • Grau(D) = 0+0+1+0 = 1

Uso pratico: A matriz de adjacencia e armazenada em computadores para representar grafos em algoritmos de roteamento, redes sociais e analise de grafos.

---

14. Coloracao de Grafos — Exemplo Aplicado

Coloracao de um Mapa Simples

Problema: Considere um mapa com 4 regioes: A (canto superior esquerdo), B (canto superior direito), C (canto inferior esquerdo), D (canto inferior direito). A e adjacente a B e C. B e adjacente a A e D. C e adjacente a A e D. D e adjacente a B e C. Qual e o numero cromatico?

Solucao:

Passo 1: Identifique as adjacencias:

• A: vizinhos B, C
• B: vizinhos A, D
• C: vizinhos A, D
• D: vizinhos B, C

Passo 2: Tente colorir com o menor numero de cores:

• A = vermelho
• B = azul (adjacente a A)
• C = azul (adjacente a A, mas nao a B)
• D = vermelho (adjacente a B e C, mas nao a A)

Resultado: $\chi(G) = 2$ — basta 2 cores!

Conexao com o Teorema das 4 Cores: O Teorema das 4 Cores (1976) garante que qualquer mapa plano pode ser colorido com no maximo 4 cores. No nosso exemplo, 2 cores ja bastam, mas grafos mais complexos podem necessitar de 3 ou 4.

---

15. Exercicios: Combinatoria e Grafos

Practice Questions

---

• Conjuntos são a base da matemática discreta
• Permutações e combinatória contam arranjos
• Teoria dos grafos estuda conectividade
• Matemática discreta é a base da ciência da computação
• Euler fundou teoria dos grafos resolvendo pontes de Königsberg