retagged by
762 views
1 votes
1 votes

Your college has sent a contingent to take part in a cultural festival at a neighbouring institution. Several team events are part of the programme. Each event takes place through the day with many elimination rounds. Your contingent is multi-talented and each individual has the skills to take part in a subset of the events. However, the same individual cannot be part of the team for two different events because of a possible clash in timings. Your aim is to create teams to take part in as many events as possible.

To do this, you decide to model the problem as a graph where the nodes are the events and edges represent pairs of events where the team that you plan to send shares a member. In this setting, the graph theoretic question to be answered is:

  1. Find a maximum length simple cycle
  2. Find a maximum size independent set
  3. Find a maximum matching
  4. Find a maximal connected component
retagged by

1 Answer

1 votes
1 votes
$\mathbf{\underline{Answer:\Rightarrow (b})}$

$\mathbf{\underline{Explanation:\Rightarrow }}$

As all the students are multi-talented, then we do want most of them to participate so as to maximize the gain, and also because each individual has the skills to take part in the subset of events.

So, we just have to calculate the maximum independent set for this problem where the nodes represent the events and edges represent the pair of events, when the above situation is represented graphically.
edited by
Answer:

Related questions

1 votes
1 votes
2 answers
1
gatecse asked Sep 13, 2019
626 views
Let $G$ be a simple graph on $n$ vertices.Prove that if $G$ has more than $\binom{n-1}{2}$ edges then $G$ is connected.For every $n>2$, find a graph $G_{n}$ which has exa...
6 votes
6 votes
3 answers
3
gatecse asked Sep 13, 2019
755 views
Let $G=(V, E)$ be an undirected simple graph, and $s$ be a designated vertex in $G.$ For each $v\in V,$ let $d(v)$ be the length of a shortest path between $s$ and $v.$ ...