Must be in python Consider a graph (V,E) where V is a set of nodes and E is a se
ID: 3887709 • Letter: M
Question
Must be in python
Consider a graph (V,E) where V is a set of nodes and E is a set of edges which connect 2 nodes and ordering on the elements in V , then the cover of two connected vertices vi and vj is defined as the distance in the ordering between vi and vj . The maximum cover of the ordering is then defined as the maximum of the individual covers. For example, consider the following graph: This can be
Figure 1: A Sample Graph
sample graph couldnt be uploaded but consists of a 3d box with points A,B,C... all the way to letter H.
ordered in many ways, two of which are illustrated below (with lines connecting adjacent vertices): For these orderings, the maximum covers of the nodes (in order) are 6, 6, 1, 4, 1, 1, 6, 6 giving a
Figure 2: Two possible orderings
maximum cover of 6, and 5, 3, 1, 4, 3, 5, 1, 4 giving a maximum cover of 5. Write a program that will find the ordering of a graph that minimizes the maximum cover.
Input
Input consists of a series of graphs. The first line of input contains a single integer g indicating the number of graphs. The first line of each graph contains of an integer n indicating the number (n > 0) of vertices in the graph. The next n lines are of the format ldl1l2...ld indicating that vertex l is connected to the vertices l1, l2. . . andld Although for analysis you should assume an infinite number of nodes, each node name (a single upper case character in the range ‘A’ to ‘Z’ .
Output
Output will consist of one line for each graph, listing the ordering of the nodes followed the maximum cover for that ordering. All items must be separated from their neighbors by exactly one space. If more than one ordering produces the same maximum cover, then choose the one that would appear first in an alphabetic listing.
Sample Input
1
8
A2BF B3AGC C2BD D3CGE E2DH F3AGH G3BFD H2FE
Corresponding Sample Output
ABCFGDHE3
Required Data Structure
2
CIS 350/3501 Barely Covered Fall 2017
{
public:
};
Explanation / Answer
False. An arbitrary vertex could lay closer to the ’center’ of the graph, hence the BFS depth will be underestimating the diameter. For example, in graph G = (V, E) = ({a, v, b}, {(a, v),(v, b)}), a BFS from v will have depth 1 but the graph has diameter 2.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.