UNIVERSIDAD MARIANO GÁLVEZ DE GUATEMALA FACULTAD

DE INGENIERÍA EN SISTEMAS DE INFORMACIÓN PLAN FIN DE

SEMANA SECCIÓN: B
CURSO:MATEMÁTICA DISCRETA CATEDRÁTICO TITULAR: ING.
FRANCO NERY LOPEZ MEJIA

TAREAS # 2

0900-24-3836
Luis Arturo Rodriguez Carrillo
Guatemala, 12 de Octubre de 2024
ECUACIONES DIOFÁNTICAS

1. DEFINICIÓN

Una ecuación diofántica es una ecuación polinómica con dos o más variables en la que se busca encontrar soluciones enteras.
Es decir, los valores de las incógnitas deben ser números enteros. El nombre proviene del matemático griego Diofanto de X
Alejandría, quien estudió este tipo de ecuaciones en la antigüedad. Un ejemplo común es la ecuación de la forma ax + by
= c, donde a, b y c son números enteros conocidos.

2. TIPOS DE ECUACIONES DIOFÁNTICAS

ECUACIÓN DIOFÁNTICA LINEAL

Es la forma más simple de una ecuación diofántica, que tiene la estructura ax + by = c. Aquí, a, b y c son enteros, y el objetivo es
encontrar soluciones enteras para x y y. La ecuación tiene soluciones enteras si y solo si el máximo común divisor (mcd) de a y b
divide a c.

ECUACIÓN DIOFÁNTICA CUADRÁTICA (PITAGÓRICAS)

Este tipo incluye ecuaciones de la forma x² + y² = z², conocidas como ternas pitagóricas. Son soluciones enteras relacionadas
con los triángulos rectángulos cuyos lados tienen longitudes enteras.

ECUACIONES DIOFÁNTICAS EXPONENCIALES

Estas ecuaciones involucran potencias de las variables. Un ejemplo es la Ecuación de Fermat: x^n + y^n = z^n, donde n > 2. El
Último Teorema de Fermat establece que no hay soluciones enteras para n mayor que 2.
Ecuación Diofántica de Pell:
Este tipo de ecuación es de la forma x² - Ny² = 1, donde N es un entero positivo que no es un cuadrado perfecto. Es un ejemplo
clave en la teoría de números.

MÉTODOS DE RESOLUCIÓN

ALGORITMO DE EUCLIDES

Se usa para resolver ecuaciones diofánticas lineales, permitiendo encontrar el mcd de los coeficientes y determinar si la
ecuación tiene solución.

DESCENSO INFINITO

Es un método empleado para resolver ecuaciones más complejas, como las involucradas en el Último Teorema de Fermat.
Consiste en demostrar que si existe una solución, se puede construir una más pequeña hasta llegar a una contradicción.

CAMBIO DE VARIABLES Y FACTORIZACIÓN

Para ecuaciones más complejas, las transformaciones algebraicas y la factorización pueden ayudar a simplificar el problema.

IMPORTANCIA EN MATEMÁTICAS

Las ecuaciones diofánticas tienen aplicaciones en diversas áreas de la matemática y la ciencia, como la criptografía, la teoría de
números y la geometría. Por ejemplo, las soluciones enteras en criptografía son fundamentales para algoritmos de clave pública
como RSA. En teoría de números, son claves para problemas de factorización y divisibilidad, y en geometría, aparecen en la
búsqueda de puntos racionales sobre curvas elípticas.
 EJEMPLO 4.8
En este ejemplo se analiza cuántas comparaciones son necesarias para determinar si un elemento r pertenece a un
conjunto A_n, donde A_n es un conjunto de tamaño
|A_n| = 2^n y cuyos elementos están ordenados de manera ascendente. Se utiliza inducción matemática para generalizar el
número de comparaciones necesarias
.
1. BASE DE LA INDUCCIÓN

Cuando n = 0, el conjunto A_0 contiene solo un elemento, es decir, A_0 = {a_0}. Por lo tanto, solo se necesita una comparación
para determinar si el elemento r es igual a a_0. Este es el caso más simple y sirve como base para la inducción.

2. CASO PARA N = 1

Cuando n = 1, el conjunto A_1 = {a_0, a_1} tiene dos elementos. Para determinar si r pertenece a A_1, se realiza la primera
comparación con el elemento a_0. Dependiendo del resultado, se realiza una segunda comparación con a_1. En total, se necesitan
dos comparaciones para verificar si r pertenece a A_1.

3. CASO GENERAL POR INDUCCIÓN

Para generalizar el proceso, se considera el conjunto A_{n+1}, el cual se divide en dos subconjuntos B y C, cada uno de tamaño
2^n. El conjunto B contiene la mitad inferior de los elementos de A_{n+1}, mientras que C contiene la mitad superior.

4. ESTRATEGIA DE RESOLUCIÓN

La estrategia para resolver el problema consiste en realizar las siguientes comparaciones:

1. Se compara el elemento r con el elemento medio del conjunto A_{n+1}. Si r es menor o igual, se verifica si pertenece a B.
2. Si r es mayor, se verifica si pertenece a C.
Por inducción, si el resultado es válido para A_n, también lo será para A_{n+1}, y se concluye que el número máximo de
comparaciones necesarias para determinar si r pertenece a A_n es de n + 1 comparaciones.

5. CONCLUSIÓN
Este ejemplo demuestra cómo la inducción matemática y la división de un conjunto en subconjuntos pueden reducir el número de
comparaciones necesarias para resolver problemas.
MCM

El mínimo común múltiplo (MCM) de dos o más números es el número entero positivo más pequeño que es divisible por todos esos
números. Existen varios métodos para calcular el MCM

1. MÉTODO DE LOS FACTORES PRIMOS

Este método implica descomponer los números en sus factores primos y luego seleccionar los factores con los
mayores exponentes.
Pasos:
1. Descompón los números en factores primos.
2. Para cada número primo que aparezca en alguna de las descomposiciones, selecciona el mayor exponente.
3. Multiplica esos factores para obtener el MCM. Ejemplo: Vamos a
encontrar el MCM de 12 y 15.

Descomposición en factores primos:

- 12 = 2^2 * 3
- 15 = 3 * 5

Ahora, seleccionamos los factores con los mayores exponentes:

- 2^2 (de 12),
- 3^1 (de ambos),
- 5^1 (de 15).
Multiplicamos: MCM = 2^2 * 3^1 * 5^1 = 4 * 3 * 5 = 60.

Por lo tanto, el MCM de 12 y 15 es 60.

2. MÉTODO USANDO EL MÁXIMO COMÚN DIVISOR (MCD)

Existe una fórmula para calcular el MCM usando el MCD de dos números:

MCM(a, b) = |a * b| / MCD(a, b) Pasos:

1. Calcula el MCD de los dos números.
2. Multiplica los dos números y luego divide el resultado entre el MCD. Ejemplo: Vamos a encontrar el
MCM de 12 y 15 usando esta fórmula.

El MCD de 12 y 15 es 3 (el mayor número que divide a ambos).

Aplicamos la fórmula:

MCM(12, 15) = (12 * 15) / MCD(12, 15) = 180 / 3 = 60.

El MCM de 12 y 15 es 60.

3. MÉTODO DE LISTADO DE MÚLTIPLOS

Este método consiste en listar los múltiplos de los números y encontrar el menor múltiplo común.

Pasos:

1. Lista los múltiplos de cada número.

2. Encuentra el primer múltiplo común entre los números.
Ejemplo: Para encontrar el MCM de 12 y 15:

Múltiplos de 12: 12, 24, 36, 48, 60, 72, ...

Múltiplos de 15: 15, 30, 45, 60, 75, ...

El primer múltiplo común es 60.

CONCLUSIÓN

El MCM es el número más pequeño que es múltiplo de dos o más números, y puede calcularse usando factorización de primos, la
fórmula con el MCD o listando múltiplos. Cada método tiene sus ventajas dependiendo del contexto del problema.

EJEMPLO 4.10:

