4. Bipartite Graphs, K&T Ch.7 Ex.15. Suppose you and your friend Alanis live, together with n-2 other people for a total of n, at a popular offcampus cooperative apartment, the Upson Collective. Over the next n nights, each of you is supposed to cook dinner for the co-op exactly once, so that someone cooks on each of the nights. Of course, everyone has scheduling conflicts with some of the nights (e.g., exams, concerts, etc.), so deciding who should cook on which night becomes a tricky task. For concreteness, lets label the people p?,... , pn) and the nights sdi,...,dn^. For person P, theres a set of nights S C [di,... , dn) when they are not able to cook. Homework 5 1-2 A feasible dinner schedule is an assignment of each person in the co-op to a different night, so that each person cooks on exactly one night, there is someone cooking on each night, and if p, cooks orn night dj , then dj (a) Describe a bipartite graph G so that G has a perfect matching if and only if there is a feasible dinner schedule for the co-op. (b) Your friend Alanis takes on the task of trying to construct a feasible dinner schedule. After great effort, she constructs what she claims is a feasible schedule and then heads off to class for the day. Unfortunately, when you look at the schedule she created, you notice a big problem. n -2 of the people at the co-op are assigned to different nights on which they are available: no problem there. But for the other two people, p, and pj, and the other two days, dk and d? you discover that she has accidentally assigned both p, and p, to cook on night dk, and assigned no one to cook on night di You want to fix Alanis's mistake but without having to recompute everything from scratch. Show that its possible, using her almost correct schedule, to decide in only O(n2) time whether there exists a feasible dinner schedule for the co-op. (If one exists, you should also output it) 4. Bipartite Graphs, K&T Ch.7 Ex.15. Suppose you and your friend Alanis live, together with n-2 other people for a total of n, at a popular offcampus cooperative apartment, the Upson Collective. Over the next n nights, each of you is supposed to cook dinner for the co-op exactly once, so that someone cooks on each of the nights. Of course, everyone has scheduling conflicts with some of the nights (e.g., exams, concerts, etc.), so deciding who should cook on which night becomes a tricky task. For concreteness, lets label the people p?,... , pn) and the nights sdi,...,dn^. For person P, theres a set of nights S C [di,... , dn) when they are not able to cook. Homework 5 1-2 A feasible dinner schedule is an assignment of each person in the co-op to a different night, so that each person cooks on exactly one night, there is someone cooking on each night, and if p, cooks orn night dj , then dj (a) Describe a bipartite graph G so that G has a perfect matching if and only if there is a feasible dinner schedule for the co-op. (b) Your friend Alanis takes on the task of trying to construct a feasible dinner schedule. After great effort, she constructs what she claims is a feasible schedule and then heads off to class for the day. Unfortunately, when you look at the schedule she created, you notice a big problem. n -2 of the people at the co-op are assigned to different nights on which they are available: no problem there. But for the other two people, p, and pj, and the other two days, dk and d? you discover that she has accidentally assigned both p, and p, to cook on night dk, and assigned no one to cook on night di You want to fix Alanis's mistake but without having to recompute everything from scratch. Show that its possible, using her almost correct schedule, to decide in only O(n2) time whether there exists a feasible dinner schedule for the co-op. (If one exists, you should also output it)
