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:
“The genius of democracies is seen not only in the great number of new words introduced but even more in the new ideas they express.”
—Alexis de Tocqueville (1805–1859)
“Religious fervor makes the devil a very real personage, and anything awe-inspiring or not easily understood is usually connected with him. Perhaps this explains why, not only in the Ozarks but all over the State, his name crops up so frequently.”
—Administration in the State of Miss, U.S. public relief program (1935-1943)
“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)