6.10: Ejercicios
- Page ID
- 118408
1. Decimos que una relación\(R\) sobre un conjunto\(X\) es simétrica si\((x,y) \in R\) implica\((y,x) \in R\) para todos\(x,y \in X\). Si\(X=\{a,b,c,d,e,f\}\), ¿en cuántas relaciones simétricas hay\(X\)? ¿Cuántos de estos son reflexivos?
2. Una relación\(R\) sobre un conjunto\(X\) es una relación de equivalencia si\(R\) es reflexiva, simétrica y transitiva. Arreglar un entero\(m \geq 2\). Mostrar que la relación definida en el conjunto\(\mathbb{Z}\) de enteros por\(aRb (a,b \in \mathbb{Z})\) si y sólo si\(a≡b(mod m)\) es una relación de equivalencia. (Recordemos que\(a≡b(mod m\)) significa que al dividir\(a\) por\(m\) y\(b\) por\(m\) usted obtiene el mismo resto.)
\(P=\{(1,1),(2,2),(3,3),(4,4),(1,3),(2,4),(2,5),(4,5),(3,5),(1,5)\}\)
una orden parcial en el set\(X=\{1,2,3,4,5\}\)? Si es así, discuta qué propiedades verificó y cómo. Si no, enumere los pares ordenados a los que se deben agregar\(P\) para que sea un pedido parcial o diga por qué no se puede hacer un pedido parcial agregando pares ordenados.
4. Dibuja el diagrama del poset\(\textbf{P}=(X,P)\) donde\(X=\{1,2,3,5,6,10,15,30\}\) y\(x \leq y\) en\(P\) si y solo si\(x|y\). (Recordemos que\(x|y\) significa que divide\(x\) uniformemente\(y\) sin resto. Equivalentemente\(x|y\), si y solo si\(y≡0\) (mod\(x\)).)
5. Dibuja el diagrama del poset\(\textbf{P}=(X,P)\) donde
\(X=\{\{1,3,4,5,6\},\{1,2,4,5,6\},\{1,2,3,6\},\{1,2,3\},\{1,5,6\},\{1,3,6\},\{1,2\},\{1,6\},\{3,5\},\{1\},\{3\},\{4\}\}\)
y\(P\) es el orden parcial\(X\) dado por la relación “es un subconjunto de”.
6. Una extensión lineal de un poset\(\textbf{P}=(X,P)\) es un orden total\(L\) en\(X\) tal que si\(x \leq y\) en\(P\), entonces\(x \leq y\) en\(L\). Dar extensión lineal de los tres posets mostrados en la Figura 6.8. Si te sientes muy ambicioso, trata de contar el número de extensiones lineales del poset en el lado izquierdo de la figura. No los enumere. Simplemente proporcione un entero como su respuesta.
7. Alice y Bob están considerando posets\(\textbf{P}\) y\(\textbf{Q}\). Pronto se dan cuenta de que\(\textbf{Q}\) es isomórfico para\(\textbf{P}^d\). Después de 10 minutos de trabajo, descubren que\(\textbf{P}\) tiene altura 5 y ancho 3. Bob no quiere hacer encontrar la altura y el ancho de\(\textbf{Q}\), ya que calcula que tomará (al menos) otros 10 minutos responder a estas preguntas para\(\textbf{Q}\). Alice dice que Bob está loco y que ya sabe la altura y anchura de\(\textbf{Q}\). ¿Quién tiene razón y por qué?
8. Para este ejercicio, considere el poset\(\textbf{P}\) en la Figura 6.5.
a. Enumerar los elementos máximos de\(\textbf{P}\).
b. Enumerar los elementos mínimos de\(\textbf{P}\).
c. Encontrar una cadena máxima con dos puntos en\(\textbf{P}\).
d. Encontrar una cadena\(\textbf{P}\) con tres puntos que no sea máxima. Di por qué tu cadena no es máxima.
e. Encontrar una anticadena máxima con cuatro puntos en\(\textbf{P}\).
9. Encuentra la altura\(h\) del poset que\(\textbf{P}=(X,P)\) se muestra a continuación así como una cadena máxima y una partición de\(X\) en\(h\) anticadena usando el algoritmo de este capítulo.
11. Un chef de restaurante ha diseñado un nuevo conjunto de platillos para su menú. Su conjunto de platillos contiene 10 platos principales, y seleccionará un subconjunto de ellos para colocar en el menú cada noche. Para asegurar variedad de platos principales para sus mecenas, quiere garantizar que un menú nocturno no esté completamente contenido ni contenga completamente el menú de otra noche. ¿Cuál es el mayor número de menús que puede planear utilizando sus 10 platos principales sujetos a este requisito?
12. Dibuja el diagrama del orden de intervalos representado en la Figura 6.34.
13. Dibuja el diagrama del orden de intervalos representado en la Figura 6.35.
14. Encuentre una representación de intervalo para el poset en la Figura 6.36 o dé una razón por la que no existe una.
15. Encuentre una representación de intervalo para el poset en la Figura 6.37 o dé una razón por la que no existe una.
16. Encuentre una representación de intervalo para el poset en la Figura 6.38 o dé una razón por la que no existe una.
17. Encuentre una representación de intervalo para el poset en la Figura 6.39 o dé una razón por la que no existe una.
18. Utilice el algoritmo First Fit (ordenando por puntos finales izquierdos) para encontrar el ancho\(w\) del orden de intervalo que se muestra en la Figura 6.40 y una partición en\(w\) cadenas. También da una anticadena con\(w\) puntos.
19. Completar la prueba del Teorema 6.30.
- Pista
-
La idea clave es mostrar que si\(d\) es el número entero menos positivo para el cual un orden de intervalo\(\textbf{P}\) tiene una representación usando puntos finales de\(\{1,2,…,n\}\), entonces cada entero\(i\) de este conjunto debe ser tanto un punto final izquierdo como un punto final derecho de un intervalo.
20. Mostrar que cada poset es isomórfico a un poset de cada uno de los cuatro tipos ilustrados en el Ejemplo 6.7.
- Pista
-
Para cada elemento\(x\), elija alguna clave de identificación única que sea un elemento/primario/coordinado/observador. Después se asocia con\(x\) una estructura que identifique las claves de los elementos de\(D[x]\).
21. La dimensión de un poset\(\textbf{P}=(X,P)\), denotada dim (\(\textbf{P}\)), es la menor\(t\) para la cual\(P\) es la intersección de órdenes\(t\) lineales en\(X\).
a. mostrar que la dimensión de un poset\(\textbf{P}\) es la misma que la dimensión de su doble.
b. Mostrar que\(\textbf{P}\) es un citatorio de\(\textbf{Q}\), luego dim (\(\textbf{P}\)) ≤dim (\(\textbf{Q}\)).
c. Demostrar que la eliminación de un punto puede reducir la dimensión como máximo en 1.
d. Encuentra la dimensión de los posets en la Figura 6.8.
e. Usar el teorema de Dilworth para mostrar que la dimensión de un poset es como mucho su ancho.
f. use el ejemplo del lado izquierdo de la Figura 6.33 para mostrar que para cada uno\(n \geq 2\), existe un poset\(\textbf{P}_n\) en\(2n\) puntos que tienen anchura y dimensión iguales a\(n\).