Diario de Clases

Recordemos que en días pasados hablamos de grafos conexos e introducimos los grafos planos, mapas y la coloración de grafos.

La coloración de grafos es una forma de asignar etiquetas, llamadas colores, a elementos del grafo. En una coloración los vértices de un grafo cumplen que ningún vértice adyacente comparte el mismo color. Un caso particular es la coloración de las aristas: asigna colores a cada arista tal que aristas adyacentes no compartan el mismo color. El proceso lo podemos repetir con las caras de un grafo plano, asignando un color a cada cara o región tal que caras que compartan una frontera común tengan colores diferentes. En este caso se trata de un grafo plano.

Un grafo plano (o planar según referencias) es un grafo que puede ser dibujado en el plano sin que ninguna arista se cruce. Un mapa es un grafo plano en el que nos interesan las caras entre las aristas.

Un de los resultado más interesante de los grafos planos es el Teorema de Euler:

Si un grafo simple plano conexo tiene $v$ vértices, $a$ aristas y $c$ caras, entonces $v − a + c = 2$

Un camino euleriano es un camino que pasa por cada arista una y solo una vez. Un ciclo o circuito euleriano es un camino cerrado que recorre cada arista exactamente una vez. Un grafo se denomina grafo euleriano si un circuito euleriano.

Propiedades de los grafo eulerianos:

• Un grafo conexo y no dirigido se dice que es euleriano si cada vértice tiene un grado par.
• Un grafo no dirigido es euleriano si es conexo y si se puede descomponer en uno con los vértices disjuntos.
• Si un grafo no dirigido G es euleriano entonces su gráfo-línea L(G) se dice que es también euleriano.
• Un grafo dirigido es euleriano si es conexo y cada vértice tiene grados internos iguales a los externos.
• Un grafo no dirigido se dice que es susceptible de ser recorrido si es conexo y dos vértices en el grafo tienen grado impar.

El siguiente resultado nos sirve para determinar si un grafo contiene un camino euleriano o un ciclo:

Dado un grafo conexo (no existen nodos aislados) y no dirigido G, si G tiene exactamente dos vértices de grado impar, entonces G tiene un camino euleriano no cerrado. En caso de que todos los vértices tengan grado par, G tiene un ciclo euleriano.

Un camino hamiltoniano es un camino de un grafo que visita todos los vértices del grafo una sola vez. Si además el último vértice visitado es adyacente al primero, el camino es un ciclo hamiltoniano. Un grafo que contiene un ciclo hamiltoniano se dice grafo hamiltoniano.

Ejempos de grafos Hamiltonianos:

• Todos los grafos ciclos son hamiltonianos.
• Todos los sólidos platónicos, (tetraedro, el cubo, el octaedro, el dodecaedro y el icosaedro.) considerados como grafos, son hamiltonianos

Hay que tener en cuenta que cualquier ciclo hamiltoniano puede ser convertido en un camino hamiltoniano si se elimina cualquiera de sus aristas, pero un camino hamiltoniano puede ser extendido en ciclo sólo si los vértices de los extremos son adyacentes.

Un resultado que puede ayudarnos a distinguirlos es el siguiente:

Un grafo con n vértices (n > 3) es hamiltoniano si cada vértice tiene grado mayor o igual a n/2.

$\quad$

Si tenemos un grafo $G=(V,E)$ donde $V=\{v_1,…,v_n\}$, llamamos matriz de adyacencia del grafo a la matriz cuadrada nxn, $A=[a_{ij}]$, donde
$$a_{ij}=\left\{\begin{matrix}1 & \mbox{si } \{v_i,v_j\}\in E\\ 0 & \mbox{si } \{v_i,v_j\}\not\in E\end{matrix}\right.$$
En caso de que hubiera un bucle en $v_i$ $a_{ii}=1$. Si es el multigrafo $a_{ij}$ seríe en número de arcos que conecten los vértices.

La matriz de adyacencia de un grafo es simétrica, pues la arista une dos vértices independiente del comienzo y el final, pero si el grafo es un digrafo entonces los arcos sólo van en una dirección y $a_{ij}$ no tiene por qué coincidir con $a_{ji}$.

Del mismo modo podemos construir la matriz de incidencia, donde las columnas de la matriz representan las aristas del grafo y las filas representan a los distintos nodos. Por cada nodo unido por una arista, ponemos un uno 1 en el lugar correspondiente, y llenamos el resto de las ubicaciones con ceros 0. Un lazo cuenta doble. Si es un digrafo atenderemos como 1 si es un vertice de salida y -1 si es de entrada.

Terminamos viendo propiedades de estas matrices.

Ejercicio: Determinar la matriz de adyacencia y de incidencia del grafo

Comenzamos con la teoría de grafos. Para adentrarnos en este tema hablamos de dos ejemplos que nos ilustran perfectamente nuestro contenido:

• El problema de los puentes de Königsberg
• El problema matemático que nació en un campo de trabajo de la Segunda Guerra Mundial

Hoy hemos trabajado las diferentes definiciones que utilizaremos: grafos, digrafos y multigrafos y otras más, siguiendo la bibliografía recomendada. Además hemos visto algunas de sus propiedades.

Bibliografía recomendada

• Capítulo 2 de Números y Grafos, Juan de Burgos, ingebook
• Temas 7 y 9 de Matemática Discreta, Félix García, Edt. Thomson

También os recomiendo el visionado de este vídeo:

• Euler: una superestrella

Hoy hemos recordado la definición del conjunto de las permutaciones $S_n$, donde un elemento será de la forma:
$$\displaystyle \left(\begin{array}{cccccccc}1 & 2 & 3 & 4 & 5 \cdots & n\\ \sigma_1 & \sigma_2 & \sigma_3 & \sigma_4 & \sigma_5 \cdots & \sigma_n \end{array}\right) .$$
Siendo $\sigma_i\in I=\{1,2,3,4,…,n\}$ y de modo que $\sigma_i\neq \sigma_j\forall i\neq j$.
Hemos visto que $S_n$ con la operación composición de permutaciones, $\circ$, le confiere una estructura de grupo; $(S_n,\circ)$ es un grupo.

Definimos un desarreglo como una permutación $\sigma\in S_n$ talque $\sigma_i\neq i\forall i\in I$. El propósito de la clase de hoy ha sido contar el número de desarreglos que podemos encontrar en el conjunto $S_n$.

Para vuestra ayuda consultar Derangement.

Terminamos los contenidos de la Teoría Combinatoria con la inclusión del estudios de las particiones.

Una partición del conjunto A es una familia P de subconjuntos no vacíos de A, disjuntos dos a dos, cuya unión es A. Es decir, $P= \{A_i: i\in I\}$, donde se cumple:

• Para cada $i\in I, A_i\subseteq A y A_i\neq\varnothing $
• Para cada par $i\neq j$, $A_i\cap A_j = \varnothing $
• $\cup_{i\in I} A_i = A$

El número de particiones posibles para un conjunto finito sólo depende de su cardinal $n$, y se llama el número de Bell, $B_n$. Los primeros números de Bell son B₀ = 1, B₁ = 1, B₂ = 2, B₃ = 5, B₄ = 15, B₅ = 52, B₆ = 203, …

Los números de Bell cumplen una relación derecurrencia muy interesante:
$$B_n=\sum_{k=0}^{n-1}B_k\binom{n-1}{k}$$

Un caso particular de contar particones son los números de Stirling de segunda especie:
$$S(n,k)=\frac{1}{k!}\sum_{i=0}^k(-1)^i\binom{k}{i}(k-i)^n.$$

Este resultado nos da pie a contar las aplicaciones suprayecivas entre dos conjuntos finitos.

Teorema: Sean $A$ y $B$ dos conjuntos finitos de cardinal $n$ y $m$ respectivamente. El número de aplicaciones suprayectivas de $A$ en $B$ es de $$m!S(n,m).$$

El principio de inclusión-exclusión permite calcular el cardinal de la unión de varios conjuntos, mediante los cardinales de cada uno de ellos y todas sus posibles intersecciones.
Si consideramos que tenemos dos conjuntos finitos $A$ y $B$, resultará:
$$|A \cup B| = |A| + |B| – |A \cap B|.$$

Imaginemos que tenemos tres conjuntos finitos:
$$|A \cup B \cup C| = |A| + |B| + |C| – |A \cap B| – |A \cap C| – |B \cap C| + |A \cap B \cap C|.$$

Esto lo podemos generalizar. Si A₁, …, A_n son conjuntos finitos entonces:

$$\begin{align}\biggl|\bigcup_{i=1}^n A_i\biggr| & {} =\sum_{i=1}^n\left|A_i\right|-\sum_{i,j\,:\,1 \le i < j \le n}\left|A_i\cap A_j\right| \\& {}\qquad +\sum_{i,j,k\,:\,1 \le i < j < k \le n}\left|A_i\cap A_j\cap A_k\right|-\ \cdots\ + \left(-1\right)^{n+1} \left|A_1\cap\cdots\cap A_n\right|\end{align}$$

Hoy terminamos la parte de los número binomiales extendiendo el teorema del binomio al conocido resultado de la fórmula de Leibniz: Dados $m$ enteros y un natural $n$, se tiene
$$(x_1 + x_2 + \cdots + x_m)^n = \sum_{k_1+k_2+\cdots+k_m=n} {n \choose k_1, k_2, \ldots, k_m} \prod_{1\le t\le m}x_{t}^{k_{t}}$$

Aquí definimos los coeficientes multinomiales como
$$
{n \choose k_1, k_2, \ldots, k_m} =\frac{n!}{k_1!· k_2! \cdots k_m!}
$$
donde $k_1+ k_2+ \ldots+ k_m=n$. Recordad que esto era equivalente a las permutaciones con repetición donde se repetían determinados elementos un determinado numero de veces.

Otro equivalente que podemos encontrar son los coeficientes $\left(\!\!{n \choose m}\!\!\right)$ que hacen referencia a las combinaciones con repetición:
$$\left(\!\!\!\!{n \choose m}\!\!\!\!\right)={n+m-1 \choose m}$$

Esto nos da pie a deducir que el número de coeficientes multinomiales de la fórmula de Leibniz es
$${n+m-1 \choose m-1}$$ que es coincidente con
$${n+m-1 \choose m-1}=\left(\!\!\!\!{m \choose n}\!\!\!\!\right)={m+n-1 \choose n},$$
ya que se corresponde con todos los posibles monomios $x_1^{k_1} \cdot x_2^{k_2} \cdots x_m^{k_m}$
Otra deducción observamos si consideramos $x_1 = x_2 = \cdots = x_m=1$, en tal caso la suma de los coeficientes multinomiales de la fórmula de Leibniz es
$$\sum_{k_1+k_2+\cdots+k_m=n} {n \choose k_1, k_2, \ldots, k_m}=m^n$$

El pasado día vimos el número binomial y dejamos las bases puestas para enunciar el Teorema del Binomio:

$$(x+y)^n=\sum_{k=0}^n {n \choose k}x^{n-k} y^k$$

Con este teorema podemos hacer fáciles ejercicios que resultan difíciles en su planteamiento.

Un resultado interesante es el siguiente. Utilizando el teorema del binomio podemos ver que

$$(1+x)^n=\sum_{k=0}^n {n \choose k}x^{k}$$

Comenzamos definiendo el número binomial ${n\choose k}$, como el número de subconjuntos con k elementos, escogidos de un conjunto con n. Esta definición coincide con la combinaciones, por ese motivo la fórmula de calcularlo debe ser la misma
$$
{n\choose k} = \frac{ n(n-1)(n-2)\cdots (n-k+1)}{1\cdot 2\cdot 3 \cdots (k-1)\cdot k}
$$
Los coeficientes binomiales cumple propiedades muy interesantes como
$$
\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k} \quad \mbox{para todos los números enteros }n,k>0.
$$
Esta propiedad es muy importante y aparece en el El teorema de Pascal.

