Maneja relaciones y grafos en la resolución de problemas

Maneja relaciones y grafos en la resolución de problemas.

UNIDAD 3

PROPÓSITO

Obtiene relaciones, grafos y árboles con base en la aplicación de sus propiedades y ordenamientos para el tratamiento de datos, su organización, y el procesamiento de información, así como el apoyo en la resolución algorítmica de lenguajes de computación.

RESULTADO DE APRENDIZAJE

3.1 Representa relaciones y funciones mediante la correspondencia de sus elementos y propiedades.

Justificación

Todo surge como consecuencia de que debido a que las relaciones comparten muchas de sus propiedades, el alumno puede entonces comprobar que hay cierta correspondencia uno a uno entre los elementos de dos relaciones, siempre y cuando exista una función biyectiva involucrada.

Estudiamos estos conceptos tan generales porque nos ayudan para poder entender hechos comunes entre los cuales están las ordenes, relaciones de equivalencia

Introducción

Una relación es un conjunto de . Las relaciones son útiles por muchas razones, por ejemplo, todas las bases de datos relacionales utilizan relaciones para el almacenamiento y el acceso a cualquier tipo de datos.

Por ejemplo los métodos gráficos son particularmente útiles para visualizar cualquier tipo de relación. Aunque por otra parte en algunas ocasiones es frecuente que para realizar operaciones matemáticas que incluyan relaciones sea más conveniente el representarlas como matrices.

En muchos problemas referentes a objetos discretos, con frecuencia se da el caso de que existe algún tipo de relación entre los objetos. Un ejemplo sería, en un conjunto de programas de computadora podríamos decir que 2 programas están relacionados, si ambos utilizan algunos datos en común y si es el caso contrario es que no están relacionados.

Otro ejemplo, sería de entre un grupo de estudiantes 2 estudiantes están relacionados si las primeras letras de sus apellidos son los mismos , o puede ocurrir de forma contraria que esos 2 estudiantes estén relacionados porque las primeras letras de sus apellidos son diferentes , o no existe tal relación .

Por supuesto, las relaciones son conjuntos, y los métodos para representar los conjuntos pueden utilizarse también para representar relaciones.

Un tipo especial de relaciones son las relaciones binarias, las cuales son conjuntos de pares y aparecen en ambos contextos.

Existe cierto número de operaciones que afectan directamente a las relaciones. De particular importancia, es la composición de dos relaciones.

Ya tenemos conocimiento de que todos los conjuntos corresponden a propiedades en el sentido de que cada propiedad define a un conjunto y cada conjunto define a una propiedad.

Los predicados y las relaciones están conectadas de una manera muy similar. Todo conjunto de que satisface a un cierto predicado define una relación , y toda relación define el predicado " Pertenece a " .

Por ejemplo, el producto cartesiano se definía antes como el conjunto de todos los pares Por consiguiente, una relación es siempre un subconjunto de .

De hecho, es en sí mismo una relación que llamaremos Relación Universal; la cual contiene todos los pares posibles. La Relación Universal tiene una relación opuesta que llamaremos Relación Vacía; la cual no contiene ningún par. Todas las demás relaciones deben de estar entre estos dos casos extremos.

Podemos definir una relación y representarla en una tabla, la cual puede estar estrechamente relacionada con una matriz, donde para convertir una tabla en una matriz simplemente se eliminan los encabezamientos.

CONJUNTOS PARCIALMENTE ORDENADOS

DEFINICIÓN

Una relación R : S  S se denomina un orden parcial débil si es reflexiva, antisimétrica y transitiva. R se denomina un orden parcial estricto si no es reflexiva, antisimétrica y transitiva.

Los órdenes parciales, débiles y estrictos están íntimamente relacionados. De hecho, si R es un orden parcial estricto, su cierre reflexivo es un orden parcial débil. Por otra parte, si S es un orden parcial débil sobre cierto conjunto A y si es la relación de identidad sobre A, entonces es un orden parcial estricto.

EJEMPLO

La relación < es un orden parcial estricto : es no reflexiva, antisimétrica y transitiva. El cierre reflexivo de < es  , y esta relación es un orden parcial débil: es reflexiva, antisimétrica y transitiva. Por otra parte, se obtiene el orden parcial estricto < a partir del orden parcial débil  mediante la eliminación de todos los pares de la forma ( x,x ).

Todos los ordenes parciales estrictos son no cíclicos, esto es, es imposible encontrar una tal que por consiguiente , es imposible encontrar un camino que comience y finalice en x. La razón es que un camino de tamaño s = s' desde a establecería y para relaciones transitivas Por lo tanto en una relación transitiva, todo camino que comience y termine en el mismo punto x implica que xRx es verdadera, puesto que un orden parcial estricto es irreflexivo, esto es imposible.

Esto tiene una implicación importante para las llamadas funciones. Si xRy significa que la función x puede llamar a la función y, y se puede determinar que estas llamadas a funciones forman un orden parcial, entonces es imposible que las llamadas causen un bucle.

La noción de conjunto parcialmente ordenado es muy importante.

DEFINICION

Un conjunto A junto con un orden parcial R se denomina conjunto parcialmente ordenado o un . El copo (A,R) es el conjunto A junto con el orden parcial R.

Observe que R en la definición 6.1.3 es un orden parcial débil. El orden parcial fuerte asociado con (A,R) los denotaremos por , donde A continuación damos , un grupo de órdenes parciales importantes:

• El conjunto de los reales junto con  forma el conjunto parcialmente ordenado ( ,  ).

• El

...