The Number of Connected Components
The number of connected components is an important topological invariant of a graph. In topological graph theory it can be interpreted as the zeroth Betti number of the graph. In algebraic graph theory it equals the multiplicity of 0 as an eigenvalue of the Laplacian matrix of the graph. It is also the index of the first nonzero coefficient of the chromatic polynomial of a graph. Numbers of connected components play a key role in the Tutte theorem characterizing graphs that have perfect matchings, and in the definition of graph toughness.
Read more about this topic: Connected Component (graph Theory)
Famous quotes containing the words number, connected and/or components:
“Can it be, that the Greek grammarians invented their dual number for the particular benefit of twins?”
—Herman Melville (1819–1891)
“I like to see a home like this, a home connected with people’s thoughts and work, things they love.”
—Dewitt Bodeen (1908–1988)
“Hence, a generative grammar must be a system of rules that can iterate to generate an indefinitely large number of structures. This system of rules can be analyzed into the three major components of a generative grammar: the syntactic, phonological, and semantic components.”
—Noam Chomsky (b. 1928)