According to McCabe’s graph-theoretic definition, the cyclomatic number V(G)…
2011
According to McCabe’s graph-theoretic definition, the cyclomatic number V(G) of a graph G with n vertices, e edges, and p connected components is:
Answer: C. \(e - n + p\) — ConceptMcCabe’s graph-theoretic definition calls V(G) the cyclomatic number: the number of independent cycles in a graph with e edges, n vertices, and p…
- A.
\(e\)
- B.
\(n\)
- C.
\(e - n + p\)
- D.
\(e - n + 2p\)
Attempted by 38 students.
Show answer & explanation
Correct answer: C
Concept
McCabe’s graph-theoretic definition calls V(G) the cyclomatic number: the number of independent cycles in a graph with e edges, n vertices, and p connected components.
It compares the edge count with a spanning forest, which contains n − p edges.
Application
A spanning forest of the p components contains n − p edges.
Every edge beyond those n − p forest edges adds one independent cycle.
Therefore, V(G) = e − (n − p) = e − n + p.
Cross-check and contrast
For a connected graph, p = 1, so the formula becomes V(G) = e − n + 1, the usual cycle-rank formula.
McCabe separately obtains program cyclomatic complexity C(G) = V(G) + p = e − n + 2p by closing each program-flow component with one additional edge; that is not the graph cyclomatic number V(G) named in the stem.
Hence, under McCabe’s stated graph-theoretic definition, V(G) = e − n + p.