background image

Definition 12

Connectedness regarding a digraph

is the connectedness for

the link

(

U

;

τ

)

where

U

is the set of vertices of the digraph and

τ

(

x, y, A

)

means

that there are a path from

x

to

y

in the subgraph restricted to

A

.

Obvious 6

The link space

(

U

;

τ

)

in the above definition is an increasing equiv-

alence.

Definition 13

S

(

U

;

f

)

def

= (

U

; (=)

|

U

f

f

2

f

3

. . .

)

for every digraph

(

U

;

f

)

.

Proposition 4

There is a path from element

a

to element

b

in a set

A

through

a digraph

µ

iff

a S

(

µ

(

A

×

C

A

))

b

.

Proof

If exists a path from

a

to

b

, then

{

b

} ⊆

(

µ

(

A

×

C

A

))

n

{

a

}

where

n

is the

path length. Consequently

{

b

} ⊆

S

(

µ

(

A

×

C

A

))

{

a

}

;

a S

(

µ

(

A

×

C

A

))

b

.

If

a

(

S

(

µ

(

A

×

C

A

)))

b

then exists

n

N

such that

a

(

µ

(

A

×

C

A

))

n

b

.

By definition of composition of binary relations this means that there
exist finite sequence

x

0

. . . x

n

where

x

0

=

a

,

x

n

=

b

for

n

N

and

x

i

(

µ

(

A

×

C

A

))

x

i

+1

for every

i

= 0

, . . . , n

1. That is there is path

from

a

to

b

.

Lemma 1

If

X

Y

=

and

¬

(

X

[

f

]

Y

)

then

¬

(

X

[

f

n

]

Y

)

for every sets

X

,

Y

,

digraph

f

, and natural number

n

.

Proof

For

n

= 0 it is obvious. Let’s prove by induction that it’s true for

n

>

1.

For

n

= 1 it is obvious.

Let it’s true for

n

=

k >

0.

¬

(

X

f

k

+1

Y

)

Y

f

k

+1

X

=

∅ ⇔

Y

f

k

h

f

i

X

=

∅ ⇔ ¬

(

h

f

i

X

f

k

Y

) what is true by induction because

h

f

i

X

Y

=

is equivalent to

¬

(

X

[

f

]

Y

).

Theorem 3

The following statements are equivalent for a digraph

µ

and a set

A

:

1.

A

is connected regarding the digraph

µ

.

2.

S

(

µ

(

A

×

C

A

))

A

×

C

A

.

3.

S

(

µ

(

A

×

C

A

)) =

A

×

C

A

.

4.

A

is connected regarding the connector

[

µ

]

.

5.

X, Y

A

\ {∅}

: (

X

Y

=

A

X

[

µ

]

Y

)

.

7