Principales Recursos y Disposiciones legales para el estudio de las Matematicas Discretas

Links y enlaces de aplicacion

Aqui les presentamos unos enlaces interesantes que nos pueden ayudar a comprender muchos temas a traves de la multimedia, para el estudio de las matematicas, y proporcionan una interaccion racional e interesante para sus diversas aplicaciones en el mundo moderno. Ademas de esto nos muestran otras areas diversas de las matematicas.


De esta forma queremos demostrar en el Blog Carlos Andres Sema y yo que las matematicas discretas tienen un campo de accion directo con la carrera que en este momento estamos ejerciendo, como lo es la Ingenieria de Sistemas.
Por esta razon, buscamos que este blog se extienda a mas personas, y seguirlo alimentando con mas informacion util, y certera que nos pueda ayudar a todos, y empezar de esta manera a interactuar con el conocimiento, dudas, ejercicios y demas que en algun momento puedan surgir a lo largo del nacimiento y consolidacion en un futuro proximo del blog matdiscretascun.

Una recomendacion especial que les hacemos, es por favor cualquier error, sugerencia y critica constructiva por favor nos la comunican por que de esto se va a tratar, lo de la interaccion que hablamos hace un momento.


Clases Didacticas con el profesor Moises Grillo

Video didactico de aplicacion del binomio de newton

Continuacion del video didactico del binomio de newton

Tercera Parte del Binomio de Newton Completo

Teoria de los grafos en Matematicas Discretas

La Teoria de los Grafos

En las matemaitcas actuales y en las ciencias de la computacion la teoria de los grafos o las graficas , estudia las propiedades de las mismas.

Un grafo es un conjunto, de objetos llamados vértices y una selección de pares de vértices, llamados aristas que pueden ser orientados o no. Típicamente, un grafo se representa mediante una serie de puntos conectados por líneas.

Definiciones

Vértice

Los vértices constituyen uno de los dos elementos que forman un grafo. Como ocurre con el resto de las ramas de las matemáticas, a la Teoría de Grafos no le interesa saber qué son los vértices.

Diferentes situaciones en las que pueden identificarse objetos y relaciones que satisfagan la definición de grafo pueden verse como grafos y así aplicar la Teoría de Grafos en ellos.

Grafo

Muchas redes de uso cotidiano pueden ser modeladas con un grafo: una red de carreteras que conecta ciudades, una red eléctrica o la red de drenaje de una ciudad.

Caracterización de grafos

Grafos simples

Un grafo es simple si sólo 1 arista une dos vértices cualesquiera. Esto es equivalente a decir que una arista cualquiera es la única que une dos vértices específicos. Un grafo que no es simple se denomina Multigráfica o Gráfo múltiple.

Grafos conexos

Un grafo es conexo si cada par de vértices está conectado por un camino; es decir, si para cualquier par de vértices (a, b), existe al menos un camino posible desde a hacia b. Un grafo es fuertemente conexo si cada par de vértices está conectado por al menos dos caminos disjuntos; es decir, es conexo y no existe un vértice tal que al sacarlo el grafo resultante sea disconexo.

Es posible determinar si un grafo es conexo usando un algoritmo Búsqueda en anchura (BFS) o Búsqueda en profundidad (DFS).

En términos matemáticos la propiedad de un grafo de ser (fuertemente) conexo permite establecer en base a él una relación de equivalencia para sus vértices, la cual lleva a una partición de éstos en "componentes (fuertemente) conexas", es decir, porciones del grafo, que son (fuertemente) conexas cuando se consideran como grafos aislados. Esta propiedad es importante para muchas demostraciones en teoría de grafos.

Las operaciones en los grafos

Árboles

Ejemplo de árbol.Un grafo que no tiene ciclos y que conecta a todos los puntos, se llama un árbol. En un grafo con n vértices, los árboles tienen exactamente n - 1 aristas, Su importancia radica en que los árboles son grafos que conectan todos los vértices utilizando el menor número posible de aristas. Un importante campo de aplicación de su estudio se encuentra en el análisis filogenético, el de la filiación de entidades que derivan unas de otras en un proceso evolutivo, que se aplica sobre todo a la averiguación del parentesco entre especies.

Teorema de los cuatro colores

