Relacioneshttp://www.youtube.com/watch?v=OvuuMB67uhU&feature=player_detailpage

RelacinRelacin Ra

b

c

1

2

3RLNDominio de RRango de R

EjemploRelacin R:Lima

Iquitos

Huacho

ArequipaLima

Iquitos

Huacho

ArequipaConexin va reaCiudades(C)Ciudades(C)

EjemploR={(L,H),(L,A),(H,L),(H,A),(A,L),(A,H)}

CxC={(L,L),(L,I),(L,H),(L,A), (I,L),(I,I),(I,H),(I,A), (H,L),(H,I),(H,H),(H,A), (A,L),(A,I),(A,H),(A,A)}

EjemploSea Una relacin R del conjunto A al conjunto B R AxB?

EjemploRelacin: Q=ToRProfesoresClasesAlumnosACP

RelacinUna relacin en un conjunto A

Propiedades de las relacionesSea R una relacin en el conjunto A

Reflexivo

Propiedades de las relacionesSea R una relacin en el conjunto A

Simtrico

Propiedades de las relacionesSea R una relacin en el conjunto A

Transitivo

Propiedades de las relacionesSea R una relacin en el conjunto A

Antisimtrico

Grafo:

Grafo:Un Grafo G es una terna (V,A,p):V (de vrtices) A (de arcos) p: A P2(V) (de incidencia)p(a) = {u, v}. (u, v son los extremos del arco a)

Dgrafos:Un Di-grafo D = (V,A,p) dnde p: A VVp(a) = (u, v) u es el extremo inicial u origen de a v es el extremo final o destino de ap(a) = (u, u) (a es un bucle)

Relaciones y dgrafos:

aRb si y solo si existe un arco que une a y b.

Matriz de una relacin:M :Matriz de orden n x n

Mik =1 si existe un arco de vi a vk

Mik =0 si no existe un arco de vi a vk

Tipos de relacionesEquivalenciaReflexiva TransitivaSimtrica

Clases de equivalencia:Sea R una relacin de equivalencia sobre A[a] = {x A: x R a}.

Conjunto cociente:Es el conjunto formado por todas las clases de equivalencia de una relacin o

Particin de un conjunto AUAi =AAi es disjunto a Ak, para todo i diferente k

TeoremaUna relacin de equivalencia en un conjunto A, particiona A.

Tipos de relacionesOrden ParcialReflexivaTransitiva Antisimtrica

Conjuntos Parcialmente ordenadosSea una relacin R en un conjunto A de Orden parcial.A con la relacin de Orden parcial se llama Conjunto parcialmente ordenado y se denota (A,R) o (A,

Totalmente ordenadosSea una relacin R en un conjunto A de Orden parcial.Sea (A,R) un conjunto parcialmente ordenado se llama totalmente ordenado si: x,y A se tiene xRy o yRx, R se llama de orden total

Diagrama de HasseSon diagramas para las relaciones de orden parcial:Se halla su dgrafo correspondienteSe borran los lazosSe eliminan las aristas que estn implicadas por la propiedad transitiva.

Elementos extremosSea (A,

Elementos extremosSea (A,

Elementos extremosTeoremaUn conjunto parcialmente ordenado tiene a lo mas un elemento mximo y a lo mas un elemento mnimo

Elementos extremosTeoremaUn conjunto parcialmente ordenado no vacio y finito tiene al menos un elemento maximal y un elemento minimal.

Supremos e InfimosSea (A, ) (A,R) y B un subconjunto de AUn elemento a A es una Cota Superior de B si x a x B.Un elemento a A es una Cota Inferior de B si a x x B.

Supremos e InfimosSupremo: Mnima cota superior

Infimo: Mxima cota inferior

*******************************