14.4: Ejercicios

1. Utilice las técnicas de este capítulo para encontrar una coincidencia máxima de\(V_1\) a\(V_2\) en la gráfica que se muestra en la Figura 14.11. Los vértices de la parte inferior son el conjunto\(V_1\), mientras que los vértices de la parte superior son el conjunto\(V_2\). Si no puedes encontrar una coincidencia que satura todos los vértices en\(V_1\), explica por qué.

Figura 14.11. ¿Hay alguna saturación coincidente\(V_1\)?

2. Utilice las técnicas de este capítulo para encontrar una coincidencia máxima de\(V_1\) a\(V_2\) en la gráfica que se muestra en la Figura 14.12. Los vértices de la parte inferior son el conjunto\(V_1\), mientras que los vértices de la parte superior son el conjunto\(V_2\). Si no puedes encontrar una coincidencia que satura todos los vértices en\(V_1\), explica por qué.

Figura 14.12. ¿Hay alguna saturación coincidente\(V_1\)?

3. Los alumnos se preparan para realizar los proyectos finales de un curso de combinatoria aplicada. Los cinco temas posibles para sus proyectos finales son algoritmos gráficos, posets, inducción, teoría de grafos y funciones generadoras. Hay cinco alumnos en la clase, y cada uno le ha dado a su profesor la lista de temas sobre los que están dispuestos a hacer su proyecto. A Alice le interesan los posets o gráficas. Bob estaría dispuesto a hacer su proyecto sobre algoritmos gráficos, posets o inducción. Carlos sólo considerará posets o gráficas. A Dave le gusta generar funciones e inducción. Yolanda quiere hacer su proyecto ya sea en gráficas o posets. Para evitar la colaboración no autorizada, el profesor no quiere que dos alumnos trabajen sobre el mismo tema. ¿Es posible asignar a cada alumno un tema de las listas anteriores para que no trabajen dos alumnos en el mismo proyecto? Si es así, encuentra tal asignación. Si no, busca una tarea que maximice el número de alumnos que tienen tareas de sus listas y explica por qué no puedes satisfacer todas las solicitudes de los estudiantes.

4. Siete colegios y universidades compiten para reclutar a seis futbolistas de secundaria para que jueguen para sus equipos universitarios. A cada escuela solo se le permite fichar a un jugador más, y a cada jugador solo se le permite comprometerse con una sola escuela. En la siguiente tabla se enumeran las siete instituciones y los alumnos que están tratando de reclutar, han sido admitidos, y también están interesados en jugar para esa escuela. (No tiene sentido asignar a una escuela a un jugador que no pueda cumplir con los requisitos académicos o que no quiera formar parte de ese equipo). Los jugadores son identificados por los enteros del 1 al 6. Encuentra una manera de asignar a los jugadores a las escuelas que maximice el número de escuelas que firmen a uno de los seis jugadores.

Figura 14.13. Esta red corresponde a un poset\(\textbf{P}\). Como es habitual, se supone que todas las capacidades son 1, y todos los bordes se dirigen hacia arriba. Responde las siguientes preguntas sobre\(\textbf{P}\) sin dibujar el diagrama del poset.

a. ¿Qué elemento (s) son mayores que\(x_1\) en\(\textbf{P}\)?

b. ¿Qué elemento (s) son menores que\(x_5\) en\(\textbf{P}\)?

c. ¿Con qué elemento (s) son comparables\(x_6\) en\(\textbf{P}\)?

d. Enumerar los elementos máximos de\(\textbf{P}\).

e. Enumerar los elementos mínimos de\(\textbf{P}\).

Figura 14.13. La red correspondiente a un poset

6. Dibuja el diagrama del poset que corresponde a la red en la Figura 14.13.

7. Utilice los métodos desarrollados en este capítulo para encontrar el ancho\(w\) del poset correspondiente a la red en la Figura 14.13. También encuentra una anticadena de tamaño\(w\) y una partición en\(w\) cadenas.

8. En la Figura 14.14 mostramos un poset\(\texbf{P}\) y una red utilizada para encontrar una partición en cadena de\(\textbf{P}\). (Todos los bordes de la red tienen una capacidad de 1 y están dirigidos de abajo hacia arriba. Los bordes en negrita actualmente llevan un flujo de 1.) Usando la red, encuentre el ancho\(w\) de\(\textbf{P}\), una partición de\(\textbf{P}\) en\(w\) cadenas y una anticadena con\(w\) elementos.

Figura 14.14. Un poset y el diagrama de red correspondiente

9. Dibuja la red correspondiente al poset\(\textbf{P}\) mostrado en la Figura 14.15. Utilice la red para encontrar el ancho\(w\) de\(\textbf{P}\), una partición en\(w\) cadenas y una anticadena de tamaño\(w\).

Figura 14.15. Un poset