Difference between revisions of "Connected component (graph theory)"
From Wiki @ Karl Jones dot com
Karl Jones (Talk | contribs) (→See also) |
Karl Jones (Talk | contribs) (→See also) |
||
| Line 14: | Line 14: | ||
* [[Connected-component labeling]], a basic technique in computer image analysis based on connected components of graphs | * [[Connected-component labeling]], a basic technique in computer image analysis based on connected components of graphs | ||
* [[Giant component]] | * [[Giant component]] | ||
| + | * [[Graph theory (mathematics)]] | ||
* [[Modular decomposition]], for a proper generalization of connected components on undirected graphs | * [[Modular decomposition]], for a proper generalization of connected components on undirected graphs | ||
* [[Percolation theory]], a theory describing the behavior of connected components in random subgraphs of grid graphs | * [[Percolation theory]], a theory describing the behavior of connected components in random subgraphs of grid graphs | ||
Latest revision as of 15:01, 6 December 2016
In graph theory, a connected component (or just component) of an undirected graph is a subgraph in which any two vertices are connected to each other by paths, and which is connected to no additional vertices in the supergraph.
For example, the graph shown in the illustration on the right has three connected components.
A vertex with no incident edges is itself a connected component.
A graph that is itself connected has exactly one connected component, consisting of the whole graph.
See also
- Biconnected component
- Bridge (graph theory)
- Centrality
- Connected-component labeling, a basic technique in computer image analysis based on connected components of graphs
- Giant component
- Graph theory (mathematics)
- Modular decomposition, for a proper generalization of connected components on undirected graphs
- Percolation theory, a theory describing the behavior of connected components in random subgraphs of grid graphs
- Strongly connected component, a related concept for directed graphs
External links
- Connected component (graph theory) @ Wikipedia
