3.2. Relaciones de equivalencia.
Una relación de equivalencia en un conjunto C es una relación R que satisface tres propiedades:
- Reflexiva: a R a, para todo a perteneciente a C.
- Simétrica: a R b si y sólo si b R a.
- Transitiva: Si (a R b) y (b R c) entonces a R c.
Ejemplos: relación de ciudades en el mismo país, relación de igualdad de enteros módulo N, relación de instrucciones en un mismo bloque.
La clase de equivalencia de un elemento a ? C, es el subconjunto de C que contiene todos los elementos relacionados con a. Las clases de equivalencia forman una partición de C (subconjuntos disjuntos y completos).
Definimos un TDA para las relaciones de equivalencia, sobre un conjunto C.
Operaciones válidas:
- Inicia (C): Crea una relación vacía, cada clase es de un sólo elemento.
- Encuentra (x, C): Devuelve la clase de equivalencia a la que pertenece x.
- Unión (c1, c2, C): Combina dos clases de equivalencia en una nueva. Es una unión de conjuntos disjuntos.