4003137
| 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) |
Want to create your own Flashcards for free with GoConqr? Learn more.