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

Wolfram Language & System Documentation Center

VertexContract

VertexContract

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

contracts a collection of vertices v₁, v₂, … into a single vertex of the graph g.

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

contracts several collections of vertices.

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

uses rules vw to specify the graph g.

Details and Options

VertexContract is also known as vertex identification.
VertexContract[g,{v₁,v₂,…}] creates a new graph from g by removing all edges between v_i and v_j and merging them into the single vertex v₁.

VertexContract works with undirected graphs, directed graphs, multigraphs, and mixed graphs.

Examples

open all close all

Basic Examples (1)

Contract vertices of a graph:

Wolfram Language code: VertexContract[[image], {1, 2}]

Scope (7)

VertexContract works with undirected graphs:

Wolfram Language code: VertexContract[[image], {1, 2}]

Directed graphs:

Wolfram Language code: VertexContract[[image], {1, 2}]

Multigraphs:

Wolfram Language code: VertexContract[[image], {1, 2}]

Mixed graphs:

Wolfram Language code: VertexContract[[image], {1, 2}]

Use rules to specify the graph:

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

Use patterns to specify a set of vertices:

Wolfram Language code: VertexContract[[image], _ ? ((# < 4)&)]

VertexContract works with large graphs:

Wolfram Language code: GridGraph[{10, 10, 10, 10}];

Wolfram Language code: VertexCount[VertexContract[%, {1, 2}]]//Timing

Applications (2)

Find the connectivity between communities in a network:

Wolfram Language code: g = [image];

Wolfram Language code: com = FindGraphCommunities[g]

Condensation graph:

Wolfram Language code: VertexContract[g, com]

List all possible vertex identifications between two RNA tree models to model RNA bonding:

Wolfram Language code: g = [image];

Wolfram Language code: gs = VertexContract[g, #]& /@ Flatten[Table[{i, j}, {i, Range[4]}, {j, Range[5, 7]}], 1]

Gather all isomorphic graphs into groups and show non-isomorphic trees:

Wolfram Language code: gc = GatherBy[Map[{#, CanonicalGraph[#]}&, gs], Last];

Wolfram Language code: First /@ (First /@ #& /@ gc)

Properties & Relations (2)

Using VertexReplace to contract vertices:

Wolfram Language code: g = CycleGraph[5];

Wolfram Language code: VertexContract[g, {1, 2}]

Wolfram Language code: SimpleGraph@VertexReplace[g, 2 -> 1]

EdgeContract can be computed using VertexContract:

Wolfram Language code: g = WheelGraph[7];

Wolfram Language code: EdgeContract[g, {12, 34}]

Wolfram Language code: VertexContract[g, Flatten[List@@@{12, 34}]]

Top