Teoría de Conjuntos y Grafos: Conceptos y Aplicaciones

Teoría de Conjuntos: Cardinalidad y Conjuntos Elementales

Si A, B, y C son tres conjuntos finitos, entonces:

• |A ∪ B| = |A| + |B| - |A ∩ B|
• Si A ∩ B = ∅, entonces |A ∪ B| = |A| + |B|
• (Principio Complementario) Si C ⊂ A (esto quiere decir que todo elemento de C es también elemento de A) y denotamos C' = A \ C al conjunto de todos los elementos de A que no son elementos de C (C' es el complemento de C), entonces |C'| = |A| - |C|
• Si A × B es el producto cartesiano de A y B, es decir, A × B = {(a, b) | a ∈ A y b ∈ B}

En la práctica, para calcular |A|:

• Descomponemos el conjunto A como uniones, complementarios y productos cartesianos de conjuntos fáciles (conjuntos elementales).
• Usaremos la regla del teorema anterior para calcular |A| a partir del número de elementos de cada uno de los conjuntos elementales.

Conjuntos Elementales: Combinaciones, Permutaciones y Variaciones

Conjuntos elementales: {combinaciones, permutaciones, variaciones} {con repetición, sin repetición}.

¿Cuántos elementos tienen cada uno de estos conjuntos?

Variaciones con Repetición

¿Cuántas apuestas diferentes pueden hacerse en la quiniela? Cada apuesta es una variación con repetición.

Definición: Si N, M ⊂ ℕ, una variación con repetición de N elementos {a₁, ..., a_n} tomados de M en M es una lista ordenada de M elementos posiblemente repetidos elegidos entre {a₁, ..., a_n}.

Ejemplo: Cada apuesta de la quiniela es una variación con repetición de 3 elementos ({1, X, 2}) tomados de 15 en 15.

Teorema: Si N, M ⊂ ℕ, entonces el cardinal del conjunto de todas las variaciones con repetición de N elementos de M en M es VR_n,m = N^m.

Ejemplo: Como cada quiniela es una variación con repetición de 3 elementos tomados de 15 en 15, entonces el número de apuestas diferentes es VR_3,15 = 3¹⁵ = 14,348,907.

Variaciones sin Repetición

Ejemplo: En una media maratón participan 154 atletas. ¿Cuántos podios diferentes pueden producirse? (Podio: medalla de oro, de plata, de bronce). Cada podio es una variación sin repetición.

Definición: Si N, M ⊂ ℕ (N ≥ M), una variación sin repetición de N elementos {a₁, ..., a_n} tomados de M en M es una lista ordenada de M elementos distintos elegidos entre {a₁, ..., a_n}.

Ejemplo: Cada podio es una variación de 154 elementos tomados de 3 en 3.

Teorema: Si N, M ⊂ ℕ (N ≥ M), entonces el número de variaciones sin repetición de N elementos tomados de M en M es V_n,m = N! / (N - M)! = N(N - 1)(N - 2)...(N - M + 1).

El número de podios es V_154,3 = 154 × 153 × 152 = (154! / 151!).

Permutaciones sin Repetición

Ejemplo: Si en la liga BBVA hay 20 equipos, ¿cuántas clasificaciones finales pueden producirse al terminar la temporada? Cada clasificación es una permutación.

Definición: Si N ⊂ ℕ, una permutación de N elementos es una variación sin repetición de N elementos tomados de N en N, es decir, N = M.

Teorema: Si N ⊂ ℕ, el número de permutaciones sin repetición de N elementos es P_n = N!.

Ejemplo: Cada clasificación de la liga BBVA es una permutación de 20 elementos, por tanto, el número de clasificaciones posibles es P₂₀ = 20! = 2,432,902,008,176,640,000.

Permutaciones con Repetición

No son un caso particular de variaciones con repetición.

Ejemplo: ¿Cuántas palabras (con sentido o sin él) se pueden calcular reordenando las letras de la palabra MATEMÁTICAS?

Definición: Una permutación con repetición de longitud n ∈ ℕ y tipo n₁, n₂, ..., n_k (n₁, n₂, ..., n_k ∈ ℕ y n = n₁ + n₂ + ... + n_k) es una lista ordenada de longitud n donde un símbolo aparece n₁ veces, otro símbolo aparece n₂ veces y otro símbolo aparece n_k veces. En permutaciones con repetición sabemos exactamente cuántas veces aparece cada símbolo.

