Definice ze 4. přednášky (grafy)

秀一 幽遊
Flashcards by 秀一 幽遊, updated more than 1 year ago
秀一 幽遊
Created by 秀一 幽遊 over 5 years ago
39
0

Description

Definice ze 4. přednášky (grafy) MI-PAR

Resource summary

Question Answer
Druhy propojovacích sítí (obecně) - Sdílené - sběrnice - Přepínané - uzly připoj. k přepínačům – Přímé – každý přepínač je připojen k 1 PE – Nepřímé – některé přepínače jsou připojiny pouze k jiným přepínačům – Pravidelné - tvoří zobecnitelný graf – Nepravidelné - náhodný graf
Podgraf Podgraf grafu \(G\), \(H\subset G: \quad V(H)\subset V(G)\) a \( E(H)\subset E(G)\)
Indukovaný podgraf Indukovaný podgraf G \(:\quad \)maximální podgraf s \(V(H). \)
Faktor grafu Faktor grafu G: \( V(H) = V(G) \)
Klika \(U_k\) Klika \(U_k = \) úplný podgraf o k uzlech
Stupeň uzlu Množina stupňů grafu Maximální stupeň Minimální stupeň k-regulární graf Řídký graf Hustý graf - Stupeň uzlu u :\( \deg_G(u) = \#\) sousedů uzlu u. - Množina stupňů grafu G \(\deg(G)=\{\deg_G(u); u\in V(G)\}\). – Maximální stupeň grafu G \( \triangle(G)=\max(\deg(G))\). – Minimální stupeň grafu G:\( \delta(G)=\min(\deg(G))\). – k-regulární graf G: \( \triangle(G)=\delta(G)=k\). – Řídký graf \(|E(G)|=O(|V(G)|) \) (stupně uzlů jsou omezeny konstantou). – Hustý graf \(|E(G)|=\omega(|V(G)|)\) (stupně uzlů jsou rostoucí funkcí \( |V(G)| \) )
Automorfismus Každé izomorfní zobrazení G na sebe sama
Kartézský součin \( G=G_1\times G_2 \) \[ V(G)=\{(x,y); x\in V(G_1), y\in V(G_2)\} \]\[ E(G)=\{\langle (x_1,y),(x_2,y)\rangle;\langle x_1,x_2\rangle\in E(G_1)\} \] \[ \cup \{\langle (x,y_1),(x,y_2)\rangle; \langle y_1,y_2\rangle\in E(G_2)\} \] komutativní a asociativní operace
Uzlově a hranově (částečně) symetrický graf – Uzlově symetrický graf: \(\forall\ u_1,u_2\in V(G) \exists \) automorfizmus f takový, že \( f(u_1)=u_2\). = graf vypadá ze všech uzlů stejně – Hranově symetrický graf: \(\forall\ e_1=\langle u_1,v_1\rangle,e_2=\langle u_2,v_2\rangle\in E(G) \exists \) automorfizmus f takový, že \( f(e_1)=e_2\). (Musí platit i pro \(e_2=\langle v_1,u_1\rangle \).) – Částečně hranově symetrický graf: \(\exists\) rozklad \( E(G)=E_1\cup\ldots\cup E_r \) pro \( r\geq 2\) takový, že \( \forall\ 1\leq j\leq r\ \forall\ e_1,e_2\in E_j\ \exists\) automorfizmus f takový, že \(f(e_1)=e_2\). = podmnož. hran, kt. jsou hr. symetrické
Věty o symetrii (5) (1) Jsou-li \(G_1\) a \(G_2\) uzl. sym., pak \( G=G_1\times G_2\) je také uzl.~sym. (2) Je-li G hranově symetrický, pak \(G^k\) je též hranově symetrický pro každé \(k\geq 2\). (3) Každý hranově symetrický graf je uzlově symetrický. (4) Každý uzlově symetrický graf je regulární. (5) Cykly \(K_k\) a kliky \(U_k\) jsou hranově symetrické.
Délka cesty Vzdálenost uzlů u, v Průměrná vzdálenost v N-uzlovém G – Délka cesty \(P(u,v): len(P(u,v)) \) = # hran v \(P(u,v)\). (v cestě se uzly neopakují) – Vzdálenost uzlů u a v: \(dist_G(u,v)\) = délka nejkratší \(P(u,v)\). – Průměrná vzdálenost v N-uzlovém G: \[ \overline { dist(G)} =\frac{1}{N(N-1)}\sum_{{u,v}\atop {u\not= v}} dist_G(u,v). \]
Excentricita Průměr grafu Poloměr grafu Uzlově disjunktní cesty Hranově disjunktní cesty – Excentricita uzlu u: \( exc(u)=\max_{v\in V(G)} dist_G(u,v)\). – Průměr grafu G: \( diam(G)=\max_{u,v} dist_G(u,v)=\max_u exc(u) \). – Poloměr grafu G: \( r(G)=\min_u exc(u)\). – Uzlově disjunktní cesty: \( V(P_1(u,v))\cap V(P_2(x,y))=\{u,v\}\cap\{x,y\}\) – Hranově disjunktní cesty: \( E(P_1(u,v))\cap E(P_2(x,y))=\emptyset \)
Uzlový (hranový) řez množina uzlů (hran), jejichž odebráním se rozpojí graf
Uzlová (hranová) souvislost grafu G \(\kappa(G) (\lambda(G)) \) = velikost minimálního uzlového (hranového) řezu.
Co platí o hranové, uzlové souvislosti a minimálním stupni grafu? \(\kappa(G) \leq \lambda(G) \leq \delta(G)\)
Co platí pro k-souvislý (hranově k-souvislý) graf? \( \kappa(G)=k (\lambda(G)=k) \)
Kdy je graf optimálně souvislý? \(\kappa(G)=\lambda(G)=\delta(G)\)
Mengerova věta Mezi libovolnými 2 uzly G \(\exists\) nejméně \(\kappa(G)\) uzlově disjunktních cest a nejméně \(\lambda(G)\) hranově disjunktních cest.
(Hranová) bisekční šířka (Hranová) bisekční šířka grafu G, \( biw_e (G) \): velikost nejmenšího hranového řezu grafu G na 2 poloviny - totéž uzlová bisekční šířka, nejvýše \( \lceil{V/2}\rceil\) uzlů
Bipartitní a vyvážený bipartitní graf bipartitní graf = graf, který lze obarvit 2 barvami, tak, že sousední uzly mají různé barvy vyvážený bipartitní graf = počet barev je stejný (pro lichý počet uzlů se mohou o 1 lišit)
Show full summary Hide full summary

Similar

Definice z 2. přednášky
秀一 幽遊
Definice ze 4. přednášky (topologie)
秀一 幽遊
Definice z 6. přednášky
秀一 幽遊
Definice z 5. přednášky
秀一 幽遊
Grafy II.
Michal Roch
FITNESS
Montse Em
Statistics - topic 2
David Klingenber
Algebra
秀一 幽遊
sport
Saki Kuwae
Fundamentos
luis lopez
1. okruh
David Klingenber