maximally connected component

(definition)

Definition: A connected subgraph of a graph to which no vertex can be added and it still be connected.

Formal Definition: Given a graph G=(V, E), a subgraph S=(V', E') is a maximally connected component if

• S is connected, and
• for all vertices u such that u∈ V and u∉ V' there is no vertex v∈ V' for which (u, v)∈ E.

See also connected graph, connected components, biconnected component, strongly connected component.

Note: Informally, (one of) the biggest connected subgraph(s) of a graph. Also know as "connected component", with the "maximal" property understood.

Author: AL

More information

(C++, C, Pascal, Mathematica, and Fortran)

If you have suggestions, corrections, or comments, please get in touch with Paul Black.

Entry modified 2 September 2014.
HTML page formatted Mon Feb 2 13:10:39 2015.

Cite this as:
Alen Lovrencic, "maximally connected component", in Dictionary of Algorithms and Data Structures [online], Vreda Pieterse and Paul E. Black, eds. 2 September 2014. (accessed TODAY) Available from: http://www.nist.gov/dads/HTML/maximallyConnectedComponent.html