## Description

Problem Deﬁnition

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 ﬁle name.

0.2 The Input File Format

Each input ﬁle 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 deﬁned. 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 ﬁrst 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 ﬁrst 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 ﬁle. You must ﬁrst compress the ﬁle using gzip -c filename.c filename.c.gz and then the compressed .gz ﬁle 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 ﬁnding 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 speciﬁcally, what type of edge will you ﬁnd 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 iﬀ there is a 2-colouring of the vertices such that no two monochromatic vertices are adjacent.