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)