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:
“Mining today is an affair of mathematics, of finance, of the latest in engineering skill. Cautious men behind polished desks in San Francisco figure out in advance the amount of metal to a cubic yard, the number of yards washed a day, the cost of each operation. They have no need of grubstakes.”
—Merle Colby, U.S. public relief program (1935-1943)
“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)