viernes, 28 de noviembre de 2014

5.1 Relaciones

Una relación es un conjunto de pares ordenados. Un par ordenado (también  llamada pareja ordenada) consta de dos elementos: (a, b) en donde el orden en que  aparece (primero a, después 
b) indica la relación: a Rb de a con b.



Una relación asocia un elemento de un conjunto A con un elemento de otro  conjunto B o con un elemento del mismo conjunto A.

5.1.1 Producto cartesiano

Considere dos conjuntos arbitrarios A y B. El conjunto de todas las parejas ordenadas (a, b) en donde a A  y b B se llama producto o producto cartesiano de A y B.

La definición de producto cartesiano puede extenderse fácilmente al caso de más de dos conjuntos.

Se llama producto cartesiano de dos conjuntos A y B y se representa  A x B, al conjunto de pares ordenados (a, b), tales que el primer elemento pertenece al primer conjunto y el segundo elemento al segundo conjunto. Es decir:


A x B = {(a, b) / a A, b B}

5.1.2 Relación binaria

La relación binaria definida en un conjunto A es un subconjunto del producto cartesiano A x A.

EJEMPLO:

Sea el conjunto  A = {x,  y,  z}. El grafo de la siguiente figura representa una relación binaria definida en A, puesto que los pares (x, z), (y, x) (y, y) constituyen un subconjunto de A x A.

Se dice que dos elementos a y b están relacionados, y se escribe a R  b, “a está relacionado con b mediante la relación binaria  R”,  cuando el par ordenado (a, b) pertenece al subconjunto del producto cartesiano que define la relación.
Si dos elementos a y b no están relacionados mediante R en algún sentido, escribiremos a R   b o b R  a o ambas cosas.

Relación Binaria

5.1.3 Representaciones de Relaciones

Representación De Relaciones Usando Matrices 

Un método para el estudio de las relaciones de manera algorítmica es utilizando matrices compuestas de ceros y unos.


 Sean A y B conjuntos finitos de la forma: 

Si R es una relación de A en B. La relación R puede ser representada por la matrizdonde:

La matriz MR se denomina matriz de R. En otras palabras la matriz, de ceros y unos, de R tiene un 1 en la posición  (i,j) cuando  ai está relacionado con bj y un 1 en está posición ai si  no está relacionado con bj.


Obsérvese en la definición anterior que los elementos de A y B han sido escritos en un orden particular pero arbitrario. Por lo tanto, la matriz que representa una relación.

Conjuntos

Un conjunto es una colección de objetos considerada como un objeto en sí. Los objetos de la colección pueden ser cualquier cosa: personas, números, colores, letras, figuras, etc. Cada uno de los objetos en la colección es un elemento o miembro del conjunto. Por ejemplo, el conjunto de los colores del arcoíris es:

AI = {Rojo, Naranja, Amarillo, Verde, Azul, Añil, Violeta}

Un conjunto suele definirse mediante una propiedad que todos sus elementos comparten. Por ejemplo, para los números naturales, si consideramos la propiedad de ser un número primo, el conjunto de los números primos es:

P = {2, 3, 5, 7, 11, 13, …}

Un conjunto queda definido únicamente por sus miembros y por nada más. En particular el orden en el que se representen estos es irrelevante. Además, cada elemento puede aparecer de manera idéntica una sola vez, esto es, no puede haber elementos totalmente idénticos repetidos. Por ejemplo:

S = {Lunes, Martes, Miércoles, Jueves, Viernes} = {Martes, Viernes, Jueves, Lunes, Miércoles}

AI = {Rojo, Naranja, Amarillo, Verde, Azul, Añil, Violeta} = {Rojo, Naranja, Amarillo, Verde, Azul, Añil, Violeta, Naranja}


Informalmente, un grafo es un conjunto de objetos llamados vértices o nodos unidos por enlaces llamados aristas o arcos, que permiten representar relaciones binaria entre elementos de un conjunto.

Típicamente, un grafo se representa gráficamente como un conjunto de puntos (vértices o nodos) unidos por líneas (aristas).

