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 […]

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 […]

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 […]

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: 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 […]

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 […]

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: […]

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 $$ […]

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 […]

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 […]

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 […]

Posted in: Matemática Discreta by admin No Comments