Suppose some people form committees to do various tasks. The problem is to sched

Question

Suppose some people form committees to do various tasks. The problem is to schedule the committee meetings in as few time slots as possible. This problem was introduced in Example 3 of Section 1.4, where S = {1, 2, 3, 4, 5, 6, 7} represents a set of seven people who have formed six 3-person committees as follows: S_1 = {1, 2, 3}, S_2 = {2, 3, 4}, S_3 = {3, 4, 5}, S_4 = {4, 5, 6}, S_5 = {5, 6, 7}, S_6 = {1, 6, 7} The problem can be modeled with the following graph, where the committee names are represented as vertices and there is an edge between two vertices if a person belongs to both committees. b. What does an edge between two vertices in the complement graph signify?

Explanation / Answer

As mentioned, if there is an edge between two committees, both the committee has atleast one member in common.
So if we consider two committees with atleast one member in common, i.e. we select two different vertices with an edge in between, the common member(s) in the committee can discuss and exchange ideas between the committees and thus they don't require a meeting to be scheduled.
So looking at the graph we can say that we only need to schedule meetings between committee with no edge connecting them.

So minimum number of meeting required is 6C2 - |E| or 15 - 10 = 5 meetings required

I explained my views with respect to the context given in the question. I hope you haven't faced any difficulty understanding my views I tried to convey. If you have a different view that contradicts mine, I would be really grateful to hear that from you.

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.