2. Suppose you and your friend Alanis live together with n -2 other people at a popular "cooperative" apartment. Over the next n nights, each of you is supposed to cook dinner for the co-op exactly once, so some one cooks on each of the nights. To make things interesting, everyone has scheduling conflicts with some of the (e.g., exams, deadlines at work, basketball games, etc.), so deciding who should cook on which night becomes a tricky task. For concreteness, let's label the people PPnand the nights di.....dn]. Then for person pi, associate a set of nights S(d dn when they are not available to cook. A feasible dinner schedule is defined to be an assignment of each person in the co-op to a different night such that each person cooks on exactly one night, there is someone to cook on each night, and ifp, cooks on night d" then dj S, . (a) |10 points Describe a bipartite graph G such that G has a perfect matching if and only if there is a feasible dinner schedule for the co-op (b) 10 pointsl 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 work 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 she has accidentally assigned both pi and pj to cook on night dk and no one to cook on night d. You want to fix the schedule but without having to recompute everything from scratch. Show that it is 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, your algorithm should also provide that schedule. 2. Suppose you and your friend Alanis live together with n -2 other people at a popular "cooperative" apartment. Over the next n nights, each of you is supposed to cook dinner for the co-op exactly once, so some one cooks on each of the nights. To make things interesting, everyone has scheduling conflicts with some of the (e.g., exams, deadlines at work, basketball games, etc.), so deciding who should cook on which night becomes a tricky task. For concreteness, let's label the people PPnand the nights di.....dn]. Then for person pi, associate a set of nights S(d dn when they are not available to cook. A feasible dinner schedule is defined to be an assignment of each person in the co-op to a different night such that each person cooks on exactly one night, there is someone to cook on each night, and ifp, cooks on night d" then dj S, . (a) |10 points Describe a bipartite graph G such that G has a perfect matching if and only if there is a feasible dinner schedule for the co-op (b) 10 pointsl 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 work 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 she has accidentally assigned both pi and pj to cook on night dk and no one to cook on night d. You want to fix the schedule but without having to recompute everything from scratch. Show that it is 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, your algorithm should also provide that schedule