Discrete Mathematics

200

DISCRETE

MATHEMATICS·------------------------

Note that this algorithm computes a transitive closure in 0 ( V ( E + V)) time, where E represents the

number

of

non-empty bits in the adjacency matrix.

DFN:

I

Low: 1

Low:

I

DFN:3

Low:2

Low: 2

DFN:7

Low:4

Let us try this out on the previous example.

DFN:4

The algorithm will print out the following regions in sequence:

Biconnected component: 8, 7, 9, 6

Biconnected component: 6, 4

Biconnected component: 4, 5, 2

Biconnected component:

2,

3, I

DFN:6

DFN: 5

Low: 4

Note that the second region is not really biconnected, although it satisfies the definition. It is what

we

call a bridge, and can be