Un grafo G es un par ordenado G = (V,E), donde:

· V es un conjunto de vértices o nodos, y

· E es un conjunto de aristas o arcos, que relacionan estos nodos.

Normalmente V suele ser finito. Muchos resultados importantes sobre grafos no son aplicables para grafos infinitos.

Se llama orden del grafo G a su número de vértices, | V | .

El grado de un vértice o nodo V es igual al número de arcos E que se encuentran en él.

Un bucle es una arista que relaciona al mismo nodo; es decir, una arista donde el nodo inicial y el nodo final coinciden.

Diagrama de flechas

Hay otra manera de visualizar una relación y es a través de una representación gráfica, donde se destaquen los puntos en el plano que pertenecen a A y los puntos que pertenecen a B. Se trazan flechas que indican la relación que existe entre cada elemento del conjunto  A y su correspondiente en el conjunto B. A esta representación gráfica se le conoce como un diagrama de flechas.


5.2 Propiedades de las relaciones (reflexiva, irreflexiva, simétrica, asimétrica, anti simétrica, transitiva)

Relaciones Reflexivas e  Irreflexivas

Una relación R en un conjunto A es reflexiva si (a, a) £ R para todas las a £ A, esto es, si a R e para todas las a e A. Una relación R en un conjunto A es irreflexiva si a R a para toda a £ A.

Por consiguiente, R es reflexiva si cada elemento a e A está relacionado consigo mismo y es irreflexiva si ningún elemento está relacionado consigo mismo.

Ejemplo:
(a) Sea Δ = [(a, a)\ a £ A], de modo que A es la relación de igualdad en el conjunto A. Entonces A es reflexiva, ya que (a, a) £ Δ para todas las a e A.
(b) Sea R = {(a, b) e A x A | a + b}, R es la relación de desigualdad en el conjunto A. Entonces R es irreflexible, ya que (a, a) £ R para todas las x € A.

Relaciones Simétricas y Asimétrica

Una relación R en un conjunto A es simétrica si cuando a R b, entonces b R a. De esto se sigue que R no es simétrica se tiene a y b € A con a R b, pero b R a. Una relación R en un conjunto A es asimétrica si cuando a R b, entonces b Ra. De esto se sigue que R no es simétrica si se tiene a y b e A con ambos a R b y b R a.
Una relación R en un conjunto A es asimétrica si cuando a R b y b R a, entonces a = b. Otra forma de expresar esta definición es diciendo que R es anti simétrica si cuando a ≠ b, se tiene a R b o b R a. De esto se sigue que R no es anti simétrica si se tiene a y b en A. a ≠ b, y ambas a R b y b R a.

Ejemplo:
Sea A «= [a, b, c, d, e} y sea R la relación simétrica dada por

R = {(a, b), (b, a), (a, c), (c, a), (b, c), (c, b), (b, e), (e, b), (e, a), (a, e), (c,a), (a,c)}

Relaciones  Transitivas

Se dice que una relación R en un conjunto A es transitiva si cuando a R b y b R e, entonces a R c. Se sigue que R no es transitiva si y sólo si se puede encontrar elemento a, b y c en A tal que a R b y b R c, pero a R c.

Una relación R en un conjunto A es transitiva si y sólo si satisface las siguientes propiedades: Si existe una trayectoria de longitud mayor que 1 del vértice a al vértice b, hay una trayectoria de extensión 1 de a a b (esto es, a está relacionada con b). Establecido algebraicamente, R es transitiva si y sólo si Rn £ R para todas las n ≥ 1.

Es posible caracterizar la relación transitiva por su matriz MR = [mij] así:
si mij =1 y mjk = 1, entonces mik = 1

Para ver qué significa transitividad en términos del grafo dirigido de una relación, se traducirá esta definición a términos geométricos.

Si se examinan los vértices particulares a y c, las condiciones a R b y b R c ocurrirán si y sólo si existe una trayectoria de longitud 2 de a a c, esto es, si y sólo si a R2 c. Es posible replantear la definición de transitividad como sigue: Si a R2 c, entonces a R c, esto es, R2 £ R (como un subconjunto de A x A).


