Ravishing Journey

Study hacks…..

Cycle and its detection in graphs

on September 20, 2013

In graph theory, the term cycle may refer to a closed path. If repeated vertices are allowed, it is more often called a closed walk. If the path is a simple path, with no repeated vertices or edges other than the starting and ending vertices, it may also be called a simple cyclecircuitcircle, or polygon; see Cycle graph. A cycle in a directed graph is called a directed cycle.

The term cycle may also refer to:

  • An element of the binary or integral (or real, complex, etc.) cycle space of a graph. This is the usage closest to that in the rest of mathematics, in particular algebraic topology. Such a cycle may be called a binary cycleintegral cycle, etc.
  • An edge set that has even degree at every vertex; also called an even edge set or, when taken together with its vertices, an even subgraph. This is equivalent to a binary cycle, since a binary cycle is the indicator function of an edge set of this type.

Chordless cycles in a graph are sometimes called graph holes. A graph antihole is the complement of a graph hole.

Cycle detection :

  • Undirected Graphs :

An undirected graph has a cycle if and only if a depth-first search (DFS) finds an edge that points to an already-visited vertex (a back edge). Equivalently, all the back edges, which DFS skips over, are part of cycles. In the case of undirected graphs, only O(n) time is required, since at most n – 1 edges can be tree edges (where n is the number of vertices).

  • Directed Graphs :

Basically this post has been written to explain the simple and straight forward way to detect cycle in a directed graph. The method explained below is the simple and correct way to do it.

directed graph has a cycle if and only if a DFS finds a back edge. Forward and cross edges do not necessarily indicate cycles. Many topological sorting algorithms will detect cycles too, since those are obstacles for topological order to exist. Also, if a directed graph has been divided into strongly connected components, cycles only exist within the components and not between them, since cycles are strongly connected.

An easy way to do this is to attempt a topological-order traversal using the algorithm given in Section . This algorithm only visits all the vertices of a directed graph if that graph contains no cycles.

To see why this is so, consider the directed cyclic graph tex2html_wrap_inline70919 shown in Figure . The topological traversal algorithm begins by computing the in-degrees of the vertices. (The number shown below each vertex in Figure is the in-degree of that vertex).

 figure50647

Figure: A directed cyclic graph.

 At each step of the traversal, a vertex with in-degree of zero is visited. After a vertex is visited, the vertex and all the edges emanating from that vertex are removed from the graph. Notice that if we remove vertex a and edge (a,b) from tex2html_wrap_inline70919, all the remaining vertices have in-degrees of one. The presence of the cycle prevents the topological-order traversal from completing.

Therefore, the a simple way to test whether a directed graph is cyclic is to attempt a topological traversal of its vertices. If all the vertices are not visited, the graph must be cyclic.

Below program  gives the implementation of the isCyclic method of the AbstractGraph class. This boolean-valued accessor returns true if the graph is cyclic. The implementation simply makes uses a visitor that counts the number of vertices visited during a topologicalOrderTraversal of the graph.

 program50816

Program: AbstractGraph class isCyclic method.

 The worst-case running time of the isCyclic method is determined by the time taken by the topologicalOrderTraversal. Since tex2html_wrap_inline60292, the running time of isCyclic is tex2html_wrap_inline70467 when adjacency matrices are used to represent the graph and tex2html_wrap_inline70663 when adjacency lists are used.

Applications :

          Applications of cycle detection include the use of wait-for graphs to detect deadlocks in concurrent systems.

See also :

Advertisements

One response to “Cycle and its detection in graphs

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: