Dokazy Flashcards
(41 cards)
1
Q
cesta <=> sled
A
2
Q
most <=> neleži na kružnici
A
3
Q
n-c≤m≤1/2(n-c)(n-c+1)
A
4
Q
rad(G)≤diam(G)≤2rad(G)
A
5
Q
Matica susednosti (3 odražky)
A
6
Q
Graf je centrom nejakeho suvisleho grafu
A
7
Q
Centrom stromu je K1 alebo K2
A
8
Q
Graf je periferiou suvisleho grafu akk ecc =1 alebo≠1
A
9
Q
Kappa ≤ delta
A
10
Q
Kappa’ < delta
A
11
Q
Kappa ≤ kappa’
A
12
Q
pre p,q,r vieme najst graf s kappa,kappa’,delta
A
13
Q
2-suvisly <=> 2 vrcholy ležia na spol kružnici
A
14
Q
Hnusna veta o postupnosti a suvislosti
A
15
Q
Bloky su disjunktne alebo artikulacia
A
16
Q
S je NZ , V-S je Pokrytie
A
17
Q
Alfa + beta = n
A
18
Q
alfa ≥ 1/1+deg
A
19
Q
Alfa’ + beta’ =n
A
20
Q
Sparenie je najväčšie <=> neobsahuje M-rozsir cestu
A
21
Q
Hallova veta
A
22
Q
M=K tak m je max a k je min
A
23
Q
Bip alfa’ = beta
A
24
Q
Erdos sekeres r(k,l)
A
25
R(k,l) odhad cez kombinacne
26
Dosledok r(k,l) cez kombinacne
27
Turanov graf ma najviac hran z k-part
28
Graf neobsahujuci kliku k+1 ma menej ako turanov
29
Farbenie je 2 <=> neobs neparnu kruznicu
30
Farbenie a bloky
31
Farbenie a min stupen podgrafu
32
Farbenie, 1+ delta
33
Farbenie brooks
34
Farbenie a nezavislost
35
Farbenie x+x, xx, nordhaus
36
Hranove farbenie, kompletny graf
37
Hranove farbenie, bipartitny
38
Chromaticky polynom rekurzia
39
Turnaj obsah hamiltonovsku drahu
40
Turnaj obsahuje cyklus, tak aj cyklus 3
41
Turnaj je silne suvisly, potom cykly 3 až n