jueves, 27 de noviembre de 2014

5.3 Relaciones de equivalencia (cerraduras, clases de equivalencia, particiones)

Las relaciones de equivalencia son relaciones entre los elementos de un elemento cualquiera. Se caracterizan por abstraer el concepto de igualdad.

Su definición formal es la siguiente:
Sea “K” un conjunto dado no vacío y “R” una relación binaria definida sobre “K”
Se dice que “R” es una relación de equivalencia si cumple las siguientes propiedades:

Reflexividad: Todo elemento de “K” está relacionado consigo mismo. Es decir,

Simetría: Si un elemento de “K” está relacionado con otro, entonces ese otro elemento también se relaciona con el primero. Es decir

Transitividad: Si un elemento de “K” está relacionado con otro, y ese otro a su vez se relaciona con un tercero, entonces el primero estará relacionado también con este último. Es decir,

CLASES DE EQUIVALENCIA
La importancia de las relaciones consiste en que dividen a los elementos del conjunto en diferentes clases, llamadas clases de equivalencia, de tal suerte que cada elemento pertenece a una y sólo una clase.

Tomemos un conjunto cualquiera X y sean a y b  dos elementos en X (lo cual denotamos por  a,b Ç X). Si  a está relacionado con b  escribiremos  a-b. Una relación de equivalencia en X es una relación que satisface las propiedades antes mencionadas.

Sea x un conjunto con una relación de equivalencia  -. Tomemos un elemento a de nuestro conjunto  X, es decir  aÇX. La clase de equivalencia de  a, la cual denotaremos por  {a}, es el subconjunto de X formado por todos los elementos b de X que están relacionados con  a, es decir  b-a. En símbolos, esto se escribe así:

De todo elemento en {a}. (por ejemplo  a) decimos que es un representante de la clase  Las relaciones de equivalencia son relaciones entre los elementos de un elemento cualquiera. Se caracterizan por abstraer el concepto de igualdad.


Su definición formal es la siguiente:
Sea “K” un conjunto dado no vacío y “R” una relación binaria definida sobre “K”. 

Se dice que “R” es una relación de equivalencia si cumple las siguientes propiedades:
Reflexividad: Todo elemento de “K” está relacionado consigo mismo. Es decir, {a}.

PARTICIONES
La partición de un conjunto es tan simple como dividir el mismo en conjuntos más pequeños formados por elementos de él mismo, es decir, en subconjuntos. Aquí no se toma en cuenta el conjunto vacío.

5.4 Funciones (inyectiva, suprayectiva, biyectiva)

Sea f una relación de A en B. Entonces f es una función de A en B (denotado f : A ! B y se lee “f es una función de A en B”) si y sólo si:

a) Dom(f) = A
b) 8 x 2 A, 8 y; z 2 B [(x; y) 2 f ^ (x; z) 2 f] ! y = z.

En palabras, lo anterior dice que si f es una relación de A en B tal que para cada x 2 A existe exactamente un y 2 B tal que (x; y) 2 f, entonces f es una función.
La condición a) garantiza que para cada x 2 A existe al menos un tal “y” y la condición b) garantiza que hay a lo más uno. Así, tomados juntos, hay exactamente uno.
Si f es una función de A en B entonces la “propiedad funcional” de cada x 2 A relacionado a exactamente un y 2 B permite el uso de la notación funcional
                              y = f(x).
La mayoría de las funciones conocidas en cálculo son dadas por una fórmula. Sin embargo esto no es necesario y, en general en matemática, las funciones no están dadas por fórmulas.
Es de resaltar que el nombre de la función es f y que f(x) no es el nombre de la función sino un elemento de B. 

Si y = f(x) entonces decimos que y es la imagen de x y que x es una Pre-imagen de y.


Puedes entender una función como una manera de conectar elementos de un conjunto "A" a los de otro conjunto "B":
"Injectivo" significa que cada elemento de "B" tiene como mucho uno de "A" al que corresponde (pero esto no nos dice que todos los elementos de "B" tengan alguno en "A"). 