En 1852 Francis Guthrie planteó el problema de los cuatro colores.Otro problema famoso relativo a los grafos: ¿Cuántos colores son necesarios para dibujar un mapa político, con la condición obvia que dos países adyacentes no puedan tener el mismo color? Se supone que los países son de un solo pedazo, y que el mundo es esférico o plano.

El mapa siguiente muestra que tres colores no bastan: Si se empieza por el país central a y se esfuerza uno en utilizar el menor número de colores, entonces en la corona alrededor de a alternan dos colores. Llegando al país h se tiene que introducir un cuarto color. Lo mismo sucede en i si se emplea el mismo método. La forma precisa de cada país no importa; lo único relevante es saber qué país toca a qué otro. Estos datos están incluidos en el grafo donde los vértices son los países y las aristas conectan los que justamente son adyacentes. Entonces la cuestión equivale a atribuir a cada vértice un color distinto del de sus vecinos.

Hemos visto que tres colores no son suficientes, y demostrar que con cinco siempre se llega, es bastante fácil. Pero el teorema de los cuatro colores no es nada obvio. 

 
 
 
 
 
 
 

Las Relaciones y sus propiedades

Las Relaciones en matematicas y sus propiedades especificas


El concepto de Relacion implica en matematicas la idea de correspondencia entre los elementos de dos conjuntos, que por consiguiente forman parejas ordenadas.

Se puede definir entonces la relación como la correspondencia que hay entre todos o algunos del primer conjunto con uno o mas del segundo conjunto.



Ejemplos de relación


A = {1, 4, 6}   B = {2, 3, 7}




TIPOS DE RELACION:






RELACION REFLEJA ( O REFLEXIVA )


R es una relación refleja en un conjunto A no vacío , si y sólo si cada elemento de él está relacionado consigo mismo expresado de estas dos formas:

a ð A ð a R a


Ejemplo:


A = { 1 , 2 , 3 }   R = { ( 1 , 1 ) , ( 1 , 3 ) , ( 2 , 2 ) , ( 3 , 2 ) , ( 3 , 3 ) }



RELACION SIMETRICA

R es una relación simétrica en un conjunto A no vacío , si y sólo si cada par de elementos de él satisface lo siguiente, expresada en cualquiera de estas dos formulas:

a R b ð b R a

Ejemplo:


A = { 1 , 2 , 3 }  R = { ( 1 , 3 ) , ( 2 , 3 ) , ( 3 , 1 ) , ( 3 , 2 ) , ( 3 , 3 ) }



RELACION ANTISIMETRICA

R es una relación antisimétrica en un conjunto A no vacío , si y sólo si cada par de elementos de él satisface lo siguiente:

a R b ð b R a ð a = b

Ejemplo:


A = { 1 , 2 , 3 }  R = { ( 1 , 3 ) , ( 2 , 1 ) , ( 2 , 2 ) , ( 3 , 2 ) }



RELACION TRANSITIVA

R es una relación transitiva en un conjunto A no vacío , si y sólo si cada trío de elementos de él satisface lo siguiente:

a R b ð b R c ð a R c

Ejemplo:

A = { 1 , 2 , 3 }  R = { ( 1 , 1 ) , ( 1 , 3 ) , ( 2 , 1 ) , ( 2 , 3 ) , ( 3 , 1 ) , ( 3 , 3 ) }



CLASIFICACION DE RELACIONES





RELACION DE EQUIVALENCIA

R es una relación de equivalencia en un conjunto A no vacío , si y sólo si es refleja, simétrica y transitiva en ese conjunto A .

Ejemplo:

La relación "igual que" ( = ) en el conjunto de los números enteros.

Sean a , b y c números enteros cualesquiera, entonces:

a = a ( Reflexividad )

a = b ð b = a ( Simetría )

a = b ð b = c ð a = c ( Transitividad )

RELACION DE ORDEN

R es una relación de orden en un conjunto A no vacío , si y sólo si es refleja, antisimétrica y transitiva en ese conjunto A .

Ejemplo:

La relación "menor o igual que" ( ð ) en el conjunto de los números enteros.


Sean a , b y c números enteros cualesquiera, entonces:


a ð a ( Reflexividad )

a ð b ð b ð a ð a = b ( Antisimetría )

a ð b ð b ð c ð a ð c ( Transitividad )

Teorema del Binomio de Isaac Newton

Teorema del Binomio de Newton

Formula creada y modificada por Isaac Newton a partir de la investigacion que realizo sobre el triangulo de Pascal, el`cual plantea la siguiente formula:

Usualmente el teorema del binomio se expresa en la siguiente variante:

 

donde recibe el nombre de coeficiente binomial y representa el número de formas de escoger k elementos a partir de un conjunto con n elementos.

 

Para calcular un Binomio de newton estilo n, k podemos utilizar de forma sencilla la siguiente formula:

 

 

Ejercicios de Aplicacion del binomio de Newton

Ejemplos:

1) Desarrollar la potencia (2x-3y)^15

Los Numeros Combinatorios y sus propiedades

Números combinatorios

Las agrupaciones combinatorias que sólo consideran la esencia de los grupos formados y no su orden, llamadas combinaciones, han constituido una rama específica dentro de la especialidad del análisis combinatorio, con múltiples usos en diversos campos. La expresión numérica de tales combinaciones recibe el nombre de número combinatorio o coeficiente binómico.

Coeficientes binómicos

Se define número combinatorio o coeficiente binómico como el valor numérico de las combinaciones ordinarias (sin repetición) de un conjunto de n elementos tomados en grupos de r, siendo n y r dos números enteros y positivos tales que n ³ r. Matemáticamente, un número combinatorio se expresa como:

Los números combinatorios se leen «n sobre r».

Propiedades de los números combinatorios

Entre las propiedades generales de los números combinatorios encontramos las siguientes que permiten un estudio mas detallado de lo mismo:

Cualquier número sobre 0 es igual a 1.

Todo número sobre sí mismo es igual a 1.

Un número sobre 1 es siempre igual al número.

Triángulo de Tartaglia

En el siglo XVI, el italiano Niccolò Tartaglia propuso un triángulo regular de números tales que:

Todas las filas del triángulo comienzan y terminan por la unidad, y son simétricas con respecto al valor central. Cada número del triángulo es igual a la suma de los dos situados encima de él.

La suma de todos los elementos de cada fila coincide con el valor 2n, siendo n el orden de la fila.

Esta disposición es de tipo combinatorio y se conoce como triángulo de Tartaglia o de Pascal.

Binomio de Newton

El uso de números combinatorios simplifica enormemente la expresión del llamado binomio de Newton, que desarrolla el valor de la potencia n-sima de un binomio:

Particularizando este binomio para el caso a = b = 1, se obtiene una explicación del hecho de que la suma de cada fila del triángulo de Tartaglia sea igual a 2n, ya que resulta:

El Principio de Inclusion y Exclusion

Es un elemental e importante principio de Combinatoria que puede ser usado para resolver una variedad de interesantes problemas. Este principio es conocido con varios nombres, los m´as comunes son: el principio del palomar, el principio de los cajones de Dirichlet.

Una forma simple del Principio de Inclusion y Exclusion dice:

Si n+1 objetos son colocados en n cajas, entonces al menos una caja contiene dos o mas objetos.

Ejemplo: Si en una habitacion hay 8 personas, entonces necesariamente existen dos de ellas que este año

celebran su cumpleaños el mismo dia de la semana. Las 8 personas las podemos modelar como el conjunto

P = {0, 1, . . . , 7} y los dias de la semana como el conjunto S = {0, 1, 2 . . . , 6}. El diıa de la semana que se celebra el cumplea˜nos de cada unas resulta ser una funci´on de P en S, por el principio de los cajones, esta funcion no puede ser inyectiva, luego al menos dos personas distintas celebraran su cumpleaños el mismo dia de la semana.

Este principio es sumamente intuitivo, sin embargo resulta de gran utilidad cuando se trabaja con conjuntos finitos, en el contexto de computacion cuando se trabaja por ejemplo con estructuras de datos como arreglos, tablas de hash, grafos, etc.

Tecnicas de Recuento en Combinatorias

Tecnicas de Recuento

Utilizadas normalmente en los procesos combinatorios, por ejemplo para desarrollar y determinar la complejidad de un algoritmo.

Para afirmar esto, tenemos que existen distintas formas de generar estas agrupaciones,segun sea el caso y se repitan los elementos de la poblacion o de la muestra, y en que por lo tanto influya o no el orden de puesta de los elementos.

Veamos todos los ejemplos y formas de la diferentes tecnicas de recuento utilizadas en Combinatoria, Variacion y Permutacion.

- Variaciones Sin repeticion

Sea A un conjunto de n elementos en la poblacion distintos y m muestra menor que n.

Se llamaràn variaciones ordinarias de m elementos de A a todas las posbiles agrupaciones ordenadas que podamos hacer de estos elementos m. Viene dado por la siguiente formula:

Vn,m= n (n-1) (n-2) (n-m+1)

Para el ejemplo:

1. ¿Cuantos numeros de tres cifras distintas se pueden formar con los numeros 1,2,3,4,5,6?

Entonces utilizamos:

V6,3 = 6! / (6-3)! = 6! / 3! = 6*5*4= 120 numeros distintos de tres cifras.

2. En la final de unas olimpiadas corren la final de 100 m 8 atletas. ¿De cuantas formas se puede configurar el podium?

Entonces utilizamos:

V8,3 = 8! / (8-3)! = 8! / 5! = 8*7*6 = 336 posibles podiums se pueden armar.

- Permutaciones sin repeticion

Sea el conjunto A con m elementos distintos. llamandose permutaciones sin repeticion de m elementos del conjunto A al numero de agrupaciones posibles que se pueden hacer con cada uno de los elementos.

Viene dada la situacion por la siguiente formula:

Pn= n (n-1) (n-2) 3*2*1

Para el ejemplo:

1. De cuantas formas posibles se pueden sentar 5 personas en un coche?

Entonces utilizamos:

P5 = 5*4*3*2*1=120 formas posibles de sentar 5 personas en un coche.

En un caso particular en el que por ejemplo la ordenacion no tiene comienzo ni fin es decir que los elementos estan dispuestos en forma circular. Una de las opciones viables es fijar uno de los elementos del conjunto y permutar los demas.

En la formula:

P*, n = (n-1)!

Un ejemplo sencillo de entender:

1. ¿De cuantas formas distintas se pueden sentar seis personas en una mesa circular?

Fijariamos entonces a una de las personas en la mesa y a las demas las ubicariamos.

P*,6 = 5! = 120

- Las permutaciones con repeticion

Se le llaman comunmente a la repeticion de los elementos n a las posibles agrupaciones que hagamos, teniendo en cuenta que dos elementos de un mismo grupo son indistinguibles, y viene dado por la formula:

n! / a! b! c!

Para el ejemplo:

1. En una urna hay 9 bolas, 3 blancas, 2 rojas y 4 negras. ¿De cuantas formas distintas se pueden extraer las bolas de la urna? Estas son las posibles ordenaciones.

Pn= 9! / 3! 2! 4! = 1260 posibles formas de extraer las bolas de la urna.

2. En una competicion deportiva participan 4 equipos de 3 atletas cada uno. ¿De cuantas formas diferentes pueden llegar los equipos?

Entonces aplicamos:

12 ! / 3! 3! 3! 3! = 369600. formas diferentes de que puedan cruzar la meta cualquiera de los equipos.

Las combinaciones

Sea A un conjunto con n elementos y m elementos naturales menores o iguales que n. Se le llama combinacion de m elementos de A a todo subconjunto de m de los contenidos en los elementos del conjunto A. Lo que nos interesa en la combinatoria es la naturaleza de los elementos y no el orden de colocacion.

Viene dado por la formula:

m! / (m-n) !n! y n siempre debe ser mayor o igual que m.

Para el ejemplo uno que tenemos acà muy curioso:

El juego de la primitiva consiste en acertar 6 numeros naturales a elegir entre el 1 y el 49.

¿cuantas combinaciones posibles hay? Si cada combinacion posible nos cuesta 1 euro.

¿cuanto nos tendremos que gastar para asegurar que vamos a acertar seguro los 6 numeros?

Queremos acertar 6 numeros de 49 posibles, independientemente del orden en que los elijamos.

Entonces observamos acà:

49! / 6! 4! 3! = 13983816, lo que tendriamos que apostar en euros para que salieran los 6 numeros posibles.

Las combinaciones con repeticion:

Sea el conjunto A con n elementos y m un natural menor o igual que n.

La llamamos combinacion con repeticion de m elementos de A a todo subconjunto de m elementos en el que un elemento puede aparecer m cantidad de veces. En este caso nos importa la naturaleza de cada elementos mas no el orden. Viene dado por la siguiente formula.

Cn,m = (n+m)! / m! (n-1)!

Para el ejemplo:

¿Cuantas fichas tiene el juego del dominò?

Una ficha de domino es un rectangulo en el que hay dos partes, en cada una de ellas hay una serie de puntos que indican la puntuacion de esa parte.

Seria entonces mirar, aunque muchos hemos jugado dominò y ya lo sabemos, ver como sale el resultado trivial.

C 1,2 = 8! / 2! 6! = 28

Teoria de las combinatorias

Teoria de las Combinatorias

Hace referencia a la solucion de problemas, que aparecen al cuantificar y estudiar los diferentes tipos de agrupaciones colecciones, o variaciones que se pueden dar en los diferentes conjuntos. Miremos entonces las mas importante conocidas dentro del estudio de las matematicas discretas.

Variaciones: En las cuales puede haber tanto repeticion de elementos como no elementos , en la cual si importa el orden por que hay una jerarquia establecida. Por lo tanto los elementos de la muestra deben ser menores que los elementos disponibles. (n<m) en la formula:

V=m!/(m-n!)

Permutaciones: De igual manera los elementos se pueden repetir o no hacerlo, tambien es importante el orden para con los elementos, dichos elementos de la muestra pueden ser iguales a los elementos disponibles. (n=m) en la formula:

Pn= n! y Pn,a,b,c= n! / a! b! c!

Combinaciones: Puede haber repeticion y no repeticion de elementos, no es necesario el orden para llegar a un mismo resultado, y los elementos de la muestra pueden ser menores o iguales a los elementos totales de la poblacion. (n<=m). en la formula:

Cn,m= m! /n! * (m-n)!

Crn,m= (m+n-1)! / n!(m-1)!

Algunos ejemplos comunes de aplicacion:

1. Variacion

¿Cuantos numeros de tres cifras se pueden formar con las nueve cifras significativas del sistema decimal?

Rta/ Primeramente se trata de numeros, y su orden es jerarquico, es decir que el orden importa y que se pueden repetir, por tanto esta es la formula:

V= 9 ^ 3= 729

2. Permutacion

¿Con las letras de la palabra DISCO ¿cuantas palabras distintas se pueden formar?

Rta/ Vuelve y juega por que el orden importa, esto nos muestra que n=m, es decir formar palabras de cinco letras con cinco elementos por tanto esta es la forma mas optima para resolver elejercicio:

P5= 5!= 5*4*3*2*1=120 palabras con la letra DISCO.

3. Combinacion

¿Cuantos grupos de cinco alumnos pueden formarse con los treinta alumnos de una clase. (Un grupo es distinto de otro si se difrencia de otro por lo menos en un alumno)?

Rta/ Son grupos de alumnos no importa el orden, esta es la solucion:

C5,30 = 30! /5!*(30-5)! = 30*29*28*27*26*25 / 5! * 25! = 142506.

Por tanto podemos formar 142506 grupos distintos de alumnos.

Notas aclaratorias al momento de resolver estos problemas:

- Si en cada agrupacion posible figuran solo algunos de los elementos de la poblacion, y nos muestran una jerarquia, entonces es un problema de Variacion.

- Si en cada agrupacion posible figuran todos los elementos de la poblacion, importando el orden se tratara de un problema de Permutacion.

- Si en cada agrupacion posible figuran solo algunos de los elementos poblacionales sin importar el orden entonces nos mostraran un problema de Combinaciones.

El origen de las matematicas discretas

Las matematicas discretas son una rama de las matematicas que nos muestran las tecnicas de conteo posibles, utilizando valores enteros, lamados comunmente discretos, en palabras sencillas elementos finitos numerables.

Esta necesidad en parte de obtener de las matematicas un estudio exacto probatorio y combinatorio se dio a partir de la segunda guerra mundial, por la urgencia de las tropas militares estadunidenses de burlar los codigos de las tropas alemanas, lo cual dio avances en lo que se empezò a conocer como criptografia y la ciencia computacional teorica.Lo que finalmente dio surgimiento a ramas añadidas a las matematicas discretas como lo fue la investigacion de operaciones.

Algunas notas importantes de la matematica discreta:

1. La matematica discreta es la contraria al calculo, no estudia el cambio continuo, incluyendo las tecnicas de la combinatoria.

2. La combinatoria es el arte de contar, todo lo que sea finito y entero que se puede contar hace parte del estudio de las matematicas discretas.

3. Es considerada la parte mas cercana al estudio de la ingenieria de sistemas, debemos recordar que los procesos en los computadores en su mayoria son progresivos y discretos, por lo que su relacion es bidireccional.