MA265 Sesión 11.1 Solucionario de Árboles dirigidos-Búsqueda

UPC – Departamento de Ciencias – MATEMATICA DISCRETA (MA265) Profesores MA265 1 Retículas y complemento Respuestas de los ejercicios propuestos 1. a) Sí es una retícula, todo par de vértices siempre tiene una MCS y un MCI b) No es una retícula, debido a que no existe 𝑀𝐶𝑆({𝑏, 𝑐}) c) No es una retícula, debido a que no existe 𝑀𝐶𝐼({𝑐, 𝑑}) 2. a) 𝐷 105 ; |) 𝑦 (𝐷 30 ; |) son retículas ya que cada par elementos tiene MCS y MCI. b) 3 ∨ 5 = 15 𝑀𝐶𝑆(30, 𝑀𝐶𝑆(5, 15)) = 30 c) 7 ∧ 15 = 1 𝑀𝐶𝐼(5, 𝑀𝐶𝐼(3,21)) = 1 3. a) Como se muestra en el diagrama vemos que sí es una retícula, ya que, si tomamos cualquier par de vértices, estos tienen MCI y MCS. (ver gráfica) b) La retícula si es acotada, pues tiene un máximo y un mínimo c) Sí es complementada, ya que cada elemento tiene por lo menos un complemento. UPC – Departamento de Ciencias – MATEMATICA DISCRETA (MA265) Profesores MA265 2 4. a) L es acotada ya que tiene un máximo y un mínimo b) L es complementada ya que cada elemento tiene al menos un complemento (ver tabla) c) 𝑑 ∧ ( 𝑓 ∨ 𝑒 ) = 𝑑 (𝑑 ∧ 𝑓 ) ∨ ( 𝑑 ∧ 𝑒 ) = 𝑎 d) L no es distributiva ya que: 𝑑 ∧ ( 𝑓 ∨ 𝑒 ) ≠ ( 𝑑 ∧ 𝑓 ) ∨ ( 𝑑 ∧ 𝑒 ) 5. a) Los complementos para cada elemento se muestran en la tabla b) 𝑏 ∨ (ℎ ∧ 𝑔) = 𝑎 (𝑏 ∨ ℎ) ∧ (𝑏 ∨ 𝑔) = 𝑑 c) 𝐿 no es distributiva debido a que: 𝑏 ∨ (ℎ ∧ 𝑔) ≠ (𝑏 ∨ ℎ) ∧ (𝑏 ∨ 𝑔) d) 𝐿 es acotada, ya que tiene un máximo y un mínimo. 6. a) Los complementos para cada elemento se muestran en la tabla b) 𝑏 ∨ (𝑖 ∧ 𝑐 ) = 𝑗 (𝑏 ∨ 𝑖 ) ∧ (𝑏 ∨ 𝑐 ) = 𝑗 c) 𝐿 no es distributiva debido a que algunos elementos tienen más de un complemento. d) 𝐿 es acotada, ya que tiene un máximo y un mínimo. 𝑥 𝑥′ 𝑎 ℎ 𝑏 𝑐 , 𝑑 , 𝑔 𝑐 𝑒 , 𝑓 𝑑 𝑏 , 𝑒 , 𝑓 𝑒 𝑐 , 𝑑 , 𝑔 𝑓 𝑐 , 𝑑 , 𝑔 𝑔 𝑒 , 𝑓 , 𝑏 ℎ 𝑎 𝑥 𝑥′ 𝑎 𝑒 𝑏 𝑒 , 𝑓 𝑐 𝑑 𝑑 𝑐 𝑒 𝑏 , ℎ , 𝑎 𝑓 ℎ , 𝑏 𝑔 𝑛𝑜 𝑒𝑥𝑖𝑠𝑡𝑒𝑛 ℎ 𝑒 , 𝑓 𝑥 𝑥′ 𝑎 𝑖 , 𝑐 , 𝑔 , 𝑓 𝑏 No tiene 𝑐 ℎ , 𝑎 , 𝑑 , 𝑒 𝑑 𝑖 , 𝑐 𝑒 𝑖 , 𝑐 𝑓 ℎ , 𝑎 𝑔 ℎ , 𝑎 ℎ 𝑖 , 𝑐 , 𝑔 , 𝑓 𝑖 ℎ , 𝑎 , 𝑑 , 𝑒 𝑗 𝑘 𝑘 𝑗 UPC – Departamento de Ciencias – MATEMATICA DISCRETA (MA265) Profesores MA265 3 7. a) Los complementos para cada elemento se muestran en la tabla b) 𝑐 ∨ (𝑖 ∧ 𝑓) = 𝑎 (𝑐 ∨ 𝑖 ) ∧ (𝑐 ∨ 𝑓 ) = 𝑎 c) 𝐿 no es distributiva debido a que f tiene más de un complemento. 𝑥 𝑥′ 𝑎 𝑒 𝑏 𝑓 𝑐 𝑓 𝑑 𝑔 𝑒 𝑎 𝑓 𝑐 , 𝑏 𝑔 𝑑 ℎ 𝑖 𝑖 ℎ