graph algorithm finding if graph is connected, bipartite, has cycle and is a tree

Question

I came to a problem when I was trying to work with graphs and write some code for it but with no luck :/ !!

I wanted to created something that will take the data of the graph and check if it is: 1- connected 2- bipartite 3- has cycle 4- is a tree

so I was wondering for example if this can be written to read a graph data from a .txt file that will do the above tests ??

using simple edge-list format is the correct approach for it ?

your help is appreciated if you can give me a link to read about how to do this task or a kick start for a code !!

thanks :D

Answer 1

check if it is:

1. connected

For this one, you try to traverse the entire graph from one point, and see if you succeed. Both depth-first traversal and breadth-first traversal are acceptable here. This algorithm will split the node into components:

• mark all nodes as unvisited
• for every node c, if this node is unvisited
  • create a new empty set of nodes, the current component
  • enqueue the this node for traversal
  • while there is any node t enqueued
    • remove this node from the queue
    • mark every unvisited neighbor as open and enqueue it for traversal
    • mark this node as traversed
    • add this node to the current component
  • close the current component, and add it to the set of components

If there is only one component, the graph is connected.

If a queue is used, the algorithm is a breadth-first search. If a stack is used, the algorithm is a depth-first search. Any other collection with the push and pop-any operations will do. Of special interest is the call-stack: replace "enqueue for traversal" with "traverse recursively"

For directed graphs, there are two related concepts: A directed graph is weakly connected iff it is connected neglecting all edge directions. A directed graph is strongly connected iff every node is reachable from every node. To test for strong connectedness it sufficces to check every node is reachable from the first node using only forward edges, and every node is reachable from the first node using only backwards edges (the first node is reachable from every node).

1. bipartite

A graph is bipartite iff it is bicolorable. Try to assign a bicoloring, and if you fail, the graph is not bipartite. This can be incorporated into the previous algorithm: Whenever you mark a node as open, assign a color to it, opposite to the color assigned to its neighbor t. When a neighbor of t is already open, check its color. If its color is the same as that of t, there is no bicoloring.

1. has cycle

This one is easy: If you observe any node that is already open, there is a cycle. Note that every graph that has no cycle is bipartite.

In directed graphs, this will detect the presence of an undirected cycle. To detect the presence of directed cycles, use the following (topological sort) algorithm:

• while there is a node with the indegree of zero
  • add the node to the topological sort (irrelevant for detecting cycles)
  • remove the node from the graph
• if there is still any node in the graph
  • the graph contains a directed cycle. No topological sort exists on that graph
• else
  • the graph does not contain a directed cycle (is acyclic). The topological sort generated is valid.

1. tree

An undirected graph is a tree iff it is connected and contains no cycle.

A directed graph is a rooted tree iff it has no undirected cycles and there is only one vertex with an indegree of zero (only one root). Also, a directed graph is a rooted tree iff it is connected, has no undirected cycles and every node with an outdegree of zero has an indegree of at most one (every sink is a leaf).