Combinatoria y Teoría de Grafos

Combinatoria

• Principios Fundamentales:
  • Principio de Adición: Si una tarea se puede realizar de n₁ formas y otra de n₂ formas, y ambas son excluyentes, el total es n₁ + n₂.
  • Principio de Multiplicación: Si una tarea se descompone en etapas sucesivas que se pueden realizar de n₁, n₂, ..., nₖ formas, el total es n₁ × n₂ × ... × nₖ.
  • Principio de Distribución: Dados m elementos y n cajas, si la suma de elementos en las cajas es p, entonces al menos una caja tendrá más de p/n elementos.

Permutaciones, Variaciones y Combinaciones

• Permutaciones:

  • P(n) = n! (Permutaciones de n elementos sin repetición).

• Variaciones:

  • V(n, r) = n! / (n - r)! (Ordenar r elementos de un conjunto de n).

• Combinaciones:

  • C(n, r) = n! / (r! × (n - r)!) (Seleccionar r elementos de un conjunto de n, sin importar el orden).

• Combinaciones con repetición:

  • C'(n, r) = C(n + r - 1, r)

Teoría de Grafos

• Conceptos Fundamentales:

  • Grado de un vértice: Número de aristas que conectan a ese vértice.
  • Ciclo: Secuencia cerrada de aristas que no se repiten.
  • Conexo: Si existe un camino entre cualquier par de vértices.

• Grafos Eulerianos y Hamiltonianos:

  • Grafo Euleriano: Un grafo que contiene un ciclo que recorre cada arista exactamente una vez. Condición: todos los vértices deben tener grado par.
  • Grafo Hamiltoniano: Un grafo que contiene un ciclo que recorre cada vértice exactamente una vez. No existe un criterio general, pero se estudian condiciones específicas como la de Ore.

• Representación de Grafos por Matrices:

  • Matriz de Adyacencia: Matriz donde A[i][j] = 1 si existe una arista entre los vértices i y j, y 0 en caso contrario.
  • Matriz de Pesos: Matriz que almacena el peso de las aristas entre los vértices.

• Algoritmo de Dijkstra: Algoritmo para encontrar el camino más corto entre un vértice origen y todos los demás vértices.

Teoría de Números

• Algoritmo de Euclides: Algoritmo para calcular el máximo común divisor (MCD) de dos números.

• Teorema Fundamental de la Aritmética: Todo número entero positivo puede descomponerse de forma única como un producto de números primos.

• Congruencias:

  • Definición: a ≡ b (mod m), significa que a y b tienen el mismo resto cuando se dividen por m.
  • Operaciones: La suma y multiplicación de congruencias se pueden realizar directamente sobre los términos.
  • Teorema Chino del Resto: Se usa para resolver sistemas de congruencias.

Criterios de Divisibilidad

• Representación: n = Σ (aᵢ × 10ⁱ), donde aᵢ son los dígitos del número n.

• Ejemplos:

  • Por 3: n es divisible por 3 si la suma de sus dígitos es múltiplo de 3.
  • Por 11: n es divisible por 11 si la diferencia entre la suma de los dígitos en posiciones pares y la suma de los dígitos en posiciones impares es múltiplo de 11.

Ecuaciones Lineales de Ecuaciones Diofánticas

• Resolver ax + by = c:
  • Calcular el gcd(a, b).
  • Si gcd(a, b) | c, parametrizar las soluciones: x = x₀ + k(b/gcd(a,b)) y = y₀ - k(a/gcd(a,b))

Este cuestionario abarca principios fundamentales de combinatoria, incluyendo permutaciones, variaciones y combinaciones. También introduce conceptos clave en teoría de grafos, ofreciendo un marco para entender cómo organizar y seleccionar elementos. Perfecto para estudiantes de matemáticas o lógica computacional.