Description
Given an undirected graph G, you are to report the following.
• Is the graph connected?
• Is the graph cyclic?
• Is the graph a tree? (Note the answer to this question comes for free.)
• Is the graph bipartite?
0.1 Command Line Arguments
Your command line argument for this assignment is a single input file name.
0.2 The Input File Format
Each input file should contain one graph. The format is as follows. First you must have an
integer n which represents the number of vertices on which the graph is defined. Given n, the
n-element vertex set is implicitly understood to be {0, 1, . . . , n − 1}. Then, you will need to
have a n × n binary matrix. The following is an example.
4
1 0 0 1
1 0 1 1
0 0 0 0
0 1 0 1
1
Note that the input may not be a symmetric matrix. For this assigmnent, you must first
make this a symmetric matrix. More precisely, if either aij = 1 or aji = 1, then you should
make both aij = aji = 1.
0.3 Output Format
For this lab, you again get a reprieve from strict output formatting. You must simply report
all the required information in an understandable way.
You can use depth first search (DFS) to solve this assignment. See the wikipedia page on DFS if needed.
In the next page, I am providing some hints on how to solve this problem.
You can skip them if you want to think on your own.
Uploading into MOODLE
Your code should be written as a single .c file. You must first compress the file using gzip -c
filename.c > filename.c.gz and then the compressed .gz file must be uploaded into moodle.
A link will be set up for this purpose in moodle.
Your TA for this lab
CS08B031, CS10B052, CS11B001 — CS11B009 Nishaanth
CS11B011 — CS11B021 Saurav Kant Jha
CS11B022 — CS11B032 Tejas Kulkarni
CS11B033 — CS11B042 Paresh Nakhe
CS11B043 — CS11B053 Shrikant Polawar
CS11B054 — CS11B063 Sai Sreenivas
2
Hints and intuition behind solving the problems
First, read the wikipedia page on DFS if you are not aware of DFS.
Perform a DFS starting from some arbitrary node. If the DFS traversal hits every node in
the graph, then the graph is connected.
What type of edge must you encounter in order to conclude that the graph is cyclic? Thinking about this question will give you the solution to finding whether a graph is cyclic.
Finally, modify the DFS to keep track of the distance (or at least the parity of the distance,
i.e., odd or even distance) from the starting node in the DFS tree. Suppose each node at
an even distance is coloured “red” and the nodes in odd distance are coloured blue. When
will two nodes of the same colour be adjacent? More specifically, what type of edge will you
find between such monochromatic adjacent vertices? Use this to answer whether the graph is
bipartite or not. Just in case you forgot, recall the following theorem.
Theorem 1 A connected graph G is bipartite iff there is a 2-colouring of the vertices such that
no two monochromatic vertices are adjacent.
3
