ConnectedGraphComponents

ConnectedGraphComponents[g]

gives the connected components of the graph g.

ConnectedGraphComponents[g,{v1,v2,…}]

gives the connected components that include at least one of the vertices v1, v2, … .

ConnectedGraphComponents[g,patt]

gives the connected components that include a vertex that matches the pattern patt.

ConnectedGraphComponents[{vw,…},…]

uses rules vw to specify the graph g.

Details and Options

  • ConnectedGraphComponents returns a list of components {c1,c2,…}, where each component ci is given as a graph.
  • For an undirected graph, the vertices u and v are in the same component if there is a path from u to v.
  • For a directed graph, the vertices u and v are in the same component if there is a directed path from u to v and from v to u.
  • For directed graphs, strongly connected components are computed.
  • For undirected graphs, the components are ordered by their length, with the largest component first.
  • For directed graphs, the components {c1,c2,…} are given in an order such that there are no edges from ci to ci+1, ci+2, etc.
  • ConnectedGraphComponents works with undirected graphs, directed graphs, multigraphs, and mixed graphs.

Examples

open allclose all

Basic Examples  (1)

Give the connected components of a graph:

Highlight connected components:

Scope  (8)

ConnectedGraphComponents works with undirected graphs:

Directed graphs:

Multigraphs:

Mixed graphs:

Use rules to specify the graph:

Select connected components that include at least one of the specified vertices:

Use patterns to select a subset of connected components:

ConnectedGraphComponents works with large graphs:

Applications  (4)

Highlight components with more than one vertex in a graph:

A frog in a lily pond is able to jump 1.5 feet to get from one of the 25 lily pads to another. Model the frog's jumping network from the lily leaf density and SpatialGraphDistribution:

Sample a random pond:

Find the largest collection of lily pads the frog can jump between:

Find the number of times the frog would have to swim to visit all lily pads:

Find a permutation p such that the matrix A〚p-1,p〛 is block triangular:

Connected components of nonzero positions form block submatrices:

The permutation p:

Properties & Relations  (4)

Use WeaklyConnectedGraphComponents to get weakly connected components for directed graphs:

Connected components:

Use ConnectedGraphQ to test whether a graph is connected:

A connected graph has exactly one connected component:

Every graph with vertices and edges has at least components:

Wolfram Research (2016), ConnectedGraphComponents, Wolfram Language function, https://reference.wolfram.com/language/ref/ConnectedGraphComponents.html.

Text

Wolfram Research (2016), ConnectedGraphComponents, Wolfram Language function, https://reference.wolfram.com/language/ref/ConnectedGraphComponents.html.

CMS

Wolfram Language. 2016. "ConnectedGraphComponents." Wolfram Language & System Documentation Center. Wolfram Research. https://reference.wolfram.com/language/ref/ConnectedGraphComponents.html.

APA

Wolfram Language. (2016). ConnectedGraphComponents. Wolfram Language & System Documentation Center. Retrieved from https://reference.wolfram.com/language/ref/ConnectedGraphComponents.html

BibTeX

@misc{reference.wolfram_2024_connectedgraphcomponents, author="Wolfram Research", title="{ConnectedGraphComponents}", year="2016", howpublished="\url{https://reference.wolfram.com/language/ref/ConnectedGraphComponents.html}", note=[Accessed: 22-December-2024 ]}

BibLaTeX

@online{reference.wolfram_2024_connectedgraphcomponents, organization={Wolfram Research}, title={ConnectedGraphComponents}, year={2016}, url={https://reference.wolfram.com/language/ref/ConnectedGraphComponents.html}, note=[Accessed: 22-December-2024 ]}