Ejercicios Resueltos de Matemáticas Discretas: Grafos, Recurrencias y Álgebra

Examen de Enero 2012: Problemas Resueltos de Matemáticas Discretas

Problemas de Desarrollo

Problema 1: Grafos y Combinatoria

1. Demuestre que el número de grafos distintos que se pueden formar con 200 vértices y 50 aristas es:

   

   La expresión C(200, 2) (o (200 sobre 2)) representa las selecciones no ordenadas de un conjunto de 200 elementos, tomados en grupos de 2 elementos. Esto define todas las posibles aristas en un grafo completo con 200 vértices.

   

   Luego, se aplica la misma lógica, pero cambiando 200 por el número total de aristas posibles (C(200, 2)) y 2 por 50 (que es el número de aristas a seleccionar). Así es como se definen todos los grafos con 50 aristas.

   Proponga un ejemplo con 4 vértices y 5 aristas.

   Número de grafos que se pueden formar:

2. Demuestre:

   Como hay dos casos posibles (tomando como ejemplo S(5,3), se pueden tener 2 conjuntos de 2 elementos y 1 de 1, o 1 de 3 elementos y 3 de 1 elemento), para obtener el número de posibilidades, habrá que aplicar la regla de la suma y sumar las maneras en que se puede obtener de la primera forma con las de la segunda.

   • De la primera forma: C(n,2) * C(n-2,2) / 2 (se divide por 2 porque se han elegido en el primer conjunto y se multiplica por 1/2, ya que, por ejemplo, pero se consideran las dos).
   • De la segunda forma: C(n,3) para el primer conjunto; el resto, al ser de 1 elemento, no se considera en el cálculo de combinaciones.

Problema 2: Relaciones de Recurrencia

1. Relación de recurrencia a_n, siendo esta el número de maneras en que se pueden usar 1 y 2 para formar n:

   Se observa que: a₁=1, a₂=2, a₃=3, a₄=5 y a₅=8. Esto sugiere la relación de recurrencia de Fibonacci: a_n = a_n-1 + a_n-2, con condiciones iniciales a₁=1, a₂=2. La ecuación característica es: p(x) = x² - x - 1 = 0.

   

   La solución general es: a_n = A · ((1 + √5) / 2)ⁿ + B · ((1 - √5) / 2)ⁿ.

   Para n=1 y n=2, se sustituyen los valores en la fórmula general para encontrar A y B. Se obtiene:

   • A = (3 + √5) / (7 + √5)
   • B = (1 - A · ((1 + √5) / 2)) / ((1 - √5) / 2)

   ¿Se deben sustituir A y B en la ecuación anterior para obtener la forma explícita de a_n?

2. Calcule el término general de la sucesión u₀=1, u₁=0, u₂=0, con la relación de recurrencia u_n+3 - 3u_n+1 - 2u_n = 0, para n ≥ 0:

   La ecuación característica es p(x) = x³ - 3x - 2 = 0. Aplicando la regla de Ruffini y resolviendo la ecuación de segundo grado resultante, se encuentran las raíces: x=2 y x=-1 (raíz doble).

   La solución general es: u_n = A · 2ⁿ + (Bn + C) · (-1)ⁿ.

   Para n=0, n=1 y n=2, se sustituyen los valores iniciales en la fórmula general. Se obtiene un sistema de ecuaciones:

   • Para n=0: u₀ = A · 2⁰ + (B·0 + C) · (-1)⁰ = A + C = 1
   • Para n=1: u₁ = A · 2¹ + (B·1 + C) · (-1)¹ = 2A - B - C = 0
   • Para n=2: u₂ = A · 2² + (B·2 + C) · (-1)² = 4A + 2B + C = 0

   Resolviendo el sistema:

   De la primera ecuación, C = 1 - A.

   Sustituyendo C en la segunda y tercera ecuaciones:

   • 2A - B - (1 - A) = 0 ⇒ 3A - B = 1
   • 4A + 2B + (1 - A) = 0 ⇒ 3A + 2B = -1

   Restando la primera de estas dos nuevas ecuaciones a la segunda: (3A + 2B) - (3A - B) = -1 - 1 ⇒ 3B = -2 ⇒ B = -2/3.

   Sustituyendo B en 3A - B = 1: 3A - (-2/3) = 1 ⇒ 3A + 2/3 = 1 ⇒ 3A = 1/3 ⇒ A = 1/9.

   Sustituyendo A en C = 1 - A: C = 1 - 1/9 = 8/9.

   Solución: u_n = (1/9) · 2ⁿ + (-2/3 · n + 8/9) · (-1)ⁿ. Para comprobar, se sustituyen n por 0, 1 y 2, y los resultados deberían ser 1, 0 y 0 respectivamente.

Cuestiones de Opción Múltiple

Cuestión 1: Conjuntos y Aplicaciones

Sean A y B conjuntos finitos de m y n elementos, respectivamente, y f: A → B una aplicación.

• 1. Si m=n, entonces f es biyectiva. [Falso]
• 2. Si f es inyectiva, entonces m ≤ n. [Verdadero]
• 3. Si f es inyectiva, entonces m ≤ n. [Verdadero]
• 4. Si m ≥ n y f es inyectiva, entonces f es biyectiva. [Verdadero]

Cuestión 2: Cantidad de Divisores

