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)