Solved–Assignment VIII –Solution

Description

1. There is total N number of players. There might be rivalry between any two players. Let’s say there is rivalry between R pairs of players. Write a program to distribute these players into two teams (might not be of equal size) such that there is no rivalry between any two players of a team.

Upload file Assignment8A.c

2. In this problem you need to construct graph G=(V,E) using a set of English words each having 5 characters. The nodes of the graph will be represented by these words. There will be an edge between two words say X and Y if we can reach from X to Y by the following series of operations i)remove the first character ii) add any character iii) rearrange characters. For example there will be an edge between: words — dross — soars — orcas — crash — sharp — graph. You may use adjacency list or adjacency matrix to store this graph.

1. 1. Find out whether a graph, created from given set of words, contains any cycle or not. If it contains any cycle then print “GRAPH IS CYCLIC” otherwise print

“GRAPH IS ACYCLIC”.

1. 2. `For every pair of nodes (i,j) determine if there is a path from i to j or not. Print the result in matrix form.

Upload file Assignment8B.c

C. Given an undirected graph with N vertices and M edges what is the maximum number of edges in any connected component of the graph. In other words, if given graph has k connected components, and E1,E2,….Ek be the number of edges in the

respective connected component, then find max(E1,E2,….,Ek).

Upload file Assignment8C.c