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 conjunto de todos los subconjuntos de A junto con Ê forma el copo (ℙ A , ).

• Si x e y son cadenas y R es verdadera, si y es una subcadena de x y si A es el conjunto de todas las subcadenas de alguna cadena a, entonces (A,R) es un copo.

• Si x es una expresión, y si A es el conjunto de todas las subexpresiones de x, y si uRv es verdadera si u tiene a v como una subexpresión, entonces (A,R) es un copo.

Nombre del Alumno Ma. Del Carmen Melc hor Ventura Fecha 3101

Actividad (Trabajo Individual) Conjuntos parcialmente ordenados

Evaluación Excelente Suficiente Insuficiente

1.- ¿Cuáles son los conjuntos parcialmente ordenados?

2.- ¿Para que una relación sea un orden parcial con que condiciones debe cumplir?

3.- ¿Cuál es la terminología que utilizamos para denotar a los conjuntos parcialmente ordenados?

4.- ¿De que otra manera podemos llamar a un conjunto parcialmente ordenado ?

5.- ¿Cuándo denominamos a un orden parcial estricto?

Nombre del Alumno Ma. Del Carmen Melc hor Ventura Fecha 3101

Actividad (Trabajo Individual) Conjuntos parcialmente ordenados

Evaluación Excelente Suficiente Insuficiente

1.- ¿ Cuándo las funciones forman un orden parcial que es imposible que ocurra?

2.- ¿ Cuál sería una definición de un conjunto parcialmente ordenado ?

3.- ¿ Cuándo una relación es un orden parcial se dice que fue porque cumplió con las tres condiciones por lo tanto como lo podemos denominar ?

4.- ¿ Qué otro nombre reciben los conjuntos parcialmente ordenados ?

ORDENES ESPECIALES

Recordaremos que los conjuntos parcialmente ordenados surgen de diversas maneras , y en muchos casos el hecho de que haya pares de elementos incomparables es un hecho esencial del contexto .

La clase importante de estructuras de datos llamadas árboles , puede pensarse que está constituida por diagramas de Hasse , como los de la figura 1 , en los cuales existe para toda y toda pero existe sólo si o .

Los árboles son estructuras de datos útiles , aunque tengan elementos incomparables , ya que es posible empezar en lo alto y seguir el árbol para llegar a cualquier elemento rápida y fácilmente . También se conocen algoritmos eficientes para examinar todos los elementos de un árbol .

Una estructura de datos todavía más común consiste en una lista o sucesión en la cual , sin importar que dos elementos se tomen , uno viene antes del otro .

Esta estructura es un ejemplo de una cadena que definiremos como un copo en el cual siempre son comparables dos elementos .

Un orden parcial se llama orden total o lineal si para cada elección de k=m<n y en , o bien k=m<n ó k=m<n . De esta manera , una cadena es un copo con un orden total . Los términos de " conjunto totalmente ordenado" y " conjunto linealmente ordenado " se utilizan a veces como sinónimos de " cadena ".

EJEMPLO 1

a. El copo de la figura 1(b) es una cadena , los demás copos de la figura 1 no lo son .

b. El conjunto z = xv con el orden usual es una cadena .

c. Las listas de nombres en un directorio telefónico o de palabras en un diccionario son cadenas que definimos como ó aparece antes de

...