# Difference between revisions of "Talk:Maximal elements algorithms"

From Electowiki

m |
|||

Line 1: | Line 1: | ||

As far as I know, Kosaraju's algorithm finds the "strongly connected components" of a directed graph. But the Schwartz set is not identical to the "strongly connected components", but to the "communicating classes" of a directed graph. | As far as I know, Kosaraju's algorithm finds the "strongly connected components" of a directed graph. But the Schwartz set is not identical to the "strongly connected components", but to the "communicating classes" of a directed graph. | ||

− | A communicating class CC is a set of knots with the following properties: | + | A strongly connected component SCC is a set of knots with the following property: |

+ | |||

+ | # If knot A is in SCC and knot B is in SCC \ {A}, then there is a directed path from knot A to knot B, that consists only of knots in SCC, and a directed path from knot B to knot A, that consists only of knots in SCC. | ||

+ | |||

+ | On the other side, a communicating class CC is a set of knots with the following properties: | ||

# If knot A is in CC and knot B is in CC \ {A}, then there is a directed path from knot A to knot B and a directed path from knot B to knot A. | # If knot A is in CC and knot B is in CC \ {A}, then there is a directed path from knot A to knot B and a directed path from knot B to knot A. | ||

− | # If knot A is in CC and there is a directed path from knot B to knot A, then knot B is | + | # If knot A is in CC and there is a directed path from knot B to knot A, then also knot B is in CC. |

[[User:MarkusSchulze|Markus Schulze]] 04:44, 27 October 2006 (PDT) | [[User:MarkusSchulze|Markus Schulze]] 04:44, 27 October 2006 (PDT) |

## Latest revision as of 02:43, 28 October 2006

As far as I know, Kosaraju's algorithm finds the "strongly connected components" of a directed graph. But the Schwartz set is not identical to the "strongly connected components", but to the "communicating classes" of a directed graph.

A strongly connected component SCC is a set of knots with the following property:

- If knot A is in SCC and knot B is in SCC \ {A}, then there is a directed path from knot A to knot B, that consists only of knots in SCC, and a directed path from knot B to knot A, that consists only of knots in SCC.

On the other side, a communicating class CC is a set of knots with the following properties:

- If knot A is in CC and knot B is in CC \ {A}, then there is a directed path from knot A to knot B and a directed path from knot B to knot A.
- If knot A is in CC and there is a directed path from knot B to knot A, then also knot B is in CC.

Markus Schulze 04:44, 27 October 2006 (PDT)