El número de permutaciones con repetición de longitud n y tipo n₁, n₂, ..., n_k (n₁, n₂, ..., n_k ∈ ℕ y n = n₁ + n₂ + ... + n_k) es PR_{n;n1,n2,...,nk} = n! / (n₁! n₂! ... n_k!).

Ejemplo: Cada palabra que obtenemos reordenando todas las letras de “MATEMÁTICAS” es una permutación con repetición de longitud 11 y tipo (2, 3, 2, 1, 1, 1, 1). Por tanto, el número de palabras obtenidas es PR_{11;2,3,2,1,1,1,1} = 11! / (2! 3! 2! 1! 1! 1! 1!) = 11! / (2! 3! 2!).

Combinaciones sin Repetición

Ejemplo: ¿Cuántas apuestas diferentes podemos hacer en un sorteo de la lotería primitiva?

Definición: Si n, k ∈ ℕ (n ≥ k), una combinación de n elementos {a₁, ..., a_n} tomados de k en k es una lista no ordenada de k elementos distintos elegidos entre {a₁, ..., a_n}.

Teorema: Si n, k ∈ ℕ (n ≥ k), el número de combinaciones de n elementos tomados de k en k es C_n,k = n! / (k! (n - k)!).

Definición: Si n, k ∈ ℤ, n ≥ k ≥ 0, el número combinatorio"n sobre " es el valor C_n,k = n! / (k! (n - k)!).

Ejemplo: Cada apuesta de la lotería primitiva es una combinación de 49 elementos (los números del 1 al 49) tomados de 6 en 6, por tanto, el número de apuestas posibles es C_49,6 = 49! / (6! 43!).

Veamos unas propiedades de los números combinatorios:

Teorema: Si n, k ∈ ℤ, n ≥ k ≥ 0, entonces:

(No se incluyen las propiedades en el JSON por falta de información en el texto original)

La propiedad (3) permite dar un método recursivo para calcular C_n,k usando los triángulos de Tartaglia y Pascal:

El triángulo de Pascal (= Tartaglia) permite recordar el binomio de Newton:

Combinaciones con Repetición

Ejemplo: ¿Cuántas fichas tiene el juego de dominó?

Definición: Una combinación con repetición de n elementos tomados de k en k (n, k ∈ ℕ) es una lista no ordenada de k elementos posiblemente repetidos elegidos entre {a₁, ..., a_n}.

Teorema: Si n, k ∈ ℕ, entonces el número de combinaciones con repetición de n elementos tomados de k en k es CR_n,k = (n + k - 1)! / (k! (n - 1)!).

Cada ficha de dominó es una combinación con repetición de 7 elementos (los números de 0 a 6) tomados de 2 en 2, por tanto, el número de fichas es CR_7,2 = (7 + 2 - 1)! / (2! (7 - 1)!) = 8! / (2! 6!) = (7 × 8) / (1 × 2) = 28.

En la práctica, nos piden calcular cuántos elementos tiene un conjunto A. Para ello seguimos el siguiente método:

• Describir cada elemento de A como una lista de (nombres, números, colores...).
• Tomados de un elemento A (que es una lista) y nos hacemos las siguientes preguntas:
• ¿Influye el orden de la lista?
  • Si al cambiar de orden entre 2 elementos de la lista nos sale otro elemento diferente, entonces sí influye el orden de la lista.
  • Si al cambiar el orden de 2 elementos de la lista nos sale el mismo resultado, entonces no influye el orden.
• ¿Se pueden repetir los elementos?
  • Si en una lista pueden aparecer 2 elementos repetidos, entonces sí se pueden repetir.
  • En caso contrario, no se puede repetir.

En función de las respuestas, usamos el siguiente cuadro (tabla anterior).

¿Cómo distinguir entre variaciones con repetición y permutaciones con repetición? Si sabemos exactamente cuántas veces se repite cada elemento, son permutaciones con repetición. Si no sabemos si se repite o no o cuántas veces se repite, son variaciones con repetición.

¿Cómo distinguir entre variaciones sin repetición y permutaciones sin repetición? No es necesario, pues las permutaciones son un caso particular de variaciones.

Teoría de Grafos: Conceptos Básicos y Tipos de Grafos

Tema 4: Teorema de Grafos

¿Qué es un Grafo Simple (No Dirigido)?

