# Lab 9 Characterizing a Graph solution

\$14.99

Original Work ?

## Description

5/5 - (1 vote)

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.