Maneja relaciones y grafos en la resolución de problemas
Enviado por Stella • 30 de Octubre de 2018 • 9.867 Palabras (40 Páginas) • 411 Visitas
...
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
...