Assignment 7 Solution

1.    (100 pts) Write a program to read a graph from a le and determine whether the graph is a tree or not. A sample graph is given below.

 

2                 3              4



 

 

 

 5                 6

 

 

1

 

Figure 1: Graph representation

 

You can visually see that this graph is not a tree. To determine whether a graph is a tree you can use the following theorem.

 

Theorem: Any connected graph with n vertices and n-1 edges is a tree.

 

Above graph is connected. However, it has 6 vertices and 7 edges. So, it is not a tree. File format for this assignment is as follows

 

numofvertices numofedges

 

edge1

 

edge2

 

....

 

First line of the le contains the number of vertices and number of edges. Each edge is listed on one line with source vertex and destination vertex. Vertices start at 1. Edges are undirected and will be listed on the le once starting with the smallest vertex id. For example, for edges 2-5 and 5-2 the le will only have 2-5. But, you need to insert both to your adjacency list representation.

 

File for above graph is as follows

 

6   7

 

1 2

 

1 5

 

1 6

 

2 5

 

3 4

 

3 5

 

4 6

 

Sample execution of the program for the above graph is as follows

 

fox01 assign7 graph1.txt

 

The graph does not belong to a tree
Powered by