|
|
|
|
connected graph
|
(Definition)
|
|
|
A connected graph is a graph such that there exists a path between all pairs of vertices. If the graph is a directed graph, and there exists a path from each vertex to every other vertex, then it is a strongly connected graph.
A connected component is a maximal (under inclusion) subset of vertices of any graph and any edges between them that forms a connected graph. Similarly, a strongly connected component is a maximal (under inclusion) subset of vertices of any digraph and any edges between them that forms a strongly connected graph. Any graph or digraph is a union of connected or strongly connected components, plus some edges to join the components together. Thus any graph can be decomposed into its connected or strongly connected components. For instance, Tarjan's algorithm can decompose any digraph into its strongly connected components.
For example, the following graph and digraph are connected and strongly connected, respectively.
On the other hand, the following graph is not connected, and consists of the union of two connected components.
The following digraph is not strongly connected, because there is no way to reach  from other vertices, and there is no vertex reachable from  .
The three strongly connected components of this graph are
|
"connected graph" is owned by rspuzio. [ full author list (2) | owner history (1) ]
|
|
(view preamble)
See Also: graph, bridge, cut-vertex, locally connected,  -connected graph, graph topology, (closed) walk / trek / trail / path, connected poset
| Other names: |
connected, strongly connected, component |
| Also defines: |
strongly connected graph, connected components, strongly connected components |
|
|
Cross-references: algorithm, join, plus, union, edges, subset, inclusion, vertex, directed graph, vertices, path, graph
There are 136 references to this entry.
This is version 4 of connected graph, born on 2002-03-02, modified 2005-08-09.
Object id is 2743, canonical name is ConnectedGraph.
Accessed 26687 times total.
Classification:
| AMS MSC: | 05C40 (Combinatorics :: Graph theory :: Connectivity) |
|
|
|
|
|
|
Pending Errata and Addenda
|
|
|
|
|
|
|
|
|
|
|
![\begin{displaymath} \begin{array}{cc} \xymatrix{ A \ar@{-}[r] & B \ar@{-}[r] & C... ...r[r] & C \ar[d]\ D \ar[u] & E \ar[l] & F \ar[l] } \end{array}\end{displaymath}](http://images.planetmath.org:8080/cache/objects/2743/l2h/img1.png "\begin{displaymath} \begin{array}{cc} \xymatrix{ A \ar@{-}[r] & B \ar@{-}[r] & C... ...r[r] & C \ar[d]\ D \ar[u] & E \ar[l] & F \ar[l] } \end{array}\end{displaymath}")
![$\displaystyle \begin{xy} *!C\xybox{ \xymatrix{ A \ar@{-}[r] & B \ar@{-}[r] & C \ D \ar@{-}[r] & E \ar@{-}[r] & F } } \end{xy}$](http://images.planetmath.org:8080/cache/objects/2743/l2h/img2.png "$\displaystyle \begin{xy} *!C\xybox{ \xymatrix{ A \ar@{-}[r] & B \ar@{-}[r] & C \ D \ar@{-}[r] & E \ar@{-}[r] & F } } \end{xy}$")
![$\displaystyle \begin{xy} *!C\xybox{ \xymatrix{ A \ar[r] & B \ar[d] \ar[r] & C \ D \ar[u] & E \ar[l] & F \ar[l]\ar[u] } } \end{xy}$](http://images.planetmath.org:8080/cache/objects/2743/l2h/img5.png "$\displaystyle \begin{xy} *!C\xybox{ \xymatrix{ A \ar[r] & B \ar[d] \ar[r] & C \ D \ar[u] & E \ar[l] & F \ar[l]\ar[u] } } \end{xy}$")
![\begin{displaymath} \begin{array}{ccc} \xymatrix{ A \ar[r] & B\ar[d] \ D \ar[u] & E\ar[l] } & $C$ & $F$ \end{array}\end{displaymath}](http://images.planetmath.org:8080/cache/objects/2743/l2h/img6.png "\begin{displaymath} \begin{array}{ccc} \xymatrix{ A \ar[r] & B\ar[d] \ D \ar[u] & E\ar[l] } & $C$ & $F$ \end{array}\end{displaymath}")