The Gateway to Computer Science Excellence
0 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
in Graph Theory by Boss (17.5k points)
retagged by | 32 views

1 Answer

0 votes
Ans $(b)$

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.
by Boss (19.2k points)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,384 answers
105,331 users