MAD: Mapas y coloración de grafos.

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$

Ejercicio: Estudiar si el grafo representado por la matriz [0,1,0,1,0,0; 1,0,1,0,0,0; 0,1,0,1,1,1; 1,0,1,0,1,1;0,0,1,1,0,0; 0,0,1,1,0,0] es plano.
Posted in: Matemática Discreta by admin No Comments

MAD: Grafos Eulerianos y Hamiltonianos

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$

Ejercicio: Estudiar si el grafo representado por la matriz [0,1,0,1,0,0; 1,0,1,0,0,0; 0,1,0,1,1,1; 1,0,1,0,1,1;0,0,1,1,0,0; 0,0,1,1,0,0] tiene un camino o ciclo eureliano y/o hamiltoniano.
Posted in: Matemática Discreta by admin No Comments

MAD: Matriz de adyacencia 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
Posted in: Matemática Discreta by admin No Comments

MAD: Teoría de Grafos

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

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:

Posted in: Matemática Discreta by admin No Comments

MAD: Desarreglos y particiones

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 B0 = 1, B1 = 1, B2 = 2, B3 = 5, B4 = 15, B5 = 52, B6 = 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).$$

Ejercicio: Calcular el número de desarreglos de $S_5$.
Posted in: Matemática Discreta by admin No Comments

MAD: Principio de inclusión-exclusión

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 A1, …, An 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}$$

Ejercicio: ¿Cuántos números del 1000 a 9999 hay que no sean múltiplos de 3 y/o de 5 y/o de 7?
Posted in: Matemática Discreta by admin No Comments

MAD: La fórmula de Leibniz

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

Ejercicio: Calcular el coeficiente de $x^3y^4z^2$ del desarrollo de $(x+y+3z)^9$
Posted in: Matemática Discreta by admin No Comments

MAD: Teorema del binomio

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

Ejercicio:Calcular cuanto suma para todo $n\in\mathbb{N}$ $${n\choose 0}-{n\choose 1}+{n\choose 2}-{n\choose 3}+\cdots+(-1)^{i+1}{n\choose i}+\cdots+(-1)^{n+1}{n\choose n}$$
Posted in: Matemática Discreta by admin No Comments

MAD: Número binomial

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.

TrianguloPascalC.svg
«TrianguloPascalC» por DriniTrabajo propio. Disponible bajo la licencia CC BY-SA 3.0 vía Wikimedia Commons.

Ejercicio:Probar que para todo $n\in\mathbb{N}$ es ${n\choose 0}+{n\choose 1}+{n\choose 2}+\cdots+{n\choose n}=2^n$
Posted in: Matemática Discreta by admin No Comments

MAD: Combinaciones

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

Ejercicio: ¿Cuántas soluciones enteras positivas admite la ecuación $x+y+z=7$.
Posted in: Matemática Discreta by admin No Comments