RELACIONES

RELACIONES

Relación `R' : Es cualquier subconjunto de A×B que cumpla la definición de la relación en concreto.

Otra def.: Sean x"A,y"A y grafo(gráfica) R / R" A×A, decimos que xRy si (x,y)"R El nº de relaciones ó subconjuntos de A×B será Relaciónaria: Cualquier subconjunto del producto cartesiano de A1× A2×...×An (Una relación binaria sería una relación de A1×A2) Propiedades que puede cumplir una relación:

- Reflexiva: Si a Є a (a,a)
Relación con sigo mismo, se refleja

- Antireflexiva: Si a NoЭ a, NoЭ (a,a)

» La recta paralela es reflexiva, la perpendicular no.

- Simétrica: Si a,b Є A (a,b) => (b,a)
se debe dar para todos los elementos

-Antisimétrica: Para todo a,b Є A (a,b) NoЭ (b,a)

- Transitiva: Para a,b,c Є A (a,b) ^ (b,c) Э (a,c) 

» Una relación es de EQUIVALENCIA si al mismo tiempo es : Reflexiva, Simétrica y Transitiva.

» Una relación s de ORDEN PARCIAL si al mismo tiempo es: Reflexiva, Antisimétrica y Transitiva.

GRAFOS

GRAFOS

Un grafo es una pareja de conjuntos G = (V,A), donde V es el conjunto de vértices, y A es el conjunto de aristas, este último es un conjunto de pares de la forma (u,v) tal que , tal que. Para simplificar, notaremos la arista (a,b) como ab.

»Multigrafo: Cuando hay 2 o más aristas paralelas, o cuando 2 vertices estan relacionados más veces con sigo mismo.

»Dígrafo: Hay un punto de origen y uno de destino final, es decir: no pueden ser a,b = b,a.

-QUE ES UNA ARISTA:

Son las lineas con las que se unen los vertices de un grafo, los vertices a y b son los extremos.

»Arista Adyacente: 2 aristas son adyacentes si convergen en el mismo vertice.
»Arista Paralelas: Son dos aristas conjuntas si el vertice inicial y final son el mismo.
»Arista Ciclicos: Es la arista que parte de un vertice para entrar en el mismo.
»Cruce: Son 2 aristas que cruzan en un mismo punto.

-QUE ES UN VERTICE:

Los vértices son 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.

CAMINO

Un camino en un grafo es una sucesión finita en la que aparecen alternadamente vértices y aristas de dicho grafo.
»Longitud del Camino: Está dada por número de aristas, parecido al tamaño.

»CAMINO ABIERTO:
Diferente punto de partida al de llegada, Que no llega a su principio.

»CAMINO CERRADO:
Cuando su punto de llegada es el mismo de partida.

»CAMINO SIMPLE:
No tiene aristas repetidas pero si puede tener vértices repartidos

»CAMINO ELEMENTAL:
No puede repetir ni aristas ni vértices, tiene que ser abierto.
»Todo camino elemental es simple, pero no todo caminos simple es elelemntal.


-TIPOS DE GRAFOS

»GRAFO CIRCULO:
Camino simple y cerrado

»GRAFO CICLO:
Camino elemental y cerrado

»GRAFO CADENA:
Camino elemental y abierto

COMBINACIONES

COMBINACIONES DE m ELEMENTOS TOMADOS DE n EN n.

Se llaman combinaciones de m elementos tomados de n en n (m - n) a todas las agrupaciones posibles que pueden hacerse con los m elementos de forma que:
No entran todos los elementos.
No importa el orden.
No se repiten los elementos. 

Tambin podemos calcular las combinaciones mediante factoriales: 

Las combinaciones se denotan por


EJEMPLO:

En una clase de 35 alumnos se quiere elegir un comite formado por tres alumnos. Cuantos comites diferentes se pueden formar?
No entran todos los elementos.
No importa el orden: Juan, Ana.
No se repiten los elementos. 

EJERCICIOS:

1. Una persona est interesada en contar todos los posibles resultados en el juego de la LOTERA PRIMITIVA. Podras ayudarle? 

2. Siete amigos hacen cola para el cine. Al llegar solo quedan 4 entradas. De cuantas formas podran repartirse estas entradas para ver la pelcula ? 

3. En una clase de 30 alumnos se quiere elegir un grupo de 5 alumnos para participar en un concurso. De cuantas formas podra hacerse ?

Dados m elementos, a ₁, a ₂, a ₃,... a _m,se llama combinacion binaria, o de orden n, a los conjuntos formados por n elementos elegidos entre ellos, de modo que dos conjuntos cualesquiera difieran en algn elemento.


Formula : C _m,n = V _m,n : P _n

COMBINACIONES CON REPETICION DE m ELEMENTOS

Las combinaciones con repeticiÓn de m elementos tomados de n en n (m y n), son los distintos grupos formados por n elementos de manera que:
No entran todos los elementos.
No importa el orden.
Si se repiten los elementos. 

EJEMPLO:

En una bodega hay cinco tipos diferentes de botellas. De cuantas formas se pueden elegir cuatro botellas? 

No entran todos los elementos. Slo elije 4.. 

No importa el orden. Da igual que elija 2 botellas de anis y 2 de ron, que 2 de ron y 2 de anis. 

Si se repiten los elementos. Puede elegir mas de una botella del mismo tipo. 

EJERCICIOS:

1. De cuantas formas se pueden organizar las vocales tomando gropos de 3, pudindose repetir los elementos en un mismo grupo. 

2. Se tienen 3 libros: uno de aritmtica (A), uno de biologa(B) y otro de clculo(C), y se quiere ver de cuántas maneras se pueden ordenar en un estante.

Las combinaciones con repeticin de m elementos tomados de n en n (m e n), son los distintos grupos formados por n elementos de manera que:

No entran todos los elementos, No importa el orden, S se repiten los elementos. 

Formula : CR _m,n = C _(m+n-1),n

PERMUTACIONES

PERMUTACIONES SIMPLES

En esta pemutación se reduce el número de opciones en cada paso.

Si se hiciera una elección ente un grupo de bolas de billar tu primera elección tiene 16 posibilidades, y tu siguiente elección tiene 15 posibilidades, despues 14, 13, etc. Y el total de permutaciones sera:

16 15 14 13 ... = 20,922,789,888,000

Pero a lo mejor no quieres elegirlas todas, slo 3 de ellas, as que sera solamente:

16 15 14 = 3360

Es decir, hay 3,360 maneras diferentes de elegir 3 bolas de billar de entre 16.

Pero como lo escribimos matemáticamente? Respuesta:

La función factorial (simbolo: !) significa que se multiplican numeros descendentes.

Asi que si quieres elegir todas las bolas de billar las permutaciones serian:

16! = 20,922,789,888,000

Pero si solo quieres elegir 3, tienes que dejar de multiplicar despues de 14. Como lo escribimos? Hay un buen truco... dividimos entre 13!...

Lo ves? 16! / 13! = 16 15 14

Ejemplos:

Nuestro "ejemplo de elegir en orden 3 bolas de 16" sera:

16!	=	16!	=	20,922,789,888,000	= 3360
(16-3)!		13!		6,227,020,800

Notación

En lugar de escribir toda la formula, la gente usa otras notaciones como:

PERMUTACIONES CON REPETICION DE m ELEMENTOS.

Permutaciones con repetición de m elementos donde el primer elemento se repite a veces, el segundo b veces , el tercero c veces, ...(m = a + b + c + ... = n) son los distintos grupos que pueden formarse con esos m elementos de forma que : 

Si entran todos los elementos. 

Si importa el orden. 

Si se repiten los elementos. 

EJEMPLO:
Con las cifras 2, 2, 2, 3, 3, 3, 3, 4, 4; cuntos nmeros de nueve cifras se pueden formar?
m = 9   a = 3     b = 4     c = 2     a + b + c = 9
Si entran todos los elementos.
Si importa el orden.
Si se repiten los elementos. 

EJERCICIOS:

1. De cuantas formas pueden ordenarse en una estantera 5 libros de lomo blanco, 3 de lomo azul y 6 de lomo rojo? 

2. Cuantas palabras de 6 letras con o sin sentido se pueden formas con las letras de AMASAS ? 

3. En una carrera por equipos participan 4 españoles, 5 franceses y 3 marroques. Si lo unico que se conoce de cada corredor es su nacionalidad, de cuantas formas posibles podran terminar la carrera?

PR _n ^a,b,c,... son las permutaciones con repetición de un conjunto con n elementos, de los cuales uno de ellos se repite a veces, otro b veces....... con la condición de que a + b + c + ... = n


Formula : PR _n ^a,b,c,... = P _n : ( a ! b ! c ! ...)

VARIACIONES

VARIACIONES DE m ELEMENTOS TOMADOS DE n EN n


Se llama variaciones ordinarias de m elementos tomados de n en n (m ' n) a los distintos grupos formados por n elementos de forma que:
No entran todos los elementos.
Si importa el orden.
No se repiten los elementos.
FORMULA :

V _m,n = m.(m-1).(m-2)...(m-n+1)

Tambin podemos calcular las variaciones mediante factoriales: 

Las variaciones se denotan por 

EJEMPLO:

Cuantos números de tres cifras diferentes se puede formar con los dígitos: 1, 2, 3, 4, 5 ?
m = 5n = 3 m ' n
No entran todos los elementos. De 5 digitos entran solo 3.
Si importa el orden. Son nmeros distintos el 123, 231, 321.
No se repiten los elementos.
El enunciado nos pide que las cifras sean diferentes.

V _3,5 = 5.4.3 = 60

EJERCICIOS:

1. En una carrera de 100 metros participan 8 corredores. De cuántas formas diferentes se podran repartir las medallas de oro, plata y bronce?
2. Un entrenador de fútbol dispone en la plantilla de su equipo de 7 delanteros de la misma calidad y que pueden actuar indistintamente en los tres puestos de ataque del equipo. Cuántas delanteras distintas podra confeccionar?
3. De cuántas maneras diferentes se pueden repartir tres premios distintos entre Juan, Pedro, Mara Alicia y Pilar?
Son las ordenaciones sin repetición de m elementos de un conjunto tomadas de n en n
Formula : V _m,n = m.(m-1).(m-2)...(m-n+1)

Tópicos en la Matemática Discreta

Informática Teórica

La teoría de la informática incluye áreas de la matemática discreta relevante a la computación. Está altamente relacionada con teoría de grafos y lógica. Dentro de la teoría de la informática se encuentra la teoría de algoritmos para problemas matemáticos. La computabilidad estudia lo que puede ser computado y tiene lazos fuertes con la lógica, mientras que la complejidad estudia el tiempo que se demora en hacer computaciones. La teoría de autómatas y los lenguajes formales se relacionan de manera cercana con la computabilidad. Las redes de Petri y álgebra de procesos se usan para modelar sistemas computacionales, y métodos de la matemática discreta se usan para analizar circuitos VLSI. La geometría computacional aplica algoritmos a problemas geométricos, mientras que el análisis digital de imágenes los aplica a representaciones de imágenes. La teoría informática también incluye el estudio de tópicos de informática continua.

Teoría de la Información

La Teoría de la Información se ve involucrada en la cuantificación de la información. Cercanamente relacionado a esto es la teoría de codificación, que es usada para diseñar métodos de transmisión y almacenamiento de datos eficientes y confiables. La teoría de la información también incluye tópicos continuos tales como señales análogas, codificación análoga y cifrado análogo.

Lógica

La lógica es el estudio de los principios del razonamiento valido y la inferencia, como también de la consistencia, solidez y completitud. Por ejemplo, en la mayoría de los sistemas en la lógica, la ley de Peirce, (((P→Q)→P)→P) es un teorema. En lógica clásica, puede ser fácilmente verificado con una tabla de verdad. El estudio de las demostraciones matemáticas es particularmente importante en lógica y tiene aplicaciones en la demostración automática de teoremas y verificación formal de software.

Las formulas lógicas son estructuras discretas, como lo son las demostraciones, las cuales forman árboles finitos, o más generalmente, estructuras de grafos acíclicos (en cada paso de inferencia combinando una o más ramas de premisas para dar una sola conclusión). Las tablas de verdad de formulas lógicas usualmente forman un conjunto finito, generalmente restringido a dos valores: verdadero y falso, pero la lógica puede tener valores continuos, por ejemplo en la lógica difusa. Los conceptos como árboles de demostraciones o derivaciones infinitas también han sido estudiados, por ejemplo en la lógica proposicional infinitaria.

Teoría de conjuntos

La teoría de conjuntos es la rama de la matemática que estudia conjuntos matemáticos, los cuales son colecciones de objetos, tales como {azul, blanco, rojo} o el conjunto infinito de todos los números primos. Conjuntos parcialmente ordenados y conjuntos con otras relaciones tienen aplicación en muchas áreas.

En la matemática discreta, los conjuntos numerables (incluyendo conjuntos finitos) son el principal objeto de estudio. El inicio de la teoría de conjuntos generalmente se relaciona con el trabajo de Georg Cantor, haciendo distinción entre diferentes tipos de conjuntos infinitos, motivado por el estudio de las series trigonométricas. El desarrollo más profundo en la teoría de conjuntos infinitos está fuera del alcance de la matemática discreta. De hecho, el trabajo contemporáneo en teoría descriptiva de conjuntos hace uso extenso del uso de la matemática continua tradicional.

Combinatoria

La combinatoria es la rama de la matemática que estudia colecciones finitas de objetos que pueden ser combinados u ordenados. La combinatoria enumerativa se ocupa, en particular, del "recuento" de los objetos de dichas colecciones.

La combinatoria analítica se concentra en la enumeración de estructuras combinatorias utilizando herramientas de análisis complejo y teoría de probabilidad. En contraste con la combinatoria enumerativa, que usa fórmulas combinatorias explicitas y funciones generadoras para describir los resultados, la combinatoria analítica se enfoca en obtener fórmulas asintóticas.

La teoría de diseño es el estudio de diseños combinatorios, que son clases de subconjuntos con ciertas propiedades numéricas de intersección. La teoría de particiones estudia varios problemas asintóticos y de enumeración relacionados con particiones enteras, y está relacionada con series q, funciones especiales y polinomios ortogonales. Originalmente una parte de teoría numérica y análisis, la teoría de particiones es considerada una parte de combinatoria, o un área independiente.

Teoría de Grafos

La teoría de distribuciones discretas trata con eventos que ocurren en espacios de muestra numerables. Por ejemplo, conteos como el número de aves en una bandada solo pueden tener valores naturales {0, 1, 2,...}. Por otra parte, observaciones continuas como los pesos de estas aves se pueden representar mediante números reales, y típicamente serian modelados por una distribución de probabilidad continua, como por ejemplo, la distribución normal. Distribuciones continuas pueden ser utilizadas para aproximar discretas y viceversa. Para situaciones en las cuales los valores posibles son altamente restringidos en su variabilidad, como por ejemplo en dados o cartas, calcular las probabilidades simplemente necesita de combinatoria enumerativa.

Teoría de números

La teoría de números principalmente tiene que ver con las propiedades de los números en general y, particularmente, de los enteros. Tiene aplicaciones en la criptografía, criptoanálisis y criptología, particularmente en lo que refiere a números primos. Otros aspectos de la teoría de números incluye la teoría geométrica de números. En la teoría analítica de números, técnicas de matemática continua también son utilizadas.

Álgebra

Las estructuras algebraicas ocurren discreta y continuamente. Como ejemplos de álgebras discretas están: el álgebra booleana, utilizada en circuitos digitales y programación, álgebra relacional, utilizada en bases de datos; grupos, finitos y discretos, así como anillos y campos son importantes en la teoría de códigos

Geometría

La geometría discreta y combinatoria tratan las propiedades combinatorias de colecciones discretas de objetos geométricos. Un antiguo tópico en la geometría discreta es el recubrimiento del plano. La geometría computacional aplica algoritmos a problemas geométricos.