"Sobreyectivo" significa que cada elemento de "B" tiene por lo menos uno de "A" (a lo mejor más de uno).

"Biyectivo" significa inyectivo y sobreyectivo a la vez. Así que hay una correspondencia perfecta "uno a uno" entre los elementos de los dos conjuntos.

5.5 Aplicaciones de las relaciones y las funciones en la computación

Uno de los conceptos más importantes en Matemáticas es el de función, ya que se puede aplicar en numerosas situaciones de la vida cotidiana, y determinar las relaciones que existen entre magnitudes tanto en Matemáticas, Físicas, Economía, etc., y poder calcular el valor de una de ellas en función de otras de las que depende.

Teoría de Grafos


6.1 Elementos y características de los grafos

Un grafo, G, es un par ordenado de V y A, donde V es el conjunto de vértices o nodos del grafo y A es un conjunto de pares de vértices, a estos también se les llama arcos o ejes del grafo. Un vértice puede tener 0 o más aristas, pero toda arista debe unir exactamente a dos vértices. Los grafos representan conjuntos de objetos que no tienen restricción de relación entre ellos. Un grafo puede representar varias cosas de la realidad cotidiana, tales como mapas de carreteras, vías férreas, circuitos eléctricos, etc. La notación G = A (V, A) se utiliza comúnmente para identificar un grafo. Los grafos se constituyen principalmente de dos partes: las aristas, vértices y los caminos que pueda contener el mismo grafo.

6.1.1 Componentes de un grafo (vértices, aristas, lazos y valencia)

• Aristas: Son las líneas con las que se unen las aristas de un grafo y con la que se construyen también caminos. Si la arista carece de dirección se denota indistintamente {a, b} o {b, a}, siendo a y b los vértices que une. Si {a ,b} es una arista, a los vértices a y b se les llama sus extremos. 

• Aristas Adyacentes: Se dice que dos aristas son adyacentes si convergen en el mismo vértice. 

• Aristas Paralelas: Se dice que dos aristas son paralelas si vértice inicial y el final son el mismo. 

• Aristas Cíclicas: Arista que parte de un vértice para entrar en el mismo. 

• Cruce: Son dos aristas que cruzan en un punto. Vértices
Son los puntos o nodos con los que esta conformado un grafo. Llamaremos grado de un vértice al número de aristas de las que es extremo. Se dice que un vértice es `par' o `impar' según lo sea su grado. 

• Vértices Adyacentes: si tenemos un par de vértices de un grafo (U, V) y si tenemos un arista que los une, entonces U y V son vértices adyacentes y se dice que U es el vértice inicial y V el vértice adyacente. 

• Vértice Aislado: Es un vértice de grado cero. 

• Vértice Terminal: Es un vértice de grado 1. 

6.2 Representación de los grafos

• Matriz de adyacencia
Dado un grafo G = (V, E) con n vértices {v1, ..., vn} su matriz de adyacencia es la matriz de orden n×n, A(G)=(aij) donde aijes el número de aristas que unen los vértices vi y vj. La matriz de adyacencia de un grafo es simétrica. Si un vértice es aislado entonces la correspondiente fila (columna) esta compuesta sólo por ceros. Si el grafo es simple entonces la matriz de adyacencia contiene solo ceros y unos (matriz binaria) y la diagonal esta compuesta sólo por ceros.


• Matriz de incidencia 
Dado un grafo simple G = (V, E) con n=|V| vértices {v1, ..., vn} y m=|E| aristas {e1, ..., em}, su matriz de incidencia es la matriz de orden nxm, B(G)=(bij), donde bij=1 si vi es incidente con ej ybij=0 en caso contrario. La matriz de incidencia sólo contiene ceros y unos (matriz binaria). Como cada arista incide exactamente en dos vértices, cada columna tiene exactamente dos unos. El número de unos que aparece en cada fila es igual al grado del vértice correspondiente. Una fila compuesta sólo por ceros corresponde a un vértice aislado.

6.2.1 Matemática

