Enable JavaScript to interact with content and submit forms on Wolfram websites. Learn how

Wolfram Language & System Documentation Center

LambdaComponents

LambdaComponents

LambdaComponents[g]

gives the lambda components of the graph g.

LambdaComponents[g,{v₁,v₂,…}]

gives the lambda components that include at least one of the vertices {v₁,v₂,…}.

LambdaComponents[{vw,…},…]

uses rules vw to specify the graph g.

Details

LambdaComponents is also known as a lambda set.
A lambda component is a set of vertices that have more edge-independent paths connecting them to each other than to outside vertices.
LambdaComponents returns a list of components {c₁,c₂,…}, where each component c_i is given as a list of vertices.
LambdaComponents[g] is equivalent to LambdaComponents[g,VertexList[g]].
LambdaComponents works with undirected graphs, directed graphs, multigraphs, and mixed graphs.

Examples

open all close all

Basic Examples (1)

Give the lambda components for a graph:

Wolfram Language code: LambdaComponents[[image]]

Scope (6)

LambdaComponents works with undirected graphs:

Wolfram Language code: LambdaComponents[[image]]

Directed graphs:

Wolfram Language code: LambdaComponents[[image]]

Multigraphs:

Wolfram Language code: LambdaComponents[[image]]

Mixed graphs:

Wolfram Language code: LambdaComponents[[image]]

Give the components that include at least one of the vertices:

Wolfram Language code: LambdaComponents[[image], {1, 3}]

Use rules to specify the graph:

Wolfram Language code: LambdaComponents[{1 -> 2, 1 -> 3, 2 -> 4, 3 -> 4, 3 -> 5, 4 -> 6, 5 -> 6}]

Applications (2)

Highlight all lambda components in a graph:

Wolfram Language code: g = [image];

Wolfram Language code: Table[HighlightGraph[g, Subgraph[g, i], VertexSize -> 0.2], {i, LambdaComponents[g]}]

A family network consisting of the closest relatives, including parents, siblings, and children. Find a smallest family group with more than one member, where relatives have more edge-independent paths connecting them to each other than to relatives outside the group:

Wolfram Language code: g = ExampleData[{"NetworkGraph", "FamilyGathering"}]

The first nontrivial λ component occurs after the singletons:

Wolfram Language code: λ = LambdaComponents[g];Length /@ λ

Wolfram Language code: HighlightGraph[g, Subgraph[g, λ[[VertexCount[g] + 1]]]]

Properties & Relations (2)

All Luccio–Sami components are lambda components:

Wolfram Language code: g = [image];

Wolfram Language code: LuccioSamiComponents[g]

Wolfram Language code: LambdaComponents[g]

Wolfram Language code: MemberQ[LuccioSamiComponents[g], Alternatives @@ LambdaComponents[g]]

The converse is not always true:

Wolfram Language code: MemberQ[LambdaComponents[g], {5, 6, 7, 8}]

Wolfram Language code: MemberQ[LuccioSamiComponents[g], {5, 6, 7, 8}]

Lambda components are partially ordered by inclusion:

Wolfram Language code: g = [image];

Wolfram Language code: λ = LambdaComponents[g]

The corresponding directed acyclic graph:

Wolfram Language code:

AdjacencyGraph[λ, Table[Boole@(SubsetQ[λ[[j]], λ[[i]]] && λ[[i]] != λ[[j]]), {i, Length[λ]}, {j, Length[λ]}], VertexLabels -> "Name", ImagePadding -> 10]

Wolfram Language code: AcyclicGraphQ[%]

Top