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… Seguir leyendo MAD: Mapas y coloración de grafos.
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… Seguir leyendo MAD: Grafos Eulerianos y Hamiltonianos
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… Seguir leyendo MAD: Matriz de adyacencia de un grafo
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… Seguir leyendo MAD: Teoría de Grafos
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… Seguir leyendo MAD: Desarreglos y particiones
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:… Seguir leyendo MAD: Principio de inclusión-exclusión
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 $$… Seguir leyendo MAD: La fórmula de Leibniz
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… Seguir leyendo MAD: Teorema del binomio
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… Seguir leyendo MAD: Número binomial
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… Seguir leyendo MAD: Combinaciones