# CS 2110 Lab 9 Characterizing a Graph

\$30.00

## Description

Given an undirected graph G, you are to report the following.
• Is the graph connected?
• Is the graph cyclic?
• 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.
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.
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