# transreduction

Transitive reduction

## Syntax

## Description

returns the transitive reduction of
graph `H`

= transreduction(`G`

)`G`

as a new graph, `H`

. The nodes in
`H`

are the same as those in `G`

, but
`H`

has different edges. `H`

contains the
fewest number of edges such that if there is a path from node `i`

to node `j`

in `G`

, then there is also a path from
node `i`

to node `j`

in
`H`

.

## Examples

### Transitive Reduction of Complete Graph

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)

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)

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

.

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)

Find the transitive reduction of `G1`

. The cycle in `G1`

is reordered so that the transitive reductions `H`

and `H1`

have the same cycle, (1,2,3,4,1).

H1 = transreduction(G1); plot(H1)

### Unique Transitive Reduction

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)

Confirm that `G`

does not contain any cycles.

tf = isdag(G)

`tf = `*logical*
1

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

.

H = transreduction(G); plot(H)

## Input Arguments

`G`

— Input graph

`digraph`

object

Input graph, specified as a `digraph`

object. Use `digraph`

to create a directed graph object.

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

## Output Arguments

`H`

— Transitive reduction of `G`

`digraph`

object

Transitive reduction of `G`

, returned as a
`digraph`

object. The table `G.Nodes`

is copied to `H`

, but any properties in
`G.Edges`

are dropped. `H`

might
contain new edges not present in `G`

.

`H`

contains the fewest number of edges that still
preserve the reachability of graph `G`

. In other words,
`transclosure(H)`

is the same as
`transclosure(G)`

.

If `isdag(G)`

is `true`

, then
`H`

is unique and is a subgraph of
`G`

.

## More About

### Transitive Reduction

The transitive reduction of graph `G`

is the
graph with the fewest edges that still shares the same reachability as
`G`

. Therefore, of all the graphs that have the same transitive
closure as `G`

, 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

## Open Example

You have a modified version of this example. Do you want to open this example with your edits?

## MATLAB Command

You clicked a link that corresponds to this MATLAB command:

Run the command by entering it in the MATLAB Command Window. Web browsers do not support MATLAB commands.

Select a Web Site

Choose a web site to get translated content where available and see local events and offers. Based on your location, we recommend that you select: .

You can also select a web site from the following list:

## How to Get Best Site Performance

Select the China site (in Chinese or English) for best site performance. Other MathWorks country sites are not optimized for visits from your location.

### Americas

- América Latina (Español)
- Canada (English)
- United States (English)

### Europe

- Belgium (English)
- Denmark (English)
- Deutschland (Deutsch)
- España (Español)
- Finland (English)
- France (Français)
- Ireland (English)
- Italia (Italiano)
- Luxembourg (English)

- Netherlands (English)
- Norway (English)
- Österreich (Deutsch)
- Portugal (English)
- Sweden (English)
- Switzerland
- United Kingdom (English)