Para determinar la cantidad de divisores que tiene el número a = 2⁶ · 3¹⁰ · 5³ · 7⁶, basta hallar la cantidad de elementos del conjunto:

• 4. { (α, β, γ, δ) : 0 ≤ α ≤ 6, 0 ≤ β ≤ 10, 0 ≤ γ ≤ 3, 0 ≤ δ ≤ 6 }. [Verdadero]

Todas las opciones son correctas (asumiendo que solo se muestra la opción correcta).

Cuestión 3: Grafos Distintos

Número de grafos distintos que se pueden formar con 200 vértices y 50 aristas:

• 1. C(C(200,2), 50). [Verdadero]

Cuestión 4: Particiones de Conjuntos

Sea A = {a₁, ..., a₁₀} un conjunto y P = {P₁, P₂, P₃, P₄} una partición de A donde cada P_i tiene i elementos.

• 1. P origina 4! aplicaciones suprayectivas distintas de A en el conjunto {1,2,3,4}. [Verdadero]
• 2. El número de particiones distintas de A con las características de P es . [Falso]
• 4. P origina 10! aplicaciones suprayectivas distintas de A en el conjunto {1,2,...,10}. [Falso]

Cuestión 5: Sucesión de Fibonacci

La sucesión de Fibonacci satisface: (a_n+2 - a_n+1 - a_n = 0). Esta es una relación de recurrencia de orden 2. Si en lugar de un 0 hubiera un 1 o cualquier otro valor, dejaría de ser homogénea.

• 1. Una recurrencia lineal con coeficientes constantes de orden 1. [Falso]
• 2. Una recurrencia lineal homogénea de orden 1. [Falso]
• 3. Una recurrencia lineal homogénea de orden 2. [Verdadero]
• 4. Una recurrencia lineal con coeficientes constantes de orden 2. [Verdadero]

Cuestión 6: Anillo de Series de Potencias

En el anillo de series de potencias Z₅[[x]]:

• 1. Los únicos elementos invertibles son 1, 2, 3 y 4. [Falso] (Por ejemplo, 1+x también tiene inverso, así como 4+x+x²+2x³, ya que su término constante es invertible en Z₅).
• 2. La serie 1+x+x²+x³+x³+... no tiene inverso. [Falso] (El término constante es 1, que es invertible en Z₅).
• 3. La serie x+x²+x³+x³+... tiene inverso. [Falso] (El término constante es 0, que no es invertible en Z₅).
• 4. Si un elemento 'a' tiene inverso, entonces a²+1 o a²+4 no tiene inverso. [Verdadero] (Si el término constante de 'a' es 'c', entonces el término constante de a² es c². En Z₅, c² puede ser 1 o 4. Si c²=1, entonces c²+4 = 1+4 = 0 (mod 5), por lo que a²+4 no es invertible. Si c²=4, entonces c²+1 = 4+1 = 0 (mod 5), por lo que a²+1 no es invertible. Por lo tanto, uno de ellos siempre tendrá un término constante de 0, haciéndolo no invertible).

Cuestión 7: Grafos Completos y Árboles

En un grafo completo K_n con n ≥ 3:

• 1. Siempre es posible encontrar un subgrafo cíclico C_n. [Verdadero]
• 4. Existen árboles con sucesiones de grados (1,1,...,1) y (n-1,1,...,1). [Falso] (Un árbol con n vértices y sucesión de grados (1,1,...,1) solo existe para n=2. Un árbol con sucesión de grados (n-1,1,...,1) es un grafo estrella, que sí existe).

Cuestión 9: Isomorfismo de Grafos

Sean G₁=(V₁, A₁) y G₂=(V₂, A₂) dos grafos con |V₁| = |V₂| = 6:

• 1. Si G₁ tiene un subgrafo isomorfo a C₃ y G₂ no lo tiene, entonces G₁ y G₂ no son isomorfos. [Verdadero]
• 2. Si |A₁|=|A₂|=6, y las sucesiones de grados de los grafos son en ambos casos (2,2,2,2,2,2), G₁ y G₂ son isomorfos. [Falso] (Por ejemplo, un ciclo C₆ y dos ciclos C₃ disjuntos tienen las mismas propiedades pero no son isomorfos).
• 3. Si G₁ y G₂ son isomorfos, entonces |A₁|=|A₂| y el número de vértices es el mismo. [Verdadero]
• 4. Si |A₁|=|A₂|, entonces G₁ y G₂ son isomorfos. [Falso] (Dos grafos pueden tener el mismo número de aristas pero estructuras diferentes, por ejemplo, un camino P₄ y un grafo estrella K_1,3).

Cuestión 10: Anillo de Polinomios Z₃[x]

En el anillo de polinomios Z₃[x]:

• 1. x^{3^4} - x tiene factores irreducibles de grado 4. [Verdadero]
• 2. x⁸⁰ - 1 tiene factores irreducibles de grado 4. [Verdadero]
• 3. x^{3^4} - x tiene factores irreducibles de grado 3. [Falso] (Porque 3 no es divisor de 4).
• 4. x²+1 es factor de x⁸⁰-1. [Verdadero] (Es un polinomio de grado 2, irreducible y mónico en Z₃[x]. Las raíces de x²+1 son tales que su cuadrado es -1. Como (-1)⁴⁰ = 1, las raíces de x²+1 son también raíces de x⁸⁰-1).

Notas adicionales:

• x es factor de x⁸¹-x.
• x no es factor de x⁸⁰-1.