PAR3

Question 1

faktor H grafu G

Answer 1

V(H) = V(G)

Question 2

Inkrementalne skalovatelna topologie

Answer 2

dej mi velikost N a ja ti vytvorim kruznici – definovana pro vsechny N

Question 3

klika Uk

Answer 3

uplny graf o k uzlech

Question 4

delka cesty P(u;v)

Answer 4

len(P(u;v)) = počet hran v P(u;v)

Question 5

Bipartitni graf a kdy je vyvazeny

Answer 5

graf; jehož množinu vrcholů je možné rozdělit na dvě disjunktní množiny tak; že žádné dva vrcholy ze stejné množiny nejsou spojeny hranou – vyvazen prvku skupin uzlu se stejnou barvouje stejny počet tech barev

Question 6

podgraf H grafu G

Answer 6

V(H) [ V(G) a E(H) [ E(G)

Question 7

(Hranova) bisekcni sirka grafu G

Answer 7

velikost nejmensiho hranoveho rezu grafu G na 2 poloviny (stejne velike)

Question 8

minimalni stupeň grafu G

Answer 8

δ(G) = min(deg(G))

Question 9

uzlove disjunktni cesty

Answer 9

V (P1(u; v)) ∩ V (P2(x; y)) = {u; v} ∩ {x; y}

Question 10

prumer grafu G diam(G)

Answer 10

vezmu vsechny mozne dvojice a ta s nejdelsi cestou je prumer ; maxu;v distG(u; v)

Question 11

Castecne hranove symetricky graf

Answer 11

∃ rozklad E(G) = E1 ∪ . . . ∪ Er pror≥2takovy; ze∀1≤j≤r∀e1;e2 ∈Ej ∃automorfizmusf takovy; ze f(e1) = e2.

Question 12

Efektivne skalovatelna topologie

Answer 12

pro konst k>0 lze (N+k)-uzlovou instanci konstruovat z N-uzlove instance tak; ze počet odebranych hran je O(k)

Question 13

Hyperstrom HT(m;k;h)

Answer 13

(m;k)-hyperstrom je stromovy graf; ve kterem ma každý uzel m rodicu a k potomku (stupeň je m+k); krome uzlu : 1)bez rodicu = koreny 2)bez potomku = listy

Question 14

excentricita uzlu u

Answer 14

nejdelsi vzdalenost do nejakeho uzlu z uzlu u ;maxv∈V (G) distG(u; v)

Question 15

Topologie

Answer 15

mnozina grafu; jejichz velikost a struktura je definovana parametry(hodnotami dimenzi) – mnozina všech kruznic napr (1 dimenze a počet uzlu – napr. Stejny stupeň mají)

Question 16

uzlove (hranove) k-souvisly graf

Answer 16

κ(G) = k nebo (hranove λ(G) = k)

Question 17

maximalni stupeň grafu G

Answer 17

△(G) = max(deg(G))

Question 18

vzdalenost uzlu u a v

Answer 18

dist(u;v) = delka nejkratsi P(u;v)

Question 19

izomorfismus G a H

Answer 19

pokud existuje bijekce fi:V(G) → V(H); tak ze pro kazde dva sousedni vrcholy u;v z G musí byt sousedni i fi(u);fi(v) v grafu H

Question 20

mnozina stupnu grafu G – deg(G)

Answer 20

deg(G)={degG(u);u∈V(G)}

Question 21

hranove disjunktni cesty

Answer 21

E(P1(u; v)) ∩ E(P2(x; y)) = ∅

Question 22

Husty graf

Answer 22

|E(G)| = ω(|V (G)|) (stupne uzlu jsou rostouci funkc ́ı |V (G)|)

Question 23

optimalni souvislost

Answer 23

κ(G) = λ(G) = δ(G)

Question 24

stupeň uzlu deg(u)

Answer 24

počet sousedu uzlu u

Question 25

indukovany podgraf H v G

Answer 25

maximalni podgraf s V(H)

Question 26

uzlova(hranova) souvislost grafu G κ(G) (λ(G))

Answer 26

velikost minimalniho uzloveho (hranoveho) rezu

Question 27

Hierarchicky rekurzivni topologie

Answer 27

instance nizsich dimenzi jsou podgrafy instanci vyssich dimenzi – velky graf obsahuje tu samou strukturu v mensim

Question 28

Ridky graf

Answer 28

|E(G)| = O(|V (G)|) (stupne uzlu jsou omezeny konstantou)

Question 29

Castecne skalovatelna topologie

Answer 29

definovana pro nektere (napr. sude), ale pro nekonecno N

Question 30

sousedni uzly u a v

Answer 30

hrana

Question 31

Uzlove symetricky graf

Answer 31

∀ u1; u2 ∈ V (G) ∃ automorfizmus f takov ́y; ˇze f(u1) = u2

Question 32

polomer grafu r(G)

Answer 32

minu exc(u)

Question 33

K-regularni graf G

Answer 33

△(G) = δ(G) = k

Question 34

uzlovy(hranovy) rez

Answer 34

mnozina uzlu (hran); jejichz odebiranim se rozpoji graf

Question 35

prumerna vzdalenost v N-uzlovem G

Answer 35

dist(G) = 1/N(N-1)SUMAu;v

Question 36

Hranove symetricky graf

Answer 36

∀ e1 = ⟨u1; v1⟩; e2 = ⟨u2; v2⟩ ∈ E(G) ∃ automorfizmus f takov ́y; ˇze f(e1) = e2

Question 37

Kartezsky soucin G = G1 x G2

Answer 37

V (G) = {(x; y); x ∈ V (G1); y ∈ V (G2)} E(G) = {⟨(x1; y); (x2; y)⟩; ⟨x1; x2⟩ ∈ E(G1)} ∪{⟨(x; y1); (x; y2)⟩; ⟨y1; y2⟩ ∈ E(G2)}

Question 38

vlastnosti toroidu

Answer 38

Question 39

definice zabaleneho motylka

Answer 39

Question 40

definice obycejneho motylka

Answer 40

Question 41

definice toroidu

Answer 41

Question 42

definice mrizky

Answer 42

Question 43

definice hyperkrychle

Answer 43

Question 44

Prime propojovaci site

Answer 44

kazdy prepinac je pripojen alespon k 1 vypocetnimu uzlu

Question 45

neprime site

Answer 45

nektere prepinace jsou pripojeny jen k jinym prepinacum

Question 46

Banyan NxN

Answer 46

exje jedinecna cesta mezi libovolnou dvojici vstup a vystup

Question 47

K-arni delta MIN

Answer 47

Banyan MINs NxN skladajici se ze stupnu N/k prepinacu k x k.