Analysis of Complex Networks

9.10 Cycles in Graphs

The identification of ring structures constitutes a large part of the structural topology in the study and characterization of molecular structures. Chemical compounds with rings can be represented as graphs. If a graph represents a compound without cycles, then the number of edges it has will be equal to the number of atoms minus 1. Graphs of compounds without cycles are called acyclic and can be presented as trees. To draw a graph in 2D, a common practice is to start with the largest ring from the set of smallest rings, which highlights the importance of algorithms for determining the size of rings. Rings are characterized as essential or nonessential. Nonessential rings are those that are tied, multitied, or dependent rings. A tied ring is defined as a ring with one transannular bond that links directly two nonadjacent nodes of rings. Essential rings are rings other than nonessential rings.

Many different approaches for the extraction of cycles from molecular graphs such as the smallest set of smallest rings (SSSR), essential set of essential rings (ESER), extended set of smallest rings (ESSR), and the set of smallest cycles at edges (SSCE) have been used. The popular graph theory problem of finding the SSSR is ambiguous and, unlike the ERER, is not used in organic chemistry. The definition of what is essential varies, and in practice the problem is solved by finding an ESSR. To solve it a tree is constructed from each vertex of the graph, which terminates ...