Las combinaciones las introducimos para determinar en número de subconjuntos que podemos hacer con los elementos de un conjunto. Sabemos que el total serían el cardinal de las partes de un conjunto, pero en este caso queremos conocer los subconjuntos con un determinado cardinal. Así definimos las combinaciones de n elementos tomados de $m$ en $m$, con $m<n$, como los subconjuntos de $m$ elementos que podemos hacer con los $n$ elementos de un conjunto.

Como hemos visto hoy ese número será $$C_{n,m}=\frac{V_{n,m}}{P_m}=\frac{n!}{m!\,(n-m)!}$$

Otra variación que podemos hacer es un número determinado de objetos elegidos entre varios conjuntos de objetos. Por ejemplo, tenemos limones, naranjas y peras suficientes para repartir un pieza a cada uno de nuestros once alumnos. ¿De cuantas formas podríamos hacerlo? Esta manera de repartir, en la que como se aprecia podemos repetir alguno de los objetos, es lo que denominamos combinaciones con repetición. Y el cómputo total será
$$CR_{n,m}=C_{n+m-1,m}$$
Observar que en este tipo de recuento es común que $n<m$.

Dos aplicaciones prácticas donde utilizamos las combinaciones:

Sean $k,n\in\mathbb{N}$. El número de soluciones enteras no negativas(es decir, $x_i\geq 0 $) de la ecuación $$x_1+x_2+\ldots+x_n=k$$ es $$CR_{n,k}=C_{n+k-1,k}$$

Sean $k,n\in\mathbb{N}$. El número de soluciones naturales (es decir, $x_i< 0 $) de la ecuación $$x_1+x_2+\ldots+x_n=k$$ es $$C_{k-1,k-n}$$