matematicas discretas

Representación de relaciones (matrices, conjuntos, grafos, diagrama de flechas)
      
       Los ejemplos de relaciones que más se presentan en el área de la computación son aquellas que están definidas sobre conjuntos finitos. En esta sección se trataran dos formas de representar dichas relaciones y su uso para poder identificar las propiedades vistas en la sección anterior.
Representaciónde 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:   A = {a1, a2, a3, .....,am} y B {b1, b2, b3, ..., bm}

Si R es una relación de A en B. La relación R puede ser representada por la matriz MR = (rij) m x n , donde

       La matriz sedenomina matriz de R. En otras palabras la matriz, de ceros y unos, de R tiene un 1 en la posición cuando está relacionado con , y un 1 en está posición si no está relacionado con .

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 depende de los órdenes usados para A y B.Cuando A = B usamos el mismo orden para A y B.


Ejemplo:


Sean A = {1,c} y B = {e,a,1}


Consideremos la siguiente relacion de A en B:
                                                                                      R = { (1,e), (c,1), (1,1), (c,a) }
Entonces la matriz de R es

Representación de relaciones usando conjuntos.
      
      Un conjunto es una colección de objetosconsiderada 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 suselementos comparten. Por ejemplo, para los números naturales, si consideramos la propiedad de ser un número primo, el conjunto de los número 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}Los conjuntos pueden ser finitos o infinitos. El conjunto de los número naturales es infinito, pero elconjunto de los planetas en el sistema solar es finito (tiene ocho elementos). Además, con los conjuntos pueden combinarse mediante operaciones, de manera similar a las operaciones con números.

Los conjuntos son un concepto básico, en el sentido de que no es posible definirlos en términos de nociones más elementales, por lo que su estudio puede realizarse de manera informal, apelando a la intuición ya la lógica. Por otro lado, son el concepto fundamental de la matemática: mediante ellos puede formularse el resto de objetos matemáticos, como los números y las funciones, entre otros. Su estudio detallado requiere pues la introducción de axiomas y conduce a la teoría de conjunto.
Representación de relaciones usando grafos.
    
     Un grafo  es el principal objeto de estudio de la teoría degrafos.

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...