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.

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 definido grafos, digrafos y multigrafos y otras más, siguiendo la bibliografía recomendada. Además hemos visto algunas de sus propiedades.

Otra definición importante es la de matriz de un grafo. 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

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}$$

Recordamos 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 es contar el número de desarreglos que podemos encontrar en el conjunto $S_n$.

Para vuestra ayuda consultar Derangement.

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.

Para el próximo día terminamos la parte de los números 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}}$$

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.

Este “triángulo” surge de cuando expresamos los coeficientes de los desarrollo binómico $(x+y)^n$, que no lleva al Teorema del Binomio:

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

El pasado día definimos la combinaciones de elementos tomados de $m$ en $m$, con $m<n$, como el número de subconjuntos de $m$ elementos que podemos hacer con los $n$ elementos de un conjunto: $$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$.

Hasta hoy hemos visto:

• Variaciones de $n$ elementos tomados de $m$ en $m$, al número de aplicaciones inyectivas que podemos hacer del conjunto $A$, de cardinal $m$, en el conjunto $B$, de cardinal $n$, $m\leq n$. $V_{n,m}=\frac{n!}{(n-m)!}.$
• Permutaciones de $n$ elemento, al número de aplicaciones biyectivas que podemos hacer del conjunto $A$, de cardinal $n$, en el conjunto $B$, de cardinal $n$, o en él misno.. $P_{n}=n!$.
• Variaciones con repetición de $m$ (0<$m$) elementos de un conjunto de $n$ elementos (0<$n$), a las aplicaciones de un conjunto de $m$ elementos de un conjunto de $n$ elementos, $VR_{n,m}=n^m$
• Permutación circular, aquella permutación que no importa por donde comience, $PC_n=P_{n-1}=(n-1)!.$

Por último podemos considerar una permutación de los elementos de un conjunto donde se repiten alguno de ellos. Una permutación con repetición de un conjunto $A=\{x_i;i=1,…,n\}$, quedará identificada por una disposición de la forma
$$(x_1,\overset{\underbrace{r_1}}{\ldots},x_1,x_2,\overset{\underbrace{r_2}}{\ldots},x_2,\ldots,x_n,\overset{\underbrace{r_n}}{\ldots},x_n)$$
donde $r_1+r_2+\ldots+r_n\in\mathbb{N}$ determina el número de elementos totales. En ese caso el número total de permutación con repetición del conjunto $A$, donde cada elemento $x_i\in A$ sae repite $r_i\mathbb{N}$ veces es
$$PR_{r_1+r_2+\ldots+r_n}^{r_1,r_2,\ldots,r_n}=\frac{(r_1+r_2+\ldots+r_n)!}{r_1!\,r_2!\,\ldots\,r_n!}.$$

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)!}$$

El pasado día terminamos introduciéndo las variaciones. Hoy comenzamos con las variaciones con repetición. Llamaremos variaciones con repetición de $m$ (0<$m$) elementos de un conjunto de $n$ elementos (0<$n$) al número $$VR_{n,m}=n^m,$$ y se corresponde con las aplicaciones de un conjunto de $m$ elementos de un conjunto de $n$ elementos. Llamaremos permutaciones de un conjunto de $n$ elementos (0<$n$) al número $$P_n=n!,$$ y se corresponde con las aplicaciones biyectivas de un conjunto de $n$ elementos sobre un subconjunto de $\mathbb{N}$ del mismo cardinal. Otra forma de definir la permutación de un conjunto de $n$ elementos es como una siposición ordenada de los elementos $n$ elementos. Esa disposición la podemos representar como una $n$-tupla. Si una $n$-tupla circular la entendemos como la $n$-tupla donde hemos unido el inicio con el fin, podemos considerar una permutación circualr como una $n$-tupla circular, donde dos permutaciones circulares son iguales si cada elemento tiene a derecha e izquierda los mismos compañeros. De esta forma, En número de permutaciones circulares que podemos hacer con un conjunto de $n>0$ elementos es $$PC_n=P_{n-1}=(n-1)!.$$

Hoy hemos tratado los principios básicos de conteo:

• Principio de adición
• Principio de multiplicación
• Principio de distribución

Introducimos las primeras de las técnicas básicas de conteo: la variaciones. Llamaremos variaciones de $n$ elementos tomados de $m$ en $m$, al número de aplicaciones inyectivas que podemos hacer del conjunto $A$, de cardinal $m$, en el conjunto $B$, de cardinal $n$, $m\leq n$. Para calcular las variaciones utilizaremos:

$$V_{n,m}=n(n-1)(n-2)\cdots(n-m+1)=\frac{n!}{(n-m)!}.$$