Main Content

transreduction

Transitive reduction

所有的页面崩溃

Syntax

H = transreduction(G)

Description

example

H= transreduction(G)returns thetransitive reductionof graphGas a new graph,H. The nodes inHare the same as those inG, butH有不同的边缘。Hcontains the fewest number of edges such that if there is a path from nodeito nodejinG, then there is also a path from nodeito nodejinH.

Examples

collapse all

Open Live Script

Create and plot a complete graph of order four.

G = digraph([1 1 1 2 2 2 3 3 3 4 4 4],[2 3 4 1 3 4 1 2 4 1 2 3]); plot(G)

Figure contains an axes object. The axes object contains an object of type graphplot.

Find the transitive reduction and plot the resulting graph. Since the reachability in a complete graph is extensive, there are theoretically several possible transitive reductions, as any cycle through the four nodes is a candidate.

H = transreduction(G); plot(H)

Figure contains an axes object. The axes object contains an object of type graphplot.

Two graphs with the same reachability also have the same transitive reduction. Therefore, any cycle of four nodes produces the same transitive reduction asH.

Create a directed graph that contains a different four node cycle: (1,3,4,2,1).

G1 = digraph([1 3 4 2],[3 4 2 1]); plot(G1)

Figure contains an axes object. The axes object contains an object of type graphplot.

Find the transitive reduction ofG1. The cycle inG1is reordered so that the transitive reductionsHandH1have the same cycle, (1,2,3,4,1).

H1 = transreduction(G1); plot(H1)

Figure contains an axes object. The axes object contains an object of type graphplot.

Open Live Script

Create and plot a directed acyclic graph.

s = [1 1 1 1 2 3 3 4]; t = [2 3 4 5 4 4 5 5]; G = digraph(s,t); plot(G)

Figure contains an axes object. The axes object contains an object of type graphplot.

Confirm thatGdoes not contain any cycles.

tf = isdag (G)
tf =logical1

Find the transitive reduction of the graph. Since the graph does not contain cycles, the transitive reduction is unique and is a subgraph ofG.

H = transreduction(G); plot(H)

Figure contains an axes object. The axes object contains an object of type graphplot.

Input Arguments

collapse all

Input graph, specified as adigraphobject. Usedigraph创建一个有向图object.

Example:G = digraph([1 2],[2 3])

Output Arguments

collapse all

Transitive reduction ofG,返回digraphobject. The tableG.Nodesis copied toH, but any properties inG.Edgesare dropped.Hmight contain new edges not present inG.

Hcontains the fewest number of edges that still preserve the reachability of graphG. In other words,transclosure(H)is the same astransclosure(G).

Ifisdag(G)istrue, thenHis unique and is a subgraph ofG.

More About

collapse all

Transitive Reduction

The transitive reduction of graphGis the graph with the fewest edges that still shares the same reachability asG. Therefore, of all the graphs that have the same transitive closure asG, the transitive reduction is the one with the fewest edges. If two directed graphs have the same transitive closure, they also have the same transitive reduction.

Version History

Introduced in R2015b

See Also

||