ciencias

República Bolivariana de Venezuela
Ministerio del Poder Popular para la Defensa
Universidad Nacional Experimental Politécnica
de la Fuerza Armada Bolivariana de Venezuela
Cátedra: Teoría de Grafos







Relaciones Equivalentes





Facilitador: Integrantes:
Ing. Diomaris ContrerasNilson Gómez M.


Caracas, 04 de Abril del 2014

















Relaciones de Equivalencia

Las relaciones de equivalencia son un concepto matemático definido sobre un conjunto dado cualquiera. Como tantos otros conceptos matemáticos, está basado en una idea intuitiva, la representación de relaciones del tipo: ciudades en una misma región, alumnos de la mismaclase, instrucciones dentro del mismo bloque de código, enteros con el mismo valor de módulo P, etc.


Una relación de equivalencia sobre un conjunto C es una relación R que cumple las siguientes propiedades 7:

Reflexiva. ∀a ∈ C; a R a
Simétrica. ∀a, b ∈ C; a R b ⇔ b R a
Transitiva. ∀a, b, c ∈ C; (a R b) ∧ (b R c) ⇒ (a R c)

Es fácil comprobar estas propiedades para los ejemplosanteriores. Por ejemplo, la propiedad reflexiva significa que una ciudad está en la misma región que ella misma, obviamente; la simétrica diría que si la ciudad a está en la misma región que b, entonces b está en la misma región que a; y la transitiva, que si a está en misma región que b, y está en la misma que c, entonces a y c están en la misma región. Las tres se cumplen de manera trivial. En lafigura 4.7 se muestra un ejemplo particular de relación de equivalencia, definida sobre un conjunto de nueve elementos.

Las relaciones de equivalencia dan lugar al concepto de clase de equivalencia.

La clase de equivalencia de un elemento a, según una relación R sobre un conjunto C, es el subconjunto de todos los elementos c de C tales que c R a. Por ejemplo, en los casos anteriorestendríamos: la clase de las ciudades de la Región de Murcia, la clase de los alumnos de segundo curso, etc. El conjunto de todas las clases de equivalencia definidas sobre C según la relación R, forma una partición de ese conjunto, es decir, son un conjunto de subconjuntos disjuntos y la unión de todos ellos es el conjunto de partida C.

Nuestro interés, como programadores, es estudiar laimplementación eficiente de relaciones de equivalencia definidas sobre conjuntos finitos. Además, vamos a considerar especialmente relaciones que no pueden ser calculadas mediante una formula (como ocurre, por ejemplo, con la igualdad de enteros modulo P) y que pueden variar en tiempo de ejecución. En otro caso, la implementación seria inmediata. Pero, en primer lugar, vamos a definir un tipo abstracto dedatos para el uso de relaciones de equivalencia.

La expresión “a R b” se lee “a esta relacionado con b”.

Teorema.

Si  y s es un entero positivo, entonces  ,
La demostración de este teorema se deja como ejercicio.
Ejemplo: Demuestre que si p es primo impar, entonces  

Solución

Como p es impar, entonces, p - 1 es par, lo que quiere decir que existe un número par desumandos  Hay que notar que  , porque  Comparando el primero y el último sumando, se tiene.
Comparando el segundo y el penúltimo sumando se tiene  .
Si comparamos el tercero con el antepenúltimo sumando y así sucesivamente, se obtiene:

Cuando la secuencia se agota, al lado izquierdo de la relación de congruencia se tendrán los enteros  y al aplicar repetidamente el teorema 3.1.8. Se tendrá:  Ejemplo: Encuentre el residuo de la división de  entre 15.

Solución.

El problema equivale a encontrar cuál de las quince clases residuales módulo 15, que contienen a  respectivamente, contiene a  .

Más claramente, se trata de hallar un número a entre 0 y 14 tal que cumpla que  o lo que es lo mismo; encontrar un a que sea igual al residuo de dividir entre 15.
Hay que notar...