Metematicas discretas

RELACIONES

Sean los conjuntos A1,A2, . . . ,An. Una relación R sobre A1×A2×· · ·×An es cualquier subconjunto
de este producto cartesiano, es decir,
R _ A1 × A2 × · · · × An
Si R = ;, llamaremos a R, la relación vacía.
Si R = A1 × A2 × · · · × An, llamaremos a R la relación universal.
Si Ai = A, 8i = 1, 2, . . . , n, entonces R es una relación n-aria sobre A.
Si n = 2, diremos que R esuna relación binaria y si n = 3, una relación ternaria.
Relaciones Binarias

La clase más importante de relaciones es la de las relaciones binarias. Debido a que este tipo de relaciones
son las más frecuentes, el término “relación” denota generalmente una relación binaria; adoptaremos este
criterio cuando no haya confusión y especificaremos las que no sean binarias con términos tales como“ternaria” o “n-aria”.
Si (a, b) 2 R diremos que a esta relacionado con b y lo notaremos por aRb.
Si (a, b) /2 R, escribiremos aR/ b y diremos que a no está relacionado con b.
Representación de relaciones
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 matriz , donde

La matriz se denomina matriz de R. En otras palabras lamatriz, 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 yB.
Propiedades de las Relaciones

Las relaciones binarias, es decir definidas sobre un único conjunto A, satisfacen ciertas propiedades que
expondremos en este apartado.
Relaciones de equivalencia

Dada una relación binaria R definida sobre A, se dice que R es una relación de equivalencia en A si verifica las propiedades:
–reflexiva
–simétrica
–transitivafunciones
Inyectivo
Una función f es inyectiva si, cuando f(x) = f(y), x = y.
Nota: inyectiva también se llama "uno a uno", pero esto se confunde porque suena un poco como si fuera biyectiva.
Sobreyectivo (o también "epiyectivo")
Una función f (de un conjunto A a otro B) es sobreyectiva si para cada y en B, existe por lo menos un x en A que cumple f(x) = y, en otras palabras f essobreyectiva si y sólo si f(A) = B.
Así que cada elemento de la imagen corresponde con un elemento del dominio por lo menos.
Sin embargo, f(x) = 2x del conjunto de los números naturales a no es sobreyectiva, porque, por ejemplo, ningún elemento de va al 3 por esta función.
Biyectiva
Una función f (del conjunto A al B) es biyectiva si, para cada y en B, hay exactamente un x en A que cumple quef(x) = y
Alternativamente, f es biyectiva si es a la vez inyectiva y sobreyectiva.

TEORIA DE GRAFOS
En matemáticas y en ciencias de la computación, la teoría de grafos (también llamada teoría de las gráficas) estudia las propiedades de los grafos (también llamadas gráficas). Un grafo es un conjunto, no vacío, de objetos llamados vértices (o nodos) y una selección de pares de vértices,llamados aristas (edges en inglés) que pueden ser orientados o no. Típicamente, un grafo se representa mediante una serie de puntos (los vértices) conectados por líneas (las aristas).
ESTRUCTURA DE REPRESENTACION DE GRAFOS
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. Entrelas estructuras más sencillas y usadas se encuentran las listas y las matrices, aunque frecuentemente se usa una combinación de ambas. Las listas son preferidas en grafos dispersos porque tienen un eficiente uso de la memoria. Por otro lado, las matrices proveen acceso rápido, pero pueden consumir grandes cantidades de memoria.
ESTRUCTURA DE LISTAS
* lista de incidencia - Las aristas son...