El ejemplo trata sobre cómo expresar el número 14 usando solo los números 3 y 8. La idea es demostrar que cualquier número
\( n \) se puede escribir como una suma de treses y ochos.

1. Base de Inducción:
Se muestra que el número 14 se puede escribir como una suma de treses y ochos: ( 14
= 3 + 3 + 8 \).

2. Hipótesis de Inducción:
Suponemos que para algún número 14 , k se puede escribir como una suma de treses y ochos.

3. Paso Inductivo:

Demostramos que si k se puede escribir como una suma de treses y ochos, entonces k
+ 1 también se puede escribir de la misma manera.
Si k ya incluye un ocho, podemos reemplazar ese ocho por tres treses ya que 8 = 3 + 3 + 2.
Si k no incluye un ocho, podemos agregar un tres a la suma para obtener k + 1

Conclusión:
Siguiendo este proceso, se demuestra que cualquier número mayor o igual a 14 se puede escribir como una suma de
treses y ochos.

EJERCICIOS 4.5

Ejercicio 1: Producto de primos

Descomponer los siguientes números en factores primos.
a) 148,500
148,500 = 2^2 × 3 × 5^3 × 11^2
b) 7,114,800
7,114,800 = 2^4 × 3^2 × 5^2 × 11 × 43
c) 7,882,875
7,882,875 = 5^3 × 7^2 × 17 × 43

Ejercicio 3: Factorización común de primos La factorización de a^2

es:
a^2 = p1^(2k1) × p2^(2k2) × ... × pn^(2kn)

Ejercicio 5: Mayor divisor

El valor más grande es 2^14.

Ejercicio 7: Irracionalidad de la raíz de un primo Demostración:

Supongamos que √p es racional, es decir, que √p = a/b donde a y b son enteros primos entre sí. Entonces:
p = a^2 / b^2
Esto implica que a^2 = p × b^2, lo cual implica que a es divisible por p. Esto llevaría a una contradicción, ya que entonces b
también sería divisible por p. Por lo tanto, √p es irracional.
Ejercicio 15: Cuadrado perfecto divisible entre 77 Descomponemos 77 en
factores primos: 77 = 7 × 11.
Para que el número sea un cuadrado perfecto, los exponentes deben ser pares. Por lo tanto, necesitamos al menos 7^2 y 11^2.
El cuadrado perfecto más pequeño que es divisible por 77 es: 7^2 × 11^2 = 5,929.

Ejercicio 17: Entero positivo más pequeño para un cubo perfecto Descomponemos 1260 en factores primos:
1260 = 2^2 × 3^2 × 5 × 7.
Para que sea un cubo perfecto, los exponentes deben ser múltiplos de 3. Debemos multiplicar 1260 por un número que
complete los exponentes.
El número necesario es: x = 2 × 3 × 5^2 × 7^2 = 7,350.

Ejercicio 19: Cantidad de productos diferentes Conjuntos:

A = {4, 8, 16, 32}
B = {4, 8, 64, 81, 243}
Multiplicamos cada elemento de A con cada elemento de B y eliminamos los productos repetidos.
Los productos únicos son: {16, 32, 64, 128, 256, 324, 512, 648, 972, 1,024, 1,296, 1,944,
2,048, 2,592, 3,888, 7,776}.
En total, hay 16 productos diferentes.

Ejercicio 21: Información incompleta

El problema está relacionado con las longitudes de los lados de un triángulo, pero la información proporcionada es
insuficiente para resolverlo.

Ejercicio 23: Evaluar el producto

a) Evaluar el producto \( \prod_{i=1}^{5} i^2 \) y \( \prod_{i=1}^{n} i^2 \).
Para \( \prod_{i=1}^{5} i^2 \), calculamos el producto de los cuadrados de los primeros 5 números:
\( \prod_{i=1}^{5} i^2 = 1^2 \times 2^2 \times 3^2 \times 4^2 \times 5^2 = 1
\times 4 \times 9 \times 16 \times 25 = 14,400 \)
Por lo tanto, \( \prod_{i=1}^{5} i^2 = 14,400 \).
Para \( \prod_{i=1}^{n} i^2 \), el resultado es el producto de los cuadrados de los primeros \( n \) números:
\( \prod_{i=1}^{n} i^2 = (n!)^2 \)
b) Encontrar una fórmula para \( \prod_{i=1}^{n} a_i \) y \( \prod_{i=1}^{n} a_i^2
\).
La fórmula general es:
\( \prod_{i=1}^{n} a_i = a_1 \times a_2 \times ... \times a_n \) Y para el producto de
cuadrados:
\( \prod_{i=1}^{n} a_i^2 = (a_1 \times a_2 \times ... \times a_n)^2 = \left(
\prod_{i=1}^{n} a_i \right)^2 \) Ejercicio 25:
Demostrar la igualdad
Demostrar que si \( n \in \mathbb{Z}^+ \) y \( n \geq 2 \), entonces:
\( \prod_{i=2}^{n} \left( 1 - \frac{1}{i} \right) = \frac{n+1}{2n} \) Descomponemos cada factor:
\( 1 - \frac{1}{2} = \frac{1}{2}, \quad 1 - \frac{1}{3} = \frac{2}{3}, \quad 1 - \frac{1}{4} =
\frac{3}{4}, \ldots, \quad 1 - \frac{1}{n} = \frac{n-1}{n} \) Multiplicamos los términos:
\( \prod_{i=2}^{n} \left( 1 - \frac{1}{i} \right) = \frac{1}{2} \times \frac{2}{3} \times
\frac{3}{4} \times \cdots \times \frac{n-1}{n} \) La cancelación
telescópica nos lleva a:
\( \frac{1 \times 2 \times \cdots \times (n-1)}{2 \times 3 \times \cdots \times n} =
\frac{1}{n} \)
Multiplicando ambos lados por \( n+1 \), obtenemos:
\( \frac{1}{n} \times (n+1) = \frac{n+1}{2n} \) Esto completa la
demostración.

EJERCICIOS 5.2

a) ((x,y) ∈Z x Z, y = x^2 + 1):

Es una función: Para cada valor entero de x, existe un único valor entero de y (su cuadrado más 1).
Imagen: El conjunto de todos los números enteros mayores o iguales a 1 (ya que el cuadrado de cualquier número entero es
mayor o igual a 0).

b) ((x,y) ∈R x R, y^2 = x):

No es una función: Para cada valor positivo de x, existen dos valores posibles de y (la raíz cuadrada positiva y negativa).
Por ejemplo, si x = 4, y puede ser 2 o -2.

c) ((x,y) ∈R x R, y = 3x + 1):

Es una función: Para cada valor real de x, existe un único valor real de y. Esta es una función lineal.
Imagen: El conjunto de todos los números reales (ya que al multiplicar cualquier número real por 3 y sumarle 1, se obtiene
otro número real).

d) ((x,y) ∈Q x Q, y = x^2 + 1):

Es una función: Similar al caso (a), pero ahora el dominio y el codominio son los números racionales. Para cada número racional
x, su cuadrado más 1 también será un número racional.
Imagen: El conjunto de todos los números racionales mayores o iguales a 1.
e) es una relación de A en B tal que |A|=5, |B|=6 y |R|=6.

No se puede determinar si es una función con esta información: Conocer solo las cardinalidades de los conjuntos no es suficiente
para determinar si la relación es una función. Necesitaríamos conocer la correspondencia específica entre los elementos de
A y B.

Función de R en R:

● Dominio: Todos los números reales (R).

● Codominio: Todos los números reales (R).
● Análisis:
○ Para cualquier valor de x que elijamos en los números reales, al elevarlo al cuadrado, restarle 2, y luego
elevar el resultado al cubo, siempre obtendremos un único valor real.
 ○ No hay ninguna restricción en la operación que impida obtener cualquier número real como resultado.

Conclusión: Sí, la regla (f(x) = (x^2 - 2)^3) define una función de (R) en (R). Esto significa que a cada número real x le corresponde
un único número real y, calculado mediante la expresión dada.

Función de Z en R:

● Dominio: Todos los números enteros (Z).

