## 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