Relaciones estructuras discretas y grafos

REPÚBLICA BOLIVARIANA DE VENEZUELA MINISTERIO DEL PODER POPULAR PARA LA EDUC. SUPERIOR INSTITUTO UNIVERSITARIO POLITÉCNICO SANTIAGO MARIÑO

AMPLIACIÓN MARACAIBO INGENIERÍA DE SISTEMAS

[pic 1]

Estructura Discreta y Grafos

Integrantes: Br. Leobardo Fuenmayor

CI: 28.488.361

Investigar

Definición de relaciones: Las relaciones generalizan el concepto de funciones. La presencia del par ordenado (a, b) en una relación se interpreta como que existe una relación de a a b. El modelo de base de datos relacional que ayuda a los usuarios a tener acceso a la información de una base de datos (una colección de registros manejados por una computadora) se basa en el concepto de relación.

Propiedades de las relaciones:

Reflexiva e Irreflexiva

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.

Simétrica 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 qué 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 qué 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 qué 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.

Transitiva

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.

Clasificación de las relaciones:

Relación de Orden Parcial (Ejemplos).

Se dice que una relación        sobre un conjunto A es una relación de orden parcial si esta es reflexiva, anti simétrica o transitiva.[pic 2]

Si        es un orden parcial sobre A, se utiliza la notación a        b para indicar que (a, b)        [pic 3]. Esta notación sugiere que estamos interpretando la relación como orden sobre los elementos.[pic 4][pic 5][pic 6]

Sea A={a, b, c, d, e} y sea [pic 7] una relación sobre A definida como sigue:

[pic 8] = {(a, a), (a, b), (a, c), (a, d), (a, e), (b, b), (b, c), (b, e), (c, c), (c, e), (d, d), (d, e), (e, e)} Representada en la siguiente tabla:[pic 9]

Como [pic 10] es reflexiva, anti simétrica y transitiva por lo tanto es una relación de orden parcial.

Un conjunto A junto con un orden parcial [pic 11] sobre A, es llamado un conjunto parcialmente ordenado y se depota por (A, [pic 12] ). Un conjunto parcialmente ordenado es conocido como POSET (del inglés: partially ordered set).

Ejemplo:

Sea A el conjunto de        y sea [pic 13] una relación sobre A , tal que (a, b)        [pic 14] si a divide a b (con residuo igual a cero).[pic 15][pic 16]

Entonces como cualquier entero se divide a si mismo, [pic 17] es una relación reflexiva.

Si a divide a b significa que b no divide a a, a menos que sea a = b, por lo que [pic 18] es anti simétrica, y puesto que si a divide a b y b divide a c entonces a divide a c, por lo que [pic 19] es transitiva. en consecuencia [pic 20] es un orden parcial.

En realidad un conjunto parcialmente ordenado es denotado como (A,        ).[pic 21]

Relación de Equivalencia (Ejemplos).

Una relación binaria es una relación de equivalencia si y solo si es reflexiva, simétrica y transitiva.

En otras palabras, si RR es una relación de equivalencia, debe cumplir las siguientes propiedades:

Es reflexiva: ∀x∈A,(x,x)∈R∀x∈A,(x,x)∈R.

Es simétrica: (x,y)∈R→(y,x)∈R(x,y)∈R→(y,x)∈R

Es transitiva: [(x,y)∈R𝖠(y,z)∈R]→(x,z)∈R[(x,y)∈R𝖠(y,z)∈R]→(x,z)∈R.

Observe que las dos primeras no tiene el cuantificador “para todo” simbolizado por ∀∀, no es una obligación que deba cumplirse para todo los elementos de AA, excepto la primera, la relación reflexiva.

Por su reflexividad, implica que el dominio de RR es el mismo conjunto AA lo que implica que la relación de equivalencia tenga como dominio al conjunto AA.

...