TEORIA GRAFÓW

OFICJALNA ŚCIĄGAWKA z MATEMATYKI DYSKRETNEJ cz. 2

 n

n( n − )

1

( n − )

1 !

−

+

  =

;

; n n−2 ; ∑ d i

( ) = 2 E ; ∑ d i

( ) = ∑ d i

( ) = A ; ( n−1)! ;

 2

2

2

i V

∈

i V

∈

i V

∈

d( i) = | V( i) |, gdzie V( i) = { j∈ V : { i, j}∈ E }; dM ( i) = | VM ( i) |, gdzie VM ( 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 }; d + ( i) = | V + ( i) |, gdzie V + ( i) = { j∈ M : ( i, j) ∈ A }; d − ( i) = | V − ( i) |, gdzie V − ( i) = { j∈ M : { j, i}∈ A }; M

M

M

M

M

M

1

jesli i ∈ e

I( G) = [ a

a

;

ij =

j

ij ] i =1, ..., n , j =1, ..., m , gdzie

0 w przeciwnym przypadku

−1 jesli a j = ( k, i)



I( D) = [ a

a

;

ij =

1

jesli

a j =

ij ] i =1, ..., n , j =1, ..., m , gdzie



( i, k)

 0

w przeciwnym przypadku

1

jesli { i, }

j ∈ E

B( G) = [ b

b

;

ij = b ji =

ij ] i =1, ..., n , j =1, ..., n , gdzie

0 w przeciwnym przypadku

1

jesli ( i, j) ∈ A B( D) = [ b

b

;

ij =

ij ] i =1, ..., n , j =1, ..., n , gdzie

0 w przeciwnym przypadku

( n − k)( n − + ) 1

( n −

k

k) ≤ m ≤

; n – m + f = k + 1; m ≤ 3 n – 6; m ≤ 2 n – 4; 2

n

( n − )

1 ( n − 2)

n

d( v) + d( w) ≥ n; d( v) ≥

; m ≥

+ 2 ; ∀ i < : ai ≤ i ⇒ an− i ≥ n – i ; 2

2

2

+

n

−

n

d ( v) + d ( ) w ≥ 2 n −1 ; d ( v) ≥

i d ( v) ≥

;

2

2

C = C ⊗ C ⊗ ... ⊗ C , gdzie { e ,..., e = C \ T ; κ ( G) ≤ λ( G); 1

k }

1

e

2

e

k

e

W ( f ) = ∑ f ( s, u) − ∑ f ( u, s) ; PU = A ∩ ( U × ( V \ U) ) = { ( u, v) ∈ A : u ∈ U, v ∈ V \ U };

+

−

∈

u V ( s)

∈

u V ( s)

f ( U, V \ U) = ∑ f u ( , v) ; W( f ) = f ( U, V \ U) − f ( V \ U, U); C( PU) = ∑ c u ( , v) ; W( f ) ≤ C( PU); ( u, v ∈

)

( u, v ∈

U

P

)

U

P

α ( G) + τ ( G) = | V |; ν ( G) + ρ ( G) = | V |; ν ( G) ≤ τ ( G); α ( G) ≤ ρ ( G); ∀ S ⊆ V 1: | N( S) | ≥ | S | ; 1

1

χ( G) ≤ + 2 m + ; 2

4

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