En matemáticas y ciencias de la computación, la teoría de grafos, también llamada teoría de loas graficas estudia las propiedades de los grafos (también llamados graficas) Un grafo es un conjunto, no vacío, de objetos llamados vértices (o nodos) y una selección de partes de vértices llamados aristas.

6.2.2 Computacional

Existen diferentes formas de almacenar grafos en una computadora. La estructura de datos, usada depende de las características del grafo y el algoritmo usado para manipularlo. Entre las estructuras más sencillas y usadas se encuentran las listas y las matrices y aunque frecuentemente se usa una combinación de ambos.

6.3 Algoritmos de recorrido y búsqueda

Algoritmos de recorrido y busqueda


6.3.1 El camino más corto

En la Teoría de Grafos, uno de los problemas más conocido es el del camino más corto.
El problema consiste en encontrar un camino entre dos vértices (o nodos) de tal manera que la suma de los pesos de las aristas que lo constituyen es mínima.
Para nosotros, los vértices serán poblaciones y los pesos de las aristas el tiempo que empleamos en desplazarnos de un sitio a otro.
La empresa TRANS VELOX es experta en resolver este tipo de problemas, ya que Juan en su juventud, aquel encuentro en la playa con María la Matemática, dio mucho de sí y siempre atento, aprendió mucho de ella, durante los 15 días que pasó en Marbella.
Volviendo al ejemplo del paquete que tenían que enviar desde Sevilla hasta Cádiz, Juan transformó esa situación real en una situación matemática (a esto lo llamamos modelización), después lo resolvió matemáticamente y lo volvió a pasar al mundo real.

6.3.2 A lo ancho

El problema de los caminos más cortos es el problema que consiste en encontrar un camino entre dos vértices (o nodos) de tal manera que la suma de los pesos de las aristas que lo constituyen es mínima. Ahora bien, podemos emplear el algoritmo de Dijkstra para éstos casos, los pasos o procedimientos a seguir para éste algoritmo son los siguientes: Teniendo un grafo dirigido ponderado de N nodos no aislados, sea x el nodo inicial, un vector D de tamaño N guardará al final del algoritmo las distancias desde x al resto de los nodos.

1. Inicializar todas las distancias en D con un valor infinito relativo ya que son desconocidas al principio, exceptuando la de x que se debe colocar en 0 debido a que la distancia de x a x sería 0.
2. Sea a = x (tomamos a como nodo actual).
3. Recorremos todos los nodos adyacentes de a, excepto los nodos marcados, llamaremos a estos vi
4. Si la distancia desde x hasta va guardada en D es mayor que la distancia desde x hasta a, sumada a la distancia desde a hasta vi; esta se sustituye con la segunda nombrada.
5. Marcamos como completo el nodo a.

6. Tomamos como próximo nodo actual el de menor valor en D (puede hacerse almacenándolos valores en una cola de prioridad) y volvemos al paso 3 mientras existan nodos no marcados.

6.3.3 En profundidad

En la búsqueda en profundidad se avanza de vértice en vértice, marcando cada vértice visitado. La búsqueda siempre avanza hacia un vértice no marcado, internándose “profundamente” en el grafo sin repetir ningún vértice. Cuando se alcanza un vértice cuyos vecinos han sido marcados, se retrocede al anterior vértice visitado y se avanza desde éste.

6.4 Arboles

En teoría de grafos, un árbol es un grafo en el que cualesquiera dos vértices están conectados por exactamente un camino. Un árbol a veces recibe el nombre de árbol libre.

Definiciones 

Un árbol es un grafo simple unidireccional G que satisface alguna de las siguientes condiciones equivalentes: 

• G es conexo y no tiene ciclos . 
• G no tiene ciclos y, si se añade alguna arista se forma un ciclo. 
• G es conexo y si se le quita alguna arista deja de ser conexo. 
• G es conexo y el grafo completo de 3 vértices no es un menor de G. 
• Dos vértices cual quiera de G están conectados por un único camino simple. 

Si G tiene muchos vértices, n, entonces las definiciones anteriores son también equivalentes a cualquiera de las siguientes condiciones: 
• G es conexo y tiene n - 1 aristas. 
• G es conexo y sin ciclos. 

