({{, (RefLink[EdgeCycleMatrix, paclet:ref/EdgeCycleMatrix])[g] 
gives the edge cycle matrix of a graph g.}, {, (RefLink[EdgeCycleMatrix, paclet:ref/EdgeCycleMatrix])[{v->w,…}]
uses rules v->w to specify the graph g. }})

OpenersNotesSection(Spacer1)Details

(RefLink[EdgeCycleMatrix, paclet:ref/EdgeCycleMatrix]) is also known as tie-set matrix or loop matrix.

(RefLink[EdgeCycleMatrix, paclet:ref/EdgeCycleMatrix]) returns a matrix (Subscript[c, ij]) where each row corresponds to a cycle i in the graph g, and each column corresponds to an edge (Subscript[e, j]).

For an undirected graph, (Subscript[c, ij]) is 1 if edge (Subscript[e, j]) is part of cycle i and zero otherwise.

For a directed graph, (Subscript[c, ij]) is 1 if edge (Subscript[e, j]) is part of cycle i, -1 if edge (Subscript[e, j]) in reverse direction is part of cycle i, and zero otherwise.

Edge (Subscript[e, j]) is the edge at position j in (RefLink[EdgeList, paclet:ref/EdgeList])[g], and the index j for an edge (Subscript[e, j]) can be found from (RefLink[EdgeIndex, paclet:ref/EdgeIndex])[g,(Subscript[e, j])].

(RefLink[EdgeCycleMatrix, paclet:ref/EdgeCycleMatrix]) gives a basis for all the cycles in the graph g.

(RefLink[EdgeCycleMatrix, paclet:ref/EdgeCycleMatrix]) works with undirected graphs, directed graphs, multigraphs, and mixed graphs.

OpenersPrimaryExamplesSection(Spacer1)Examples  (12)

OpenersExampleSection0(Spacer1)Basic Examples  (2)

Find the edge cycle matrix of a graph:

g=WheelGraph[4]

EdgeCycleMatrix[g]//MatrixForm

Obtain a cycle basis of a graph:

g=GridGraph[{3,3}];

Pick[EdgeList[g],#,1] & /@ EdgeCycleMatrix[g]

Show the cycles:

HighlightGraph[g,#] & /@ %

OpenersExampleSection1(Spacer1)Scope  (6)

(RefLink[EdgeCycleMatrix, paclet:ref/EdgeCycleMatrix]) works with undirected graphs:

EdgeCycleMatrix[]//MatrixForm

Directed graphs:

EdgeCycleMatrix[]//MatrixForm

Multigraphs:

EdgeCycleMatrix[]//MatrixForm

Mixed graphs:

EdgeCycleMatrix[]//MatrixForm

Use rules to specify the graph:

EdgeCycleMatrix[{1->2,1->4,2->3,2->5,3->6,4->5,4->7,5->6,5->8,6->9,7->8,8->9}]//MatrixForm

(RefLink[EdgeCycleMatrix, paclet:ref/EdgeCycleMatrix]) works with large graphs:

g=GridGraph[{10,10,10}];

EdgeCycleMatrix[g]//Timing

OpenersExampleSection3(Spacer1)Applications  (1)

Obtain a cycle basis of a graph:

g=WheelGraph[4]

basis=Pick[EdgeList[g],#,1] & /@ EdgeCycleMatrix[g]

Build all simple cycles:

addedges[edges_]:=Cases[Tally[Flatten[edges]],{e_,_?OddQ} :>e]

cycles=addedges[Pick[basis,#,1]]& /@ Most[Tuples[{1,0},3]]

OpenersExampleSection4(Spacer1)Properties & Relations  (3)

Use (RefLink[EdgeList, paclet:ref/EdgeList]) to obtain a cycle representation:

g=GridGraph[{3,3}];

Pick[EdgeList[g],#,1] & /@ EdgeCycleMatrix[g]

HighlightGraph[g,#]&/@%

A connected graph with n vertices and m edges:

g=PetersenGraph[];

{n,m}={VertexCount[g],EdgeCount[g]};

Has an edge cycle matrix of dimensions (m-n+1)×m:

Dimensions[EdgeCycleMatrix[g]]=={m-n+1,m}

Compute the (RefLink[EdgeCycleMatrix, paclet:ref/EdgeCycleMatrix]) from the (RefLink[IncidenceMatrix, paclet:ref/IncidenceMatrix]):

g=WheelGraph[4,DirectedEdges->True]

m=IncidenceMatrix[g];

NullSpace[m]//MatrixForm

Compare with (RefLink[EdgeCycleMatrix, paclet:ref/EdgeCycleMatrix]):

EdgeCycleMatrix[g]//MatrixForm

({{DocumentationFooterIconsRelatedFunction.png, ({{See Also}, {(RefLink[FindFundamentalCycles, paclet:ref/FindFundamentalCycles])  ▪  (RefLink[FindCycle, paclet:ref/FindCycle])}})}})

({{DocumentationFooterIconsRelatedGuide.png, ({{Related Guides}, {▪(RefLinkPlain[Paths, Cycles, and Flows, paclet:guide/GraphPathsCyclesAndFlows])}})}})