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:
“That country is the richest which nourishes the greatest number of noble and happy human beings.”
—John Ruskin (1819–1900)
“We can’t nourish our children if we don’t nourish ourselves.... Parents who manage to stay married, sane, and connected to each other share one basic characteristic: The ability to protect even small amounts of time together no matter what else is going on in their lives.”
—Ron Taffel (20th century)
“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)