Cualesquiera 2 vértices están unidos por una única trayectoria


6.4.1 Componentes (raíz, hoja, padre, hijo, descendientes, ancestros)


Es una estructura jerárquica aplicada sobre una colección de elementos u objetos llamados nodos, de los cuales uno es conocido como raíz, además se crea una relación de parentesco entre los nodos dando lugar a términos como padre, hijo, hermano, antecesor, sucesor, ancestro, etc. Un árbol es una estructura que está compuesta por un dato y varios árboles. Dado un nodo cualquiera de la estructura, podemos considerarlo como una estructura independiente, es decir un nodo cualquiera puede ser considerado como la raíz de una árbol completo. En relación con otros nodos: 



Nodo Padre: Nodo que contiene un puntero al nodo actual. En un árbol un nodo solo puede tener un nodo padre.. X es padre de Y sí y solo sí el nodo X apunta a Y, también se dice que X es antecesor de Y. 

Nodo Hijo: Cualquiera de lo nodo apuntado por uno de lo nodo del árbol. Un nodo puede tener varios hijos. X es hijo de Y, sí y solo sí el nodo X es apuntado por Y. También se dice que X es descendiente directo de Y. 

Hermano: Dos nodos serán hermanos si son descendientes directos de un mismo nodo. En cuanto a la posición dentro del árbol,

Nodo Raíz: Es el único nodo del árbol que no tiene padre. Este es el nodo que usaremos para referirnos al árbol. 

Nodo Hoja: Nodo que no tiene hijos. Se llama hoja o terminal a aquellos nodos que no tienen ramificaciones (hijos). 

Nodo Interior: Es un nodo que no es raíz ni hoja. 

Orden: Es el número potencial de hijos que puede tener cada elemento de árbol. De este modo, diremos que un árbol en el que cada nodo puede apuntar a otros dos es de orden dos, si puede apuntar a tres será de orden tres, etc. Podríamos decir que nuestro árbol de ejemplo es de orden tres. 

Grado: El número de hijos que tiene el elemento con más hijos dentro del árbol. En el árbol del ejemplo, el grado es tres, ya que tanto A como D tienen tres hijos, y no existen elementos con más de tres hijos 

Nivel: Se define para cada elemento del árbol como la distancia a la raíz, medida en nodos. El nivel de la raíz es cero, el de sus hijos uno y así sucesivamente. En el ejemplo, el nodo D tiene nivel 1, el nodo G tiene nivel 2 y el nodo N nivel 3. 

Rama: Es el camino desde el nodo raíz a una hoja. 

Altura: La altura de un árbol se define como el nivel del nodo de mayor nivel. Como cada nodo de un árbol puede considerarse a su vez como la raíz de un árbol, también podemos hablar de altura de ramas, el máximo número de nodos que hay que recorrer para llegar de la raíz a una de las hojas. 

Peso: Es el número de nodos del árbol sin contar la raíz. 



6.4.2 Propiedades

Todo árbol es a su vez un grafo con sólo un conjunto numerable de vértices es además un grafo plano.

Todo grafo conexo G admite un árbol de expansión, que es un árbol que contiene cada vértice de G y cuyas aristas son aristas de G.


Dado n vértices etiquetados, hay n n−2 maneras diferentes de conectarlos para construir un grafo. El resultado se llama fórmula de Cayley. El número de árboles con n vértices de grado d1,d2,...,dn es:
que es un coeficiente multinomial.



Contar el número de árboles no etiquetados es un problema complicado. De hecho, no se conoce ninguna fórmula para el número de árboles t(n) con n vértices (debe entederse aquí el número de árboles diferentes salvo isomorfismo de grafos). Los primeros valores de t(n) son 1, 1, 1, 1, 2, 3, 6, 11, 23, 47, 106, 235, 551, 1301, 3159, ... (sucesión A000055 en OEIS). Otter (1948) probó que



Una fórmula más exacta para el comportamiento asintótico de t(n) implica que hay dos números α y β (α ≈ 3 y β ≈ 0.5) tales que: