2. Encuentre el flujo correspondiente al acoplamiento de la figura 10.4.2. Demuestre que este flujo es máximo exhibiendo un corte mínimo con capacidad 3.
Los ejercicios 3 al 7 se refieren a la figura 10.4.1, donde se invierte la dirección de las aristas de manera que estén dirigidas de los puestos a los candidatos.
3. ¿Qué representa un acoplamiento?
4. ¿Qué representa un acoplamiento máximo?
5. Muestre un acoplamiento máximo.
6. ¿Qué representa un acoplamiento completo?
7. ¿Existe un acoplamiento completo? Si la hay, muestre una. Si no hay un acoplamiento completo, explique por qué.
8. El candidato A está calificado para los trabajos J1 y J4; B está calificado para los puestos J2, J3 y J6; Cestá calificado para los puestos J1, J3, J5 y J6; D puede estar en los puestos J1, J3 y J4; y E está calificado para los puestos J1, J3 y J6. a) Modele esta situación como una red de acoplamiento. b) Use el algoritmo 10.2.4 para encontrar un acoplamiento máximo. c) ¿Existe un acoplamiento completo?
9. El candidato A está calificado para los trabajos J1, J2, J4 y J5; B está calificado para los puestos J1, J4 y J5; Cestá calificado para los puestos J1, J4, y J5; D puede estar en los puestos J1, y J5; E está calificado para los puestos J2, J3 y J5; y F está calificado para los puestos J4 y J5. Conteste los incisos a) al c) del ejercicio 8 para esta situación.
10. El candidato A está calificado para los trabajos J1, J2 y J4; B está calificado para los puestos J3, J4, J5 y J6; C está calificado para los puestos J1 y J5; D puede estar en los puestos J1, J3, J4 y J8; E está calificado para los puestos J1, J2, J4, J6 y J8; F está calificado para los puestos J4 y J6; y G está calificado para J3, J5 y J7. Conteste los incisos a) al c) del ejercicio 8 para esta situación.
11. Cinco estudiantes, V, W, X, Y y Z, son miembros de cuatro comités, C1, C2 C3 y C4. Los miembros de C1 son V, X y Y; los integrantes de C2 son X y Z; los de C3 son V, Y y Z; y los miembros de C4 son V, W, X y Z. Cada comité debe enviar un representante a la ad
ministración. Ningún estudiante puede representar a dos comités. a) Modele esta situación como red de acoplamiento. b) ¿Cuál es la interpretación de un acoplamiento máximo? c) ¿Cuál es la interpretación de un acoplamiento completo? d) Use al algoritmo 10.2.4 para encontrar un acoplamiento máximo. e) ¿Existe un acoplamiento completo?
12. Demuestre que con un orden apropiado de los vértices, la matriz de adyacencia de una gráfica bipartita se puede escribir
donde 0 es una matriz con sólo ceros y AT es la transpuesta de la matriz A.
En los ejercicios 13 al 15, G es una gráfica bipartita, A es la matriz del ejercicio 12, y F es un flujo en la red de acoplamiento asociada. Etiquete cada elemento de A que represente una arista con flujo 1.
14. ¿Qué tipo de etiquetas corresponde a un acoplamiento completo?
15. ¿Qué tipo de etiquetas corresponde a un acoplamiento máximo?
16. Enuncie de nuevo el algoritmo 10.2.4, aplicado a una red de acoplamiento, en términos de las operaciones en la matriz A del ejercicio 12.
Sea G una gráfica bipartita dirigida con conjuntos ajenos de vértices V y W en los que las aristas están dirigidas de los vértices de V a los vértices de W. (Cualquier vértice de G está en V o bien esta en W). La deficiencia se define como
δ(G) = máx{|S|−|R(S)||S ⊆ V}.
17. Demuestre que G tiene un acoplamiento completo si y sólo si δ(G) =0.
18. Demuestre que el máximo número de vértices en V que se pueden acoplar a vértices en W es |V|− δ(G).
19. ¿Falso o verdadero? Cualquier acoplar está contenido en un acoplamiento máximo. Si es verdadero, pruébelo; si es falso, dé un contraejemplo.