● Codominio: Todos los números reales (R).
● Análisis:
○ Al igual que en el caso anterior, para cualquier número entero x, al realizar las operaciones
indicadas, siempre obtendremos un único número real.
○ No hay ninguna restricción adicional al trabajar con números enteros que
impida obtener cualquier número real como resultado.

Conclusión: Sí, la regla (f(x) = (x^2 - 2)^3) también define una función de (Z) en (R). Esto significa que a cada número entero x le
corresponde un único número real y, calculado mediante la misma expresión.

En resumen:

La función (f(x) = (x^2 - 2)^3) es una función tanto de los números reales en los números reales como de los números enteros en
los números reales. Esto se debe a que para cualquier valor de x en el dominio (ya sea real o entero), la expresión siempre
produce un único valor real y bien definido.

Ejemplo:

Si evaluamos la función en x = 2 (un número entero):

● f(2) = (2^2 - 2)^3 = (4 - 2)^3 = 2^3 = 8

Si evaluamos la función en x = 1.5 (un número real):

● f(1.5) = (1.5^2 - 2)^3 = (2.25 - 2)^3 = 0.25^3 = 0.015625

(a)Enumerar cinco funciones de A en B: Una función de A en B asigna a cada elemento de A un único elemento de B.
Aquí hay 5 ejemplos:

1. f(1) = x, f(2) = y, f(3) = z, f(4) = x

2. f(1) = y, f(2) = z, f(3) = x, f(4) = y
3. f(1) = z, f(2) = x, f(3) = y, f(4) = z
4. f(1) = x, f(2) = x, f(3) = y, f(4) = z
5. f(1) = y, f(2) = y, f(3) = z, f(4) = x

(b)¿Cuántas funciones f: A → B existen? Cada elemento de A puede tomar 3 valores posibles (x, y o z). Entonces,
para los 4 elementos de A, hay 3 opciones para cada uno. Por el principio multiplicativo, hay 3^4 = 81 funciones
posibles.

(c) ¿Cuántas funciones f: A → B son uno a uno? Para que una función sea uno a uno, todos los elementos de A deben tener
imágenes distintas en B. Sin embargo, como A tiene más elementos que B, es imposible que todas las imágenes sean distintas.
Por lo tanto, no hay funciones inyectivas de A en B.

(d)¿Cuántas funciones g: B → A existen? Ahora estamos buscando funciones de B a A. Cada elemento de B puede
tomar 4 valores posibles (1, 2, 3 o 4). Entonces, para los 3 elementos de B, hay 4 opciones para cada uno. Por lo
tanto, hay 4^3 = 64 funciones posibles.

(e)¿Cuántas funciones g: B → A son inyectivas? En este caso, como B tiene menos elementos que A, sí es posible encontrar
funciones inyectivas. Cada elemento de B puede tomar 4 valores posibles, y como no hay restricciones, la primera imagen
puede ser cualquiera de las 4, la segunda cualquiera de las 3 restantes, y la tercera cualquiera de las 2 restantes. Entonces,
hay 432 = 24 funciones inyectivas.

(f) ¿Cuántas funciones f: A → B satisfacen f(1) = x? Si f(1) está fijo en x, entonces para los otros 3 elementos de A hay 3
opciones cada uno. Por lo tanto, hay 3^3 = 27 funciones.

(g) ¿Cuántas funciones f: A → B satisfacen f(1) = f(2) = x? Si f(1) y f(2) están fijos en x, entonces para los otros 2
elementos de A hay 3 opciones cada uno. Por lo tanto, hay 3^2 = 9 funciones.
(h) ¿Cuántas funciones f: A → B satisfacen f(1) = x y f(2) = y? Si f(1) está fijo en x y f(2) en y, entonces para los otros 2
elementos de A hay 3 opciones cada uno. Por lo tanto, hay 3^2 = 9 funciones.

En resumen:

● Hay 81 funciones posibles de A en B.

● No hay funciones inyectivas de A en B.
● Hay 64 funciones posibles de B en A.
● Hay 24 funciones inyectivas de B en A.
● El número de funciones que cumplen condiciones específicas depende de cuántas opciones quedan para
asignar los demás elementos.

a) A ∩ B: Intersección de A y B.

● Para encontrar la intersección, igualamos las ecuaciones de A y B: 2x + 1 = 3x x = 1 Sustituyendo x = 1 en

cualquiera de las ecuaciones, encontramos y = 3.
● Respuesta: A ∩ B = {(1, 3)}. Es decir, el único punto que pertenece tanto a A como a B es (1, 3).

b) B ∩ C: Intersección de B y C.

● Igualamos las ecuaciones de B y C: 3x = x - 3 2x = -3 x = -3/2 Sustituyendo x =

-3/2 en cualquiera de las ecuaciones, encontramos y = -9/2.
● Respuesta: B ∩ C = {(-3/2, -9/2)}.

c) A ∪C: Unión de A y C.

● La unión de A y C es simplemente la combinación de todos los puntos que pertenecen a A o a C. Esto es, todas las
soluciones de las ecuaciones y = 2x + 1 o y

= x - 3.
● Respuesta: A ∪C es la unión de las dos rectas definidas por las ecuaciones y = 2x + 1 y y = x - 3.

d) B ∪C: Unión de B y C.
 ● Similarmente a c), B ∪C es la unión de todas las soluciones de las ecuaciones y
= 3x o y = x - 3.
● Respuesta: B ∪C es la unión de las dos rectas definidas por las ecuaciones y = 3x y y = x - 3.

En resumen:

● La intersección de dos rectas es un punto (si se cortan) o el conjunto vacío (si son paralelas).
● La unión de dos rectas es la combinación de todos los puntos que pertenecen a cualquiera de las dos rectas.

a) [2.3 - 1.6]

● 2.3 - 1.6 = 0.7

● [0.7] = 0 (El mayor entero menor o igual a 0.7 es 0)

b) [2.3] - [1.6]

● [2.3] = 2
● [1.6] = 1
● 2-1=1

c) [2.3] - [1.6]

● Este inciso es igual al inciso b), por lo tanto: [2.3] - [1.6] = 1

d) [3.7] + [7.3]

● [3.7] = 3
● [7.3] = 7
● 3 + 7 = 10

e) [3.4][6.2]

● [3.4] = 3
● [6.2] = 6
● 3 * 6 = 18
f) 3.4 [6.2]

● [6.2] = 6
● 3.4 * 6 = 20.4

g) [2π]

● π ≈ 3.14
● 2π ≈ 6.28
● [6.28] = 6

h) 2[π]

● [π] = 3
● 2*3=6

Respuestas: a) 0 b) 1 c) 1 d) 10 e) 18 f) 20.4 g) 6 h) 6

a) 7[x] = [7x]

● Análisis: Esta igualdad nos dice que al multiplicar la parte entera de x por 7, obtenemos lo mismo que al calcular
la parte entera del producto de 7 y x.
● Solución: Esta igualdad se cumple para todos los números reales x. Esto se debe a que al multiplicar un número por
un entero y luego tomar su parte entera, es lo mismo que tomar la parte entera primero y luego multiplicar.

b) [3x] = 7

● Análisis: Aquí se nos pide encontrar los valores de x para los cuales la parte entera de 3x es exactamente
7.
● Solución: Para que [3x] = 7, 3x debe estar entre 7 y 8 (excluyendo el 8). Es decir, 7
≤ 3x < 8. Dividiendo todos los términos por 3, obtenemos: 7/3 ≤ x < 8/3.
● Respuesta: Los valores de x que satisfacen la ecuación son todos los números reales en el intervalo [7/3, 8/3).

c) [x + 7] = x + 7
 ● Análisis: Esta igualdad nos dice que la parte entera de x + 7 es igual a x + 7. Esto solo ocurre cuando x + 7 es un
número entero.
● Solución: Para que [x + 7] = x + 7, x debe ser un número entero. Si x es un número entero, al sumarle 7 y tomar la
parte entera, obtenemos el mismo número.
● Respuesta: Los valores de x que satisfacen la ecuación son todos los números enteros.

d) [x + 7] = [x] + 7

● Análisis: Esta igualdad nos dice que al sumar 7 a la parte entera de x, obtenemos lo mismo que al tomar la parte
entera de la suma de x y 7.
● Solución: Esta igualdad se cumple para todos los números reales x. Esto es porque al sumar un entero (7) a un
número y luego tomar la parte entera, es lo mismo que tomar la parte entera primero y luego sumar el entero.

Respuestas finales:

● a) Todos los números reales.

● b) x ∈[7/3, 8/3).
● c) Todos los números enteros.
● d) Todos los números reales.

a) Encuentre todos los números reales x tales que [2x] = 2[x].

● Análisis: Esta ecuación nos dice que el doble de la parte entera de x es igual a la parte entera del doble de x.
● Solución: Esta igualdad se cumple para todos los números reales x. Esto es porque al duplicar un número y luego
tomar su parte entera, es lo mismo que tomar la parte entera primero y luego duplicar.
● Respuesta: Todos los números reales.

b) Encuentre todos los números reales x tales que [3x] = 3x.

● Análisis: Esta ecuación nos dice que la parte entera de 3x es igual a 3x. Esto solo ocurre cuando 3x es un número
entero.
 ● Solución: Para que [3x] = 3x, 3x debe ser un número entero. Esto significa que x debe ser un múltiplo de 1/3.
● Respuesta: Todos los números de la forma x = n/3, donde n es un número entero.

c) Sea n ∈Z donde n > 1. Determine todos los x ∈R tales que [nx] = n[x].

● Análisis: Esta ecuación es una generalización de la parte a).

● Solución: Al igual que en el inciso a), esta igualdad se cumple para todos los números reales x. Multiplicar por un
entero y luego tomar la parte entera, o tomar la parte entera primero y luego multiplicar, da el mismo
resultado.
● Respuesta: Todos los números reales.

Respuestas finales:

● a) Todos los números reales.

● b) Todos los números de la forma x = n/3, donde n es un número entero.
● c) Todos los números reales.

a) Sea a ∈R, donde a ≥ 1. Demuestre que (i) [a/a] = 1 y que (ii) [a]/a ≤ 1.

● (i) [a/a] = 1:

○ Si a ≥ 1, entonces a/a = 1.
○ La parte entera de 1 es 1.
○ Por lo tanto, [a/a] = [1] = 1.
● (ii) [a]/a ≤ 1:

○ La parte entera de un número siempre es menor o igual al número mismo.

○ Por lo tanto, [a] ≤ a.
○ Dividiendo ambos lados de la desigualdad por a (que es positivo ya que a ≥ 1), obtenemos: [a]/a ≤ 1.

b) Si a ∈R y 0 < a < 1, ¿qué resultados de la parte (a) son verdaderos?

 ● (i) [a/a] = 1: Este resultado sigue siendo válido, ya que a/a = 1 independientemente del valor de a
(siempre que a sea distinto de cero).
● (ii) [a]/a ≤ 1: Este resultado también sigue siendo válido, ya que la parte entera de un número siempre es menor o
igual al número mismo.

Conclusión:

Ambos resultados, (i) y (ii), son verdaderos tanto para a ≥ 1 como para 0 < a < 1.

a) f: Z → Z, f(x) = 2x - 1

● Inyectiva: Sí. Si f(x₁) = f(x₂), entonces 2x₁- 1 = 2x₂- 1, lo que implica que x₁= x₂.
● Imagen: Todos los números impares.

b) f: Q → Q, f(x) = 2x + 1

● Inyectiva: Sí. Similar al caso anterior, si f(x₁) = f(x₂), entonces x₁= x₂.
● Imagen: Todos los números racionales.

c) f: Z → Z, f(x) = x² - x

● Inyectiva: No. Por ejemplo, f(0) = f(1) = 0, pero 0 ≠ 1.

● Imagen: Todos los números enteros no negativos.

d) f: R → R, f(x) = e^x

● Inyectiva: Sí. La función exponencial es estrictamente creciente, por lo que si x₁

≠ x₂, entonces e^x₁≠ e^x₂.
● Imagen: Todos los números reales positivos.

e) f: [-π/2, π/2] → R, f(x) = sen(x)

● Inyectiva: Sí. En el intervalo [-π/2, π/2], la función seno es estrictamente creciente.

● Imagen: [-1, 1].

f) f: [0, π] → R, f(x) = sen(x)

● Inyectiva: No. Por ejemplo, f(π/2) = f(3π/2) = 1, pero π/2 ≠ 3π/2.

 ● Imagen: [0, 1].

Resolución Análisis:

● El elemento 2 ya está asignado a x e y. Esto significa que para que sea una
función (cada elemento de A debe tener una única imagen en B), no podemos asignar 2 a z.
● El elemento 1 ya está asignado a z. Entonces, 1 no puede asignarse a x ni a y.
● El elemento 3, 4 y 5 aún no tienen asignación.

Posibles asignaciones para 3, 4 y 5:

● 3: Puede ir a x o y (ya que 2 ya está asignado a ambos).

● 4: También puede ir a x o y.
● 5: Lo mismo, puede ir a x o y.

Calculando las posibilidades:

● Para el elemento 3 hay 2 opciones (x o y).

● Para el elemento 4, habiendo elegido una opción para 3, quedan 2 opciones.
● Para el elemento 5, quedan 2 opciones.

Total de formas: 2 opciones * 2 opciones * 2 opciones = 8 formas.

Conclusión: Existen 8 formas diferentes de extender la relación parcial dada a una función completa de A a B.

Solución

a) Función de acceso Método de la fila

principal

Si comenzamos a indexar desde 2 en lugar de 1, y almacenamos la matriz por filas, podemos modificar la fórmula de acceso
estándar de la siguiente manera:
f(i, j) = (i - 1) * n + j + 1 Donde:

● i es el índice de fila (1-indexado).

● j es el índice de columna (1-indexado).
● n es el número de columnas.

La parte (i - 1) * n nos lleva al inicio de la fila i, y luego sumamos j para llegar a la columna j. Finalmente, sumamos 1
para compensar el cambio de índice inicial.

Método de la columna principal

Si almacenamos la matriz por columnas, la fórmula sería:

f(i, j) = (j - 1) * m + i + 1 Donde:

● m es el número de filas.

La lógica es similar, pero ahora recorremos las columnas primero.

b) Condiciones para m, n, r, y k

● m, n > 0: El número de filas y columnas debe ser positivo.

● r, k ≤ m*n: Los índices de fila (r) y columna (k) deben estar dentro de los límites de la matriz.
● r, k ≥ 1: Dado que hemos modificado el índice inicial a 2, los índices de fila y columna deben ser al menos 1.

Ejemplo

Supongamos una matriz de 3x2 (m=3, n=2) y queremos acceder al elemento en la posición (2,1) (segunda fila, primera columna).
Usando el método de la fila principal:

f(2, 1) = (2 - 1) * 2 + 1 + 1 = 4
Entonces, el elemento en (2,1) de la matriz se almacena en la posición 4 del arreglo unidimensional.

Caso base 1: Si m = 0, entonces A(m, n) = n + 1. Esto significa que si el primer argumento es 0, la función simplemente
incrementa el segundo argumento en 1.

Caso base 2: Si m > 0 y n = 0, entonces A(m, n) = A(m - 1, 1). Esto significa que si el segundo argumento es 0 y el primero es mayor
que 0, la función se reduce a un caso donde el primer argumento se decrementa en 1 y el segundo se establece en 1.

Caso recursivo: Si m > 0 y n > 0, entonces A(m, n) = A(m - 1, A(m, n - 1)). Este es el caso más complejo y define la función
recursivamente en términos de sí misma con argumentos más pequeños.

Enunciado Formal

De manera más formal, el Principio del Palomar establece que:

● Si n objetos se distribuyen en m contenedores, y n > m, entonces al menos un contenedor debe contener más de
un objeto.

¿Por qué es importante?

A pesar de su simplicidad, el Principio del Palomar es una herramienta poderosa en matemáticas, especialmente en
combinatoria y teoría de números. Te permite demostrar resultados sorprendentes a partir de supuestos muy básicos.

Ejemplo:

● Cumpleaños: En un grupo de 367 personas, al menos dos comparten cumpleaños. ¿Por qué? Porque hay
366 días en un año (palomares) y 367 personas (palomas).
● Medias: Si tienes 11 pares de calcetines de diferentes colores y los metes todos
revueltos en un cajón oscuro, ¿cuántos calcetines necesitas sacar para asegurarte de tener al menos un par del
mismo color? La respuesta es 3. Si sacas 3 calcetines, tendrás al menos dos del mismo color, ya que solo hay dos
colores posibles.
Aplicaciones del Principio del Palomar

● Teoría de números: Demostrar la existencia de números con ciertas propiedades.

● Combinatoria: Resolver problemas de conteo y distribución.
● Informática: Analizar algoritmos y estructuras de datos.
● Geometría: Demostrar propiedades de figuras geométricas.

¿Por qué funciona?

La idea detrás del Principio del Palomar es muy intuitiva: si tienes más objetos que contenedores, inevitablemente tendrás que
poner más de un objeto en al menos uno de los contenedores. Es una forma de razonamiento por reducción al absurdo: si
asumimos que ningún contenedor tiene más de un objeto, llegamos a una contradicción con la hipótesis inicial de que hay
más objetos que contenedores.

En resumen,

El Principio del Palomar es una herramienta matemática fundamental que nos permite resolver problemas de una manera
elegante y sencilla. A pesar de su aparente simplicidad, sus aplicaciones son vastas y variadas.

EJERCICIOS 6.2

Entendiendo la Tabla

¿Qué representa cada elemento de la tabla?

● Filas (s₀, s₁, s₂): Corresponden a los posibles estados en los que se puede encontrar la máquina.
● Columnas (0, 1): Representan las posibles entradas que la máquina puede recibir.
● ν: Indica el nuevo estado al que transita la máquina después de recibir una entrada en un estado particular.
● ω: Representa la salida que produce la máquina al realizar una transición.

Cómo funciona la máquina

Para entender cómo funciona, vamos a simular una secuencia de entradas. Supongamos que comenzamos en el estado s₀y
recibimos la secuencia de entrada "011".

1. Estado inicial: s₀
2. Entrada 0: Según la tabla, al estar en s₀y recibir un 0, permanecemos en s₀y la salida es 0.
3. Entrada 1: Ahora estamos en s₀y recibimos un 1, pasamos a s₁y la salida es 0.
4. Entrada 1: Estamos en s₁y recibimos un 1, pasamos a s₁y la salida es 0.

Resultado:

● Estado final: s₁
● Salida: 000

Resolución del Problema

Para resolver este problema, necesitamos una secuencia de entrada específica. Sin una secuencia de entrada concreta, no
podemos determinar el estado final ni la salida.

Ejemplo: Supongamos que se nos pide analizar la secuencia de entrada "abac" comenzando desde el estado inicial s₀.

1. Estado inicial: s₀
2. Entrada "a": Según la tabla, al estar en s₀y recibir "a", pasamos a s₀y la salida es 0.
3. Entrada "b": Ahora estamos en s₀y recibimos "b", pasamos a s₁y la salida es 0.
4. Entrada "a": Estamos en s₁y recibimos "a", pasamos a s₁y la salida es 0.
5. Entrada "c": Estamos en s₁y recibimos "c", pasamos a s₃y la salida es 1.

Resultado:

● Estado final: s₃
● Salida: 0001

Entendiendo la Tabla

La tabla 6.5 describe el comportamiento de una máquina expendedora de bebidas. Cada estado de la máquina
representa una cantidad específica de dinero depositado. Las
entradas son las monedas que se insertan o los botones que se presionan para dispensar el producto.

● Estados (s₀, s₁, s₂, s₃, s₄): Representan la cantidad de dinero depositada en la máquina: 0, 5, 10, 15, y 20 centavos
respectivamente.
● Entradas (5¢, 10¢, 25¢, B, W): Corresponden a las monedas de 5, 10 y 25 centavos, y a los botones para comprar
cola (B) o cerveza (W).
● ν (Nuevo estado): Indica el estado al que pasa la máquina después de recibir una entrada, dada su estado actual.
● ω (Salida): Muestra la salida que produce la máquina, como el producto dispensado o el dinero devuelto.

Funcionamiento de la Máquina

La máquina funciona de la siguiente manera:

1. Inicio: La máquina siempre comienza en el estado s₀(sin dinero depositado).

2. Inserción de monedas: Al insertar una moneda, la máquina pasa al estado correspondiente a la cantidad total
de dinero depositado.
3. Selección de producto: Al presionar el botón B o W, la máquina verifica si se ha depositado suficiente dinero para
comprar el producto seleccionado. Si es así, dispensa el producto y vuelve al estado inicial. Si no, permanece en el
mismo estado o pasa a un estado con un saldo menor si se devuelve dinero.

Ejemplo

Supongamos que queremos comprar una cola (B) y tenemos 15 centavos.

1. Inicio: Estamos en el estado s₀.

2. Insertamos 10 centavos: Pasamos al estado s₁.
3. Insertamos 5 centavos: Pasamos al estado s₂.
4. Presionamos B: Como tenemos 15 centavos (estado s₂), la máquina dispensa una cola y vuelve al estado s₀.

Análisis de la Máquina
 ● Flexibilidad: La máquina permite diferentes combinaciones de monedas para comprar un producto.
● Gestión de errores: Si se introduce más dinero del necesario, la máquina devuelve el exceso.
● Estados de espera: La máquina puede permanecer en un estado si no se ha depositado suficiente dinero.

Posibles Ampliaciones

● Productos con diferentes precios: Se podrían agregar más estados para representar diferentes precios
de productos.
● Devolución de cambio: Se podrían agregar estados y salidas para indicar la cantidad de cambio a devolver.
● Limitación de productos: Se podrían agregar estados para indicar que un producto se ha agotado.

El análisis del comportamiento de una máquina de estados finitos para la secuencia de entradas {1, 0, 1, 1, 0, 0}. Se analiza cómo
la máquina transita por los diferentes estados según el diagrama presentado en la Figura 6.5.

Diagrama de Estados

El diagrama de estados incluye los siguientes estados: S = {s0, s1, s2, s3, s4, s5}, y la máquina comienza en el estado inicial s0.
Dependiendo de la entrada (0 o 1), la máquina se mueve entre los estados.

Análisis de la Secuencia {1, 0, 1, 1, 0, 0}

Para la secuencia de entradas {1, 0, 1, 1, 0, 0}, la máquina realiza el siguiente recorrido por los estados:

1. Estado inicial: s0.

2. Con la entrada 1 desde s0, la máquina se mueve a s4.

3. Con la entrada 0 desde s4, la máquina se mueve a s3.

4. Con la entrada 1 desde s3, la máquina se mueve a s5.

5. Con la entrada 1 desde s5, la máquina permanece en s5.

6. Con la entrada 0 desde s5, la máquina se mueve de vuelta a s3.

7. Con la entrada 0 desde s3, la máquina se mueve a s2.

Resumen del Comportamiento

La secuencia de estados que recorre la máquina con la entrada {1, 0, 1, 1, 0, 0} es: s0 → s4 → s3 → s5 → s5 → s3

→ s2.

Esto muestra cómo la máquina explora varios estados y vuelve a algunos de ellos, dependiendo de las entradas.

Inciso a: Descripción del comportamiento de la máquina de estados

La máquina de estados cambia entre los estados s0 y s1 dependiendo de las entradas 0 o 1. Funciona de la siguiente manera:

1. En s0:

- Si recibe un 0, la máquina permanece en s0.

- Si recibe un 1, la máquina transita a s1.

2. En s1:

- Si recibe un 0, la máquina regresa a s0.

- Si recibe un 1, la máquina permanece en s1.

Comportamiento general: La máquina alterna entre los estados s0 y s1 cuando las entradas son diferentes (1 desde s0 o 0
desde s1), y permanece en el mismo estado cuando las entradas son iguales (0 en s0 o 1 en s1).

Inciso b: ¿Qué debe recordar el estado s1?

El estado s1 recuerda que la última entrada recibida fue un 1. Es decir, cuando la máquina está en s1, eso significa que la última
entrada procesada fue un 1. Si la máquina está en s0, la última entrada fue un 0.

Inciso c: Lenguajes A y B tales que cada x ∈AB tiene 1 como sufijo

Los lenguajes A y B que garantizan que cualquier x ∈AB tenga 1 como sufijo son:

- A = { 0^n | n ≥ 0 } (cadenas de ceros que mantienen a la máquina en s0).

- B = { 1 } (cadenas que mueven la máquina a s1 con un 1 al final).

Justificación: Cualquier cadena x que pertenezca a AB terminará en 1, lo que significa que la máquina terminará en el estado s1
al finalizar el procesamiento.

Análisis y Solución del Problema Entendiendo el

Problema

Tenemos tres conjuntos finitos: S, T, y C. Se nos dan sus cardinalidades (número de elementos): |S| = 3, |T| = 5, y |C| = 2.

Se nos pide determinar:

● i) El cardinal del producto cartesiano S x T.

● ii) El número de funciones de T a S unión T.

● iii) El número de funciones de C a C.

● iv) El número de máquinas de estados finitos que se pueden determinar con estos conjuntos.

Resolviendo cada inciso

i) Cardinal del producto cartesiano S x T

El producto cartesiano de dos conjuntos A y B, denotado A x B, es el conjunto de todos los pares ordenados (a, b) donde a ∈A

y b ∈B.
 ● Principio de multiplicación: Si un evento puede ocurrir de m maneras y otro evento puede ocurrir de n maneras,

entonces ambos eventos pueden ocurrir de m * n maneras.

Por lo tanto, |S x T| = |S| * |T| = 3 * 5 = 15.

ii) Número de funciones de T a S ∪T

● S ∪ T: La unión de dos conjuntos contiene todos los elementos que están en al menos uno de los conjuntos.

Dado que S y T son conjuntos finitos y disjuntos (no comparten elementos), |S ∪T| = |S| + |T| = 3 + 5 = 8.

● Número de funciones: Una función de un conjunto A a un conjunto B asigna a

cada elemento de A exactamente un elemento de B. Si el dominio (conjunto de partida) tiene m elementos y el

codominio (conjunto de llegada) tiene n elementos, entonces hay n^m funciones posibles.

Por lo tanto, el número de funciones de T a S ∪T es 8^5 = 32768.

iii) Número de funciones de C a C

● Funciones identidad: En este caso, el dominio y el codominio son el mismo conjunto. Una función identidad

asigna cada elemento a sí mismo.

● Otras funciones: Además de la función identidad, pueden existir otras funciones que asignen elementos de C a

elementos de C de diferentes maneras.

Para calcular el número total de funciones, aplicamos el principio de multiplicación. Cada elemento de C puede ser asignado

a cualquiera de los 2 elementos de C. Por lo tanto, hay 2^2 = 4 funciones posibles de C a C.

iv) Número de máquinas de estados finitos

El cálculo exacto del número de máquinas de estados finitos que se pueden determinar con estos conjuntos dependería de la

definición específica de máquina de estados finito que se esté utilizando. Sin embargo, podemos hacer algunas observaciones

generales:

● Componentes de una máquina de estados finito: Generalmente, una máquina de estados finito consta de un conjunto de

estados, un conjunto de símbolos de entrada, un conjunto de símbolos de salida, una función de transición y una

función de salida.

● Relación con los conjuntos dados: Los conjuntos S, T, y C podrían representar diferentes componentes de la

máquina, como estados, entradas o salidas.

● Combinaciones posibles: El número de máquinas posibles dependerá de las restricciones impuestas sobre

estas combinaciones.

Análisis y Solución del Problema de la Máquina de Estados Finitos

Entendiendo el Problema

Tenemos una máquina de estados finitos definida por:

● Conjunto de estados: S = {s0, s1, s2, s3, s4, s5}

● Alfabeto de entrada: Σ = {0, 1}

● Alfabeto de salida: Σo = {0, 1}

● Función de transición: Definida por las aristas del diagrama

● Estado inicial: s0

Se nos pide analizar el comportamiento de esta máquina para diferentes entradas.

Resolviendo los incisos

a) Encontrar la salida para la cadena de entrada x = 0110111011

Procedimiento:

1. Iniciamos en el estado s0.

2. Leemos el primer símbolo de entrada (0) y seguimos la arista correspondiente desde s0, obteniendo una salida y

llegando a un nuevo estado.

3. Repetimos el paso 2 para cada símbolo restante de la cadena de entrada.

4. La secuencia de salidas obtenidas es la salida de la máquina para la cadena completa.

Solución: Al seguir el diagrama de estados con la cadena de entrada dada, obtendremos una secuencia de salidas. Sin el

diagrama específico, no puedo proporcionar la respuesta exacta. Sin embargo, el procedimiento descrito te permitirá obtener

la respuesta manualmente.

b) Tabla de transición

La tabla de transición es una representación tabular de la función de transición. Cada fila representa un estado, cada columna

una entrada, y la celda correspondiente contiene el estado de llegada y la salida.

Ejemplo de una fila de la tabla:

Estado actual Entrada Estado siguiente Salida

s0 0 s1 0

s0 1 s2 1

c) Posibilidades para x si partimos de s5 y la salida es 0000001 Procedimiento:

 1. Iniciamos en el estado s5.

2. Buscamos todas las posibles combinaciones de entradas que, al ser procesadas desde s5, produzcan una salida de

0000001 y terminen en cualquier estado.

Solución: Este inciso requiere un análisis exhaustivo del diagrama de estados a partir del estado s5. Al explorar todas las

posibles rutas desde s5 con una salida de 0000001, podrás encontrar todas las posibles cadenas de entrada x.

Análisis y Solución del Problema de la Máquina de Estados Finitos

Entendiendo el Problema

Tenemos una máquina de estados finitos definida por:

● Conjunto de estados: S = {s0, s1, s2, s3, s4, s5}

● Alfabeto de entrada: Σ = {0, 1}

● Alfabeto de salida: Σo = {0, 1}

● Función de transición: Definida por las aristas del diagrama

● Estado inicial: s0

Se nos pide analizar el comportamiento de esta máquina para diferentes entradas y construir una tabla de transición.

Resolviendo los incisos

a) Encontrar la tabla de estados

La tabla de transición es una representación tabular de la función de transición. Cada fila representa un estado, cada columna

una entrada, y la celda correspondiente contiene el estado de llegada y la salida.

Tabla de Transición:

Estado actual Entrada Estado siguiente Salida

s0 0 s1 0

s0 1 s2 1

s1 0 s3 0

s1 1 s0 1

s2 0 s4 0

s2 1 s5 1

s3 0 s1 0

s3 1 s2 1

s4 0 s5 0

s4 1 s4 1

s5 0 s5 0

s5 1 s5 1

b) Posibilidades para x si partimos de s5 y la salida es 0000001

Dado que el estado s5 es un estado de "sumidero" (una vez que entras, no puedes salir), cualquier cadena de entrada que

comience en s5 y tenga una longitud de 4 terminará en s5 y producirá una salida de 0000001. Por lo tanto, las posibilidades

para la cadena x son todas las cadenas de longitud 4 sobre el alfabeto {0, 1}.

Respuesta: x puede ser cualquier cadena de 4 bits, como 0000, 0001, 0010, ..., 1111.
c) Lenguaje A: Cadenas que producen una salida con 1 como sufijo

El lenguaje A consiste en todas las cadenas de entrada que, al ser procesadas por la máquina a partir del estado inicial s0,

producen una salida que termina en 1.

Análisis:

● Para que la salida termine en 1, la máquina debe terminar en un estado donde la salida asociada a cualquier entrada

sea 1.

● Observando la tabla de transición, vemos que los estados s1, s2, s4 y s5 tienen al menos una transición con salida 1.

● Por lo tanto, cualquier cadena que lleve la máquina a uno de estos estados y luego se quede en ese estado o pase a

