Answer:
Relative greedy algorithm is not optimal
Explanation:
Proving that Relative’s greedy algorithm is not optimal.
This can be further proved by the following example.
Let us assumethe friends to be invited be Ali, Bill, David, Dennis, Grace, Eemi, and Sam.
The enemy list of each friend is shown below:
• Ali: Bill. David, Dennis
• Bill: Ali, Grace, Eemi, Sam
• David: Ali, Grace, Eemi, Sam
• Dennis: Ali, Grace, Eemi, Sam
• Grace: Bill. David, Dennis. Eemi . Sam
• Eemi: Bill, David, Dennis, Grace, Sam
• Sam: Bill, David, Dennis, Eemi, Grace
From the enemy list, the one with fewer enemies is Ali.
If we invite Ali, then Bill, David, and Dennis cannot be invited.
Next person that can be invited is one from Grace, Eemi, and Sam
If we choose any one of them we cannot add any other person.
For example, if we choose Grace, all other members are enemies of Ali and Grace. So only Ali
and Grace can only be invited.
So we get a list of two members using relative’s greedy algorithm.
This is not the optimal solution.
The optimal solution is a list of 3 members
• Bill, David, and Dennis can be invited to the party.
Hence, it is proved that relative’s greedy algorithm is not optimal, where the maximum number of friends is not invited to the party.