Es una pareja de conjuntos G = (V, E) donde:

1. V es un conjunto finito. Los elementos v ∈ V se llaman vértices del grafo.
2. E es un subconjunto del conjunto de pares de vértices E ⊆ {(v_i, v_j) | v_i, v_j ∈ V}. Los elementos (v_i, v_j) ∈ E se llaman aristas del grafo.

Ejemplo: Si tenemos G = (V, E) donde V = {1, 2, 3, 4} y E = {(1, 2), (1, 3), (1, 4), (4, 4)}, este es un grafo que se representa... (falta la representación gráfica en el texto original).

Definición: Una representación pictográfica de un grafo G = (V, E) es una identificación de vértices del grafo en puntos del plano y aristas con líneas del plano entre los puntos correspondientes.

La representación pictórica no es única.

Ejemplo: Si tenemos el grafo del ejemplo anterior, podemos dar muchas representaciones distintas (falta la representación gráfica en el texto original).

Grado de un Vértice y Sucesión de Grados

Definición: Si G = (V, E) es un grafo y v ∈ V, el grado de v es el número de aristas de G que contienen a v. Se suele denotar gr(v). Si V = {v₁, ..., v_n}, la sucesión de grados es gr(v₁), gr(v₂), ..., gr(v_n).

La sucesión de grados da mucha información sobre el grafo, por ejemplo, nos dice cuántos vértices tiene.

Teorema de Euler: Si tenemos un grafo G = (V, E) y sus aristas son de la forma (v, v), entonces el número de aristas (|E|) se puede calcular como: 2|E| = Σ gr(v), es decir, si V = {v₁, ..., v_n}, entonces |E| = 1/2 (gr(v₁) + ... + gr(v_n)).

¿Qué pasa si hay aristas de la forma (v, v)? En este caso, al calcular el grado de cada v, las aristas (v, v) las contamos 2 veces. De esta forma, el teorema anterior vale también cuando hay aristas del tipo (v, v).

En el ejemplo anterior: gr(1) = 3, gr(2) = 1, gr(3) = 1, gr(4) = 3.

Matriz de Adyacencia

¿Cómo podemos almacenar un grafo? Usando una matriz.

Definición: Si tenemos un G = (V, E), una matriz de adyacencia de G es una matriz cuadrada que cumple: tiene tantas filas como vértices tiene G. Si V = {v₁, ..., v_n} y la matriz de adyacencia la denotamos como A = [a_ij], entonces a_ij = {1 si (v_i, v_j) es arista de G y 0 si (v_i, v_j) no es arista de G}.

Grafos Notables

Definición: Si n es un número natural (n ∈ ℕ), el grafo completo de n vértices es el grafo K_n = (V, E) que tiene V = {v₁, ..., v_n} y todas las aristas posibles salvo las aristas (v_i, v_i).

Ejemplo: Veamos la representación pictórica de varios grafos completos (falta la representación gráfica en el texto original).

¿Cuál es el grado de cada vértice de K_n? gr(v₁) = n - 1, gr(v₂) = n - 1, ..., gr(v_n) = n - 1. Por tanto, el número de aristas de K_n es (usando el Teorema de Euler) |E| = 1/2 (gr(v₁) + ... + gr(v_n)) = n × (n - 1) / 2.

¿Cuál es la matriz de adyacencia de K_n? (falta la matriz en el texto original).

Definición: Si n ∈ ℕ, la estrella S_n es un grafo S_n = (V, E) donde: V = {c, v₁, v₂, ..., v_n} (n + 1 vértices) y E = {(c, v_i) | 1 ≤ i ≤ n}.

Gráficamente (falta la representación gráfica en el texto original).

¿Cuál es la sucesión de grados de S_n? gr(c) = n, gr(v₁) = gr(v₂) = ... = gr(v_n) = 1. Por tanto, el número de aristas de S_n (usando el Teorema de Euler) es |E| = 1/2 (gr(c) + gr(v₁) + ... + gr(v_n)) = 2n / 2 = n.

Por último, la matriz de adyacencia de S_n es una matriz (n + 1) × (n + 1) de la forma (falta la matriz en el texto original).

Definición: Si n ∈ ℕ (n ≥ 2), el ciclo C_n es un grafo C_n = (V, E) tal que: V = {v₁, ..., v_n} y E = {(v₁, v₂), (v₂, v₃), ..., (v_n-1, v_n), (v_n, v₁)}.