otro con salida 1 pertenece al lenguaje A.

Ejemplos de cadenas en A:

● 1 (lleva a s2)

● 011 (lleva a s5)

● 1010101 (lleva a s2)

Descripción formal: A = {x ∈{0, 1}* | existe y ∈{0, 1}* tal que xy lleva la máquina a s1, s2, s4 o s5}

d) Lenguaje AC: Cadenas que producen una salida con 111 como sufijo

El lenguaje AC consiste en todas las cadenas de entrada que, al ser procesadas por la máquina a partir del estado inicial s0,

producen una salida que termina en 111.

Análisis:

● Para que la salida termine en 111, la máquina debe realizar al menos tres transiciones consecutivas con

salida 1.
 ● Observando la tabla de transición, vemos que esto solo es posible si la máquina pasa por los estados s1, s2 o s4 en

algún momento.

● Sin embargo, es difícil dar una descripción formal precisa de este lenguaje sin un análisis más detallado de las

posibles rutas en el autómata.

EJERCICIOS 11.1

Tres Situaciones Adicionales donde los Grafos Pueden Ser Útiles

Prompt: Enumere tres situaciones, diferentes de las vistas en esta sección, en que un grafo puede ser útil.

Respuesta:

Los grafos son estructuras de datos versátiles que pueden modelar una amplia variedad de relaciones y sistemas. A

continuación, se presentan tres situaciones adicionales en las que los grafos pueden ser particularmente útiles:

1. Redes Sociales:

○ Amistades: Las redes sociales pueden representarse como grafos donde los nodos son usuarios y las

aristas representan relaciones de amistad. Los grafos permiten analizar la popularidad de usuarios,

identificar comunidades, y recomendar amigos en común.

○ Interacciones: Las interacciones en redes sociales (me gusta, comentarios, compartidos) pueden

modelarse como un grafo dirigido, donde las aristas indican la dirección de la interacción. Esto permite

analizar la influencia de usuarios y la propagación de información.

2. Sistemas de Transporte:
 ○ Rutas: Las redes de transporte (carreteras, trenes, vuelos) pueden representarse como grafos donde los

nodos son ciudades, estaciones o aeropuertos, y las aristas son las conexiones entre ellos. Los algoritmos

de búsqueda en grafos pueden utilizarse para encontrar la ruta más corta o el camino más eficiente entre

dos puntos.

○ Optimización de rutas: Los grafos permiten modelar problemas de optimización como el problema del

vendedor viajero, donde se busca encontrar la ruta más corta que visita todos los nodos de un grafo

exactamente una vez.

3. Bioinformática:

○ Redes de proteínas: Las interacciones entre proteínas en una célula pueden representarse como un grafo,

donde los nodos son proteínas y las aristas representan las interacciones. El análisis de estos grafos

permite comprender la función de las proteínas y predecir nuevas interacciones.

○ Filogenia: Los árboles filogenéticos, que representan la historia evolutiva de un grupo de organismos, son

un tipo especial de grafo acíclico dirigido. Estos árboles se utilizan para estudiar la diversidad biológica y

las relaciones evolutivas entre especies.

Otras aplicaciones posibles de los grafos:

● Diseño de circuitos electrónicos: Los circuitos digitales pueden representarse como grafos para analizar su

funcionamiento y optimizar su diseño.

● Análisis de redes eléctricas: Las redes eléctricas pueden modelarse como grafos para analizar el flujo de energía y

detectar posibles fallas.

● Recomendación de productos: Los sistemas de recomendación pueden utilizar grafos para modelar las relaciones

entre usuarios y productos, y así recomendar productos relevantes a un usuario en particular.

 ● Análisis de texto: Los grafos pueden utilizarse para representar la estructura de un texto, donde los nodos son

palabras y las aristas representan relaciones semánticas entre ellas.

En resumen, los grafos son una herramienta poderosa para modelar y analizar una amplia variedad de sistemas y problemas.

Su versatilidad se debe a su capacidad para representar relaciones entre entidades de manera abstracta y eficiente.

el grafo de la Figura 11.7.

a) Un camino de b a d que no sea un recorrido:

● Ejemplo: b-e-a-c-d. Este camino utiliza la arista b-e dos veces, por lo que no es un recorrido.

b) Un recorrido b-d que no sea un camino simple:

● Ejemplo: b-e-a-b-e-d. Este recorrido utiliza el vértice b y la arista b-e dos veces, por lo que no es un camino simple.

c) Un camino simple de b a d:

● Ejemplo: b-e-d. Este camino utiliza cada vértice y cada arista solo una vez.

d) Un camino cerrado de b a b que no sea un circuito:

● Ejemplo: b-e-a-b-e-b. Este camino cerrado utiliza el vértice b y la arista b-e más de una vez, por lo que no es un

circuito.

e) Un circuito de b a b que no sea un ciclo:

● No es posible: Un circuito implica que todos los vértices son distintos, excepto el primero y el último. Por lo tanto, si

un circuito comienza y termina en b, no

 puede tener ningún otro vértice repetido. Por lo tanto, cualquier circuito de b a b es automáticamente un ciclo.

f) Un ciclo de b a b:

● Ejemplo: b-e-d-c-b. Este camino es un circuito cerrado donde todos los vértices son distintos, excepto el primero y el

último.

Figura 11.8

Contando los Caminos:

Contar todos los caminos posibles a mano puede ser tedioso y propenso a errores. Una forma más sistemática de abordar

este problema sería utilizar un algoritmo de búsqueda en un grafo, como la búsqueda en profundidad o en anchura.

Sin embargo, para este caso específico, podemos observar lo siguiente:

● Simetría del cubo: Debido a la simetría del cubo, muchos caminos son equivalentes. Por ejemplo, el camino a-h-

f es equivalente al camino a-g-f si rotamos el cubo.

● Combinaciones: Para cada cara que elegimos para comenzar el camino (frontal, trasera, superior o inferior), hay

múltiples opciones para continuar el camino.

Análisis del Problema y Construcción del Grafo Construyendo el Grafo:

Basándonos en la descripción del problema, podemos construir el siguiente grafo dirigido:

● Vértices: a, b, c, d, e, f, g, h, i, k, m

● Aristas:

○ a -> b, b -> c
 ○ c -> d, d -> b, b -> f

○ d -> e, e -> a

○ f -> a, f -> g

○ g -> d

○ k -> m

○ m -> i

b) Enumere los caminos simples de g a a.

Un camino simple es aquel en el que no se pasa por el mismo vértice más de una vez. Desde g, podemos llegar a a de las siguientes

maneras:

● g -> d -> e -> a

● g -> f -> a

c) ¿Cuál es el menor número de segmentos de autopista que tendrían que cerrarse para interrumpir el paso de b a d?

Para interrumpir el paso de b a d, debemos eliminar todas las aristas que conectan directamente o indirectamente a b con d. En

este caso, bastaría con eliminar la arista b

-> f, ya que esta es la única conexión directa entre el subgrafo de b y el subgrafo de d.

d) ¿Es posible salir de la ciudad e y regresar a ella, visitando una sola vez las otras ciudades?

No es posible. Para realizar un recorrido que visite todas las ciudades una sola vez y regrese al punto de partida (un

circuito Hamiltoniano), el grafo debe cumplir ciertas condiciones que este grafo no cumple.

e) ¿Cuál es la respuesta de la parte (d) si no es necesario regresar a c?

Incluso sin la restricción de regresar a c, no es posible encontrar un circuito Hamiltoniano en este grafo, ya que hay vértices

con grados impares (es decir, tienen un

número impar de aristas incidentes). Un teorema en teoría de grafos establece que un grafo solo tiene un circuito Hamiltoniano si

todos sus vértices tienen grado par.

f) ¿Es posible comenzar en alguna ciudad y viajar por todas las autopistas exactamente una vez? (Se permite visitar una ciudad

más de una vez y no es necesario regresar a la ciudad donde se inició el recorrido.)

Esta pregunta se refiere a la existencia de un camino euleriano. Un camino euleriano es un camino que recorre todas las aristas

de un grafo exactamente una vez. Para que exista un camino euleriano, el grafo debe ser conexo y todos los vértices deben

tener grado par, excepto posiblemente dos vértices que pueden tener grado impar (si el camino comienza y termina en vértices

diferentes). En este grafo, hay varios vértices con grado impar, por lo que no existe un camino euleriano.

Problema 8: Colocación de guardias en un almacén

Entendiendo el problema: Tenemos un grafo que representa un almacén, donde los vértices son cajas y las aristas son pasillos.

Queremos colocar guardias en algunas cajas de manera que cada caja esté vigilada directamente o a través de un solo pasillo.

Solución: Este problema se reduce a encontrar un conjunto mínimo de vértices tal que cada vértice del grafo esté adyacente a al

menos un vértice del conjunto. Este conjunto de vértices se conoce como conjunto dominante.

Encontrar el conjunto dominante mínimo es un problema NP-completo, lo que significa que no existe un algoritmo eficiente para

resolverlo en todos los casos. Sin embargo, existen algoritmos heurísticos y aproximados que pueden proporcionar buenas

soluciones en la práctica.

Para el grafo específico de la Figura 11.11: Necesitaríamos una representación más detallada del grafo (matriz de adyacencia, lista

de adyacencia) para aplicar un algoritmo de búsqueda de conjunto dominante. Sin embargo, podemos hacer una observación: si
colocamos un guardia en cada esquina del almacén (vértices a, c, h, k), es muy probable que todos los demás vértices estén

cubiertos.

Problema 9: Aristas en un ciclo

Enunciado: Sea G un grafo no dirigido sin lazos y sea (a, b) una arista de G. Demuestre que la arista (a, b) es parte de un ciclo si

y solo si al eliminarla (conservando los vértices a y b), G no se vuelve disconexo.

Demostración:

● Si (a, b) es parte de un ciclo: Si eliminamos (a, b), todavía existirá al menos un camino entre a y b a través del ciclo,

por lo que el grafo seguirá siendo conexo.

● Si al eliminar (a, b) el grafo no se vuelve disconexo: Si existe un camino entre a y b después de eliminar (a, b),

entonces, al agregar nuevamente la arista (a, b), formamos un ciclo.

Conclusión: La arista (a, b) pertenece a un ciclo si y solo si su eliminación no desconecta el grafo.

Problema 10: Grafo conexo que se desconecta al eliminar cualquier arista

Enunciado: Dar un ejemplo de un grafo conexo G tal que al eliminar cualquier arista de G se obtenga un grafo disconexo.

Solución: Este tipo de grafo se llama árbol. Un árbol es un grafo conexo y acíclico (sin ciclos). Si eliminamos cualquier arista de un

árbol, se rompe una conexión y el grafo se vuelve disconexo.

Ejemplo: Un simple ejemplo de un árbol es un camino lineal. Por ejemplo, un grafo con vértices a, b, c y aristas (a, b) y (b, c) es un

árbol. Si eliminamos cualquiera de estas aristas, el grafo se desconecta.

Conclusión: Cualquier árbol es un ejemplo de un grafo que cumple con las condiciones del problema.

Ejercicio 11

Premisa: G es un grafo que satisface la condición del ejercicio 10, es decir, es un grafo conexo que se desconecta al eliminar

cualquier arista.

a) ¿Debe G carecer de lazos?

● Sí. Un lazo es una arista que conecta un vértice consigo mismo. Si G tuviera un lazo, al eliminar cualquier otra arista,

el grafo seguiría siendo conexo debido al lazo. Por lo tanto, para cumplir la condición de que G se desconecte al

eliminar cualquier arista, G no puede tener lazos.

b) ¿Puede G ser un multigrafo?

● No. Un multigrafo permite múltiples aristas entre dos vértices. Si G fuera un multigrafo y tuviéramos dos aristas

paralelas entre dos vértices, al eliminar una, el grafo seguiría siendo conexo debido a la otra arista. Por lo tanto, para

cumplir la condición de que G se desconecte al eliminar cualquier arista, G no puede ser un multigrafo.

c) Si G tiene n vértices, ¿podemos determinar cuántas aristas tiene?

● Sí. Si G es un grafo conexo que se desconecta al eliminar cualquier arista, entonces G es un árbol. Un árbol con n

vértices tiene exactamente n-1 aristas.

Ejercicio 12

a) Si G=(V, E) es un grafo no dirigido con |V| = |E| y no hay lazos, demuestre que 2|E| ≤

|V|(|V| - 1).
 ● Demostración: En un grafo no dirigido sin lazos, cada arista conecta exactamente dos vértices. Por lo tanto, el

número total de aristas es como máximo la cantidad de pares de vértices distintos que podemos formar. La

cantidad de pares de vértices distintos en un conjunto de n elementos es n(n-1)/2. Entonces, 2|E| ≤ n(n-1), donde

n = |V|.

b) Establezca la desigualdad correspondiente en caso de que G sea dirigido.

● Demostración: En un grafo dirigido, cada arista va de un vértice a otro. Por lo tanto, el número máximo de

aristas es n(n-1), donde n = |V|. Entonces, |E| ≤ n(n-1).

Ejercicio 13

Enunciado: Sea G = (V, E) un grafo no dirigido. Definimos una relación R sobre V como aRb si y solo si existe un camino simple en

G de a a b. Demuestre que R es una relación de equivalencia. Describa la partición de V inducida por R.

Demostración:

● Reflexividad: Para cualquier vértice a, existe un camino trivial de a a a (de longitud 0). Por lo tanto, aRa

para todo a en V.

● Simetría: Si existe un camino simple de a a b, entonces existe un camino simple de b a a invirtiendo el orden de los

vértices en el camino. Por lo tanto, si aRb, entonces bRa.

● Transitividad: Si aRb y bRc, entonces existe un camino simple de a a b y otro de b a c. Concatenando estos caminos

(eliminando posibles vértices repetidos), obtenemos un camino simple de a a c. Por lo tanto, si aRb y bRc, entonces

aRc.

Dado que R es reflexiva, simétrica y transitiva, es una relación de equivalencia.

Partición de V inducida por R: La relación de equivalencia R divide a V en clases de equivalencia. Cada clase de equivalencia contiene

todos los vértices que están

conectados por un camino simple. Es decir, cada clase de equivalencia corresponde a una componente conexa del grafo G.

¿Qué es un recorrido de árbol?

Imagina un árbol genealógico. Para listar a todos los miembros de una familia, puedes hacerlo de diferentes formas:

empezando por el abuelo (preorden), luego sus hijos y nietos (inorden), o terminando con el abuelo (postorden).

En programación, un árbol es una estructura de datos jerárquica que se utiliza para representar relaciones entre elementos. Un

recorrido de árbol es una forma de visitar todos los nodos de un árbol en un orden específico.

Los tres recorridos principales son:

● Preorden:

○ Visitas la raíz primero.

○ Luego, recorres el subárbol izquierdo.

○ Finalmente, recorres el subárbol derecho.

○ Ejemplo: En un árbol genealógico, sería listar primero al abuelo, luego sus hijos y finalmente sus nietos.

● Inorden:

○ Recorres el subárbol izquierdo primero.

○ Luego, visitas la raíz.

○ Finalmente, recorres el subárbol derecho.

○ Ejemplo: En un árbol genealógico, sería listar primero los hijos mayores, luego al padre (raíz) y finalmente

los hijos menores.

● Postorden:
 ○ Recorres el subárbol izquierdo primero.

○ Luego, recorres el subárbol derecho.

○ Finalmente, visitas la raíz.

○ Ejemplo: En un árbol genealógico, sería listar primero a los nietos, luego a los hijos y finalmente al abuelo.

¿Para qué sirven estos recorridos?

La elección del recorrido depende de la tarea que quieras realizar con el árbol. Por ejemplo:

● Preorden:

○ Crear una copia del árbol.

○ Evaluar una expresión aritmética.

● Inorden:

○ Obtener los elementos de un árbol de búsqueda binaria en orden ascendente.

● Postorden:

○ Liberar la memoria de un árbol.

○ Evaluar una expresión posfija.