Fórmulas Básicas de Matemática Discreta

Teoria dos Grafos

Teorema de Euler para Grafos Planos: V – E + F = 2 (Onde V é o número de vértices, E é o número de arestas, e F é o número de faces.)

Teorema do Grafo Bipartido: Um grafo é bipartido se e somente se não contém ciclos ímpares.

Combinatória

Princípio Fundamental da Contagem: Se há n formas de fazer uma coisa, e m formas de fazer outra, então há n × m formas de fazer ambas.

Permutações: P(n) = n!

Combinações: C(n, k) = n! / [k!(n-k)!]

Teoria dos Números

Algoritmo de Euclides (Máximo Divisor Comum): MDC(a, b) = MDC(b, a mod b) quando b ≠ 0

Lógica e Conjuntos

Leis de De Morgan: ¬(A ∨ B) = ¬A ∧ ¬B; ¬(A ∧ B) = ¬A ∨ ¬B

União de Conjuntos: A ∪ B

Interseção de Conjuntos: A ∩ B

Teoria da Computação

Complexidade de Tempo (Notação Big O): O(f(n))

Máquina de Turing: Modelo computacional para algoritmos.