PAR3 Flashcards
faktor H grafu G
V(H) = V(G)
Inkrementalne skalovatelna topologie
dej mi velikost N a ja ti vytvorim kruznici – definovana pro vsechny N
klika Uk
uplny graf o k uzlech
delka cesty P(u;v)
len(P(u;v)) = počet hran v P(u;v)
Bipartitni graf a kdy je vyvazeny
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
podgraf H grafu G
V(H) [ V(G) a E(H) [ E(G)
(Hranova) bisekcni sirka grafu G
velikost nejmensiho hranoveho rezu grafu G na 2 poloviny (stejne velike)
minimalni stupeň grafu G
δ(G) = min(deg(G))
uzlove disjunktni cesty
V (P1(u; v)) ∩ V (P2(x; y)) = {u; v} ∩ {x; y}
prumer grafu G diam(G)
vezmu vsechny mozne dvojice a ta s nejdelsi cestou je prumer ; maxu;v distG(u; v)
Castecne hranove symetricky graf
∃ rozklad E(G) = E1 ∪ . . . ∪ Er pror≥2takovy; ze∀1≤j≤r∀e1;e2 ∈Ej ∃automorfizmusf takovy; ze f(e1) = e2.
Efektivne skalovatelna topologie
pro konst k>0 lze (N+k)-uzlovou instanci konstruovat z N-uzlove instance tak; ze počet odebranych hran je O(k)
Hyperstrom HT(m;k;h)
(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
excentricita uzlu u
nejdelsi vzdalenost do nejakeho uzlu z uzlu u ;maxv∈V (G) distG(u; v)
Topologie
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í)
uzlove (hranove) k-souvisly graf
κ(G) = k nebo (hranove λ(G) = k)
maximalni stupeň grafu G
△(G) = max(deg(G))
vzdalenost uzlu u a v
dist(u;v) = delka nejkratsi P(u;v)
izomorfismus G a H
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
mnozina stupnu grafu G – deg(G)
deg(G)={degG(u);u∈V(G)}
hranove disjunktni cesty
E(P1(u; v)) ∩ E(P2(x; y)) = ∅
Husty graf
|E(G)| = ω(|V (G)|) (stupne uzlu jsou rostouci funkc ́ı |V (G)|)
optimalni souvislost
κ(G) = λ(G) = δ(G)
stupeň uzlu deg(u)
počet sousedu uzlu u
indukovany podgraf H v G
maximalni podgraf s V(H)
uzlova(hranova) souvislost grafu G κ(G) (λ(G))
velikost minimalniho uzloveho (hranoveho) rezu
Hierarchicky rekurzivni topologie
instance nizsich dimenzi jsou podgrafy instanci vyssich dimenzi – velky graf obsahuje tu samou strukturu v mensim
Ridky graf
|E(G)| = O(|V (G)|) (stupne uzlu jsou omezeny konstantou)
Castecne skalovatelna topologie
definovana pro nektere (napr. sude), ale pro nekonecno N
sousedni uzly u a v
hrana
Uzlove symetricky graf
∀ u1; u2 ∈ V (G) ∃ automorfizmus f takov ́y; ˇze f(u1) = u2
polomer grafu r(G)
minu exc(u)
K-regularni graf G
△(G) = δ(G) = k
uzlovy(hranovy) rez
mnozina uzlu (hran); jejichz odebiranim se rozpoji graf
prumerna vzdalenost v N-uzlovem G
dist(G) = 1/N(N-1)SUMAu;v
Hranove symetricky graf
∀ e1 = ⟨u1; v1⟩; e2 = ⟨u2; v2⟩ ∈ E(G) ∃ automorfizmus f takov ́y; ˇze f(e1) = e2
Kartezsky soucin G = G1 x G2
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)}
vlastnosti toroidu
definice zabaleneho motylka
definice obycejneho motylka
definice toroidu
definice mrizky
definice hyperkrychle
Prime propojovaci site
kazdy prepinac je pripojen alespon k 1 vypocetnimu uzlu
neprime site
nektere prepinace jsou pripojeny jen k jinym prepinacum
Banyan NxN
exje jedinecna cesta mezi libovolnou dvojici vstup a vystup
K-arni delta MIN
Banyan MINs NxN skladajici se ze stupnu N/k prepinacu k x k.