Gráficamente (falta la representación gráfica en el texto original).

Vamos a calcular el número de aristas y para ello calculamos primero el grado de cada vértice: gr(v₁) = gr(v₂) = ... = gr(v_n) = 2. Por tanto, usando el Teorema de Euler, |E| = 1/2 (gr(v₁) + ... + gr(v_n)) = n. La matriz de adyacencia de C_n es una matriz de la forma (falta la matriz en el texto original).

Definición: Si n ∈ ℕ, el grafo rueda W_n es el grafo W_n = (V, E) dado por: V = {c, v₁, ..., v_n} (n vértices), E = {(c, v_i) | 1 ≤ i ≤ n} ∪ {(v₁, v₂), (v₂, v₃), ..., (v_n-1, v_n), (v_n, v₁)}.

Gráficamente (falta la representación gráfica en el texto original). |E| = 1/2 (gr(c) + gr(v₁) + ... + gr(v_n)) = 4n / 2 = 2n y la matriz de adyacencia es (falta la matriz en el texto original).

Grafos Bipartidos

Definición: Un grafo G = (V, E) es bipartido si podemos expresar V como V = A ∪ B de forma que:

• A ∩ B = ∅ (A y B es una partición de V)
• A, B ≠ ∅
• Si (v, n) ∈ E, entonces v ∈ A y n ∈ B ó v ∈ B y n ∈ A.

¿Cómo sabemos si un grafo G = (V, E) es bipartido o no? Usamos el siguiente algoritmo:

1. Elegimos al azar un vértice y lo resolvemos como A.
2. Elegimos alguna arista que salga del vértice anterior y el vértice destino lo llamamos B.
3. Elegimos una arista (no elegida antes) que salga de B y el destino lo llamamos A.
4. Repetimos hasta haber elegido todas las aristas.

Una vez hemos terminado, si cada vértice tiene solo una letra, entonces G es bipartido. Si un vértice tiene dos letras diferentes, entonces no es bipartido.

Nota: Si tenemos un grafo G = (V, E) de forma que (w, v), (v, w), (w, u) ∈ E (es decir, G tiene un triángulo), entonces G no es bipartido.

Ejemplo: C₄ es bipartido y K₄ no lo es.

Definición: Si n, m ∈ ℕ, el grafo bipartido completo K_n,m es un grafo completo K_n,m = (V, E) tal que: V = A ∪ B con A = {v₁, ..., v_n}, B = {w₁, ..., w_m}, K_n,m es bipartido con partición A, B. Tiene todas las aristas posibles.

Ejemplo: (falta la representación gráfica en el texto original).

Caminos, Conexión, Grafos Eulerianos y Hamiltonianos

Definición: Si G = (V, E) es un grafo, un camino que empieza en v y termina en w es una lista ordenada de aristas de G de la forma: (v₁, v₂), (v₂, v₃), (v₃, v_k), ..., (v_k, w). La longitud de un camino es el número de aristas que forma la línea ordenada.

¿Cuántos caminos de longitud k hay entre 2 vértices v_i, v_j?

Teorema: Si G = (V, E) es un grafo con V = {v₁, ..., v_n} y matriz de adyacencia A, entonces el número de caminos de longitud k que empieza en v_i y termina en v_j es el elemento que está en la fila i y columna j de A^k = A × A × A × ... × A.

Definición: Un grafo G es conexo si entre cualesquiera 2 vértices v_i, v_j hay un camino que empieza en v_i y termina en v_j.

Definición: Si G = (V, E), decimos que un camino es euleriano si cumple: contiene todas las aristas de G sin repetir ninguna.

Ejemplo: En C₅, (v₁, v₂), (v₂, v₃), (v₃, v₄), (v₄, v₅), (v₅, v₁) es un camino euleriano.

No siempre existen caminos eulerianos. Ejemplo: Si tenemos K₄, no hay caminos eulerianos.

¿Cómo sabemos cuándo hay y cuándo no?

Teorema: Si G = (V, E) es conexo, entonces:

1. Si todos los vértices tienen grado par, entonces existen caminos eulerianos.
2. Si hay como mucho 2 vértices de grado impar, entonces existen caminos eulerianos.
3. Si hay 3 vértices o más con grado impar, no hay caminos eulerianos.

Ejemplo: Recordemos el problema de los puentes de Königsberg (falta la representación gráfica en el texto original).