Fichas
Definice ze 4. přednášky (grafy)
Fichas del conjunto (20)
- 1Druhy 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 - 2PodgrafPodgraf grafu \(G\), \(H\subset G: \quad V(H)\subset V(G)\) a \( E(H)\subset E(G)\)
- 3Indukovaný podgrafIndukovaný podgraf G \(:\quad \)maximální podgraf s \(V(H).
\) - 4Faktor grafuFaktor grafu G: \( V(H) = V(G) \)
- 5Klika \(U_k\)Klika \(U_k = \) úplný podgraf o k uzlech
- 6Stupeň 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)| \) ) - 7AutomorfismusKaždé izomorfní zobrazení G na sebe sama
- 8Karté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 - 9Uzlově 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é - 10Vě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é. - 11Dé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).
\] - 12Excentricita 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 \) - 13Uzlový (hranový) řezmnožina uzlů (hran), jejichž odebráním se rozpojí graf
- 14Uzlová (hranová) souvislost grafu G\(\kappa(G) (\lambda(G)) \) = velikost minimálního uzlového (hranového) řezu.
- 15Co platí o hranové, uzlové souvislosti a minimálním stupni grafu?\(\kappa(G) \leq \lambda(G) \leq \delta(G)\)
- 16Co platí pro k-souvislý (hranově k-souvislý) graf?\(
\kappa(G)=k (\lambda(G)=k)
\) - 17Kdy je graf optimálně souvislý?\(\kappa(G)=\lambda(G)=\delta(G)\)
- 18Mengerova větaMezi libovolnými 2 uzly G
\(\exists\) nejméně \(\kappa(G)\) uzlově disjunktních cest
a nejméně \(\lambda(G)\) hranově disjunktních cest. - 19(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ů - 20Bipartitní a vyvážený bipartitní grafbipartitní 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)
Información
- Descripción
- Definice ze 4. přednášky (grafy) MI-PAR
- Creado por
- 秀一 幽遊
- Visitas
- 49
- Etiquetas
- Valoración