Maneja relaciones y grafos en la resolución de problemas

...

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

Todo subcopo de una cadena a su vez es una cadena . Por ejemplo los copos (w=xu, ) y (u, ) son subcopos de (z=xv, ) y están totalmente ordenados por el orden que heredan de z=xv . En el diccionario , las palabras que se encuentran entre las palabras "iniciar" e "interrumpir" forman una subcadena de todas las palabras del ejemplo 1( c ) .

Un copo que no es una cadena puede tener subcopos que sí lo sean . Con frecuencia es útil conocer los subcopos de un copo que son cadenas .

EJEMPLO 2

a) Sea el conjunto de todas las personas en una reunión familiar , escribamos si es descendiente de s = s’ . Entonces es un orden parcial estricto que define un orden parcial por s = s’ si y sólo si ó .

Una cadena en el copo es un conjunto de la forma en el cual es un descendiente de s = s’ ,s = s’ un descendiente de , etc. Sería muy poco usual que está cadena tuviera más de 5 elementos , en tanto que el conjunto podría ser muy grande .

b) El diagrama Hasse que se muestra en la figura 2 describe un copo que tiene bastantes cadenas [ 49 si contamos las cadenas de un elemento pero no la cadena vacía ] .

Con frecuencia nos interesamos por las cadenas maximales de un copo . Para definir esto observaremos que si es un copo si (S) es el conjunto de todas las cadenas en entonces es también un copo .

Una cadena maximal en es un elemento maximal de (S) , es decir , una cadena que no está contenida propiamente en ninguna otra .

EJEMPLO 3

a) En el copo de la figura 2 las cadenas maximales son

y Nótese que las cadenas maximales no son todas del mismo tamaño .

b) En el copo de la figura 3 las dos cadenas maximales que contienen a

y a , y tienen distinto número de elementos . Este copo tiene 4 cadenas maximales en total .

Una cadena finita debe tener elemento mínimo , lo mismo que cada una de sus subcadenas no vacías . Por otro lado las cadenas infinitas pueden tener distintos comportamientos . Las cadenas infinitas (w=xu, ) y (z = xv , ) con el orden usual no tienen elementos mínimos .

La cadena ({x z = xv : Q x }, ) tiene el mínimo elemento , a saber : el 0 , pero tiene subconjuntos como