TEORIA GRAFÓW

OFICJALNA ŚCIĄGAWKA z MATEMATYKI DYSKRETNEJ cz. 2

2

)

1

(

2

−

=













n

n

n

;

2

)!

1

(

−

n

; n

n

−

2

;

E

i

d

V

i

2

)

(

=

∑

∈

;

A

i

d

i

d

V

i

V

i

=

=

∑

∑

∈

+

∈

−

)

(

)

(

; (n

−

1)! ;

d(i) = | V(i) |, gdzie V(i) = { j

∈

V : {i, j}

∈

E }; d

M

(i) = | V

M

(i) |, gdzie V

M

(i) = { j

∈

M : {i, j}

∈

E };

d

+

(i) = | V

+

(i) |, gdzie V

+

(i) = { j

∈

V : (i, j)

∈

A }; d

−

(i) = | V

−

(i) |, gdzie V

−

(i) = { j

∈

V : (j, i)

∈

A };

)

(i

d

M

+

= |

)

(i

V

M

+

|, gdzie

)

(i

V

M

+

= { j

∈

M : (i, j)

∈

A };

)

(i

d

M

−

= |

)

(i

V

M

−

|, gdzie

)

(i

V

M

−

= { j

∈

M : {j, i}

∈

A };

I(G) = [ a

ij

]

i =1, ..., n , j =1, ..., m

, gdzie







∈

=

przypadku

przeciwnym

w

0

jesli

1

j

ij

e

i

a

;

I(D) = [ a

ij

]

i =1, ..., n , j =1, ..., m

, gdzie











=

=

−

=

przypadku

przeciwnym

w

0

)

,

(

jesli

1

)

,

(

jesli

1

k

i

a

i

k

a

a

j

j

ij

;

B(G) = [ b

ij

]

i =1, ..., n , j =1, ..., n

, gdzie







∈

=

=

przypadku

przeciwnym

w

0

}

,

{

jesli

1

E

j

i

b

b

ji

ij

;

B(D) = [ b

ij

]

i =1, ..., n , j =1, ..., n

, gdzie







∈

=

przypadku

przeciwnym

w

0

)

,

(

jesli

1

A

j

i

b

ij

;

2

)

1

)(

(

)

(

+

−

−

≤

≤

−

k

n

k

n

m

k

n

; n – m + f = k + 1; m

≤

3n – 6; m

≤

2n – 4;

d(v) + d(w)

≥

n; d(v)

≥

2

n

; m

≥

2

2

)

2

)(

1

(

+

−

−

n

n

;

∀

i <

2

n

: a

i

≤

i ⇒ a

n

−

i

≥

n – i ;

1

2

)

(

)

(

−

≥

+

n

w

d

v

d

;

2

)

(

n

v

d

≥

+

i

2

)

(

n

v

d

≥

−

;

C =

1

e

C

⊗

2

e

C

⊗

...

⊗

k

e

C

, gdzie

{

}

k

e

e ...,

,

1

= C \ T ;

κ

(G)

≤

λ

(G);

∑

∑

−

+

∈

∈

−

=

)

(

)

(

)

,

(

)

,

(

)

(

s

V

u

s

V

u

s

u

f

u

s

f

f

W

; P

U

= A

∩

( U

×

( V \ U) ) = { (u, v)

∈

A : u

∈

U, v

∈

V \ U };

f (U, V \ U) =

∑

∈

U

P

v

u

v

u

f

)

,

(

)

,

(

; W(f ) = f (U, V \ U)

−

f (V \ U, U); C(P

U

) =

∑

∈

U

P

v

u

v

u

c

)

,

(

)

,

(

; W(f )

≤

C(P

U

);

α

(G) +

τ

(G) = | V |;

ν

(G) +

ρ

(G) = | V |;

ν

(G)

≤

τ

(G);

α

(G)

≤

ρ

(G);

∀

S

⊆

V

1

: | N(S) |

≥

| S | ;

4

1

2

2

1

)

(

+

+

≤

m

G

χ

;

(jedyna ściągawka, którą wolno mieć na egzaminie, ale nie wolno jej używać na kolokwium poprawkowym)