U spodních mezí komunikačních operací dávejte pozor na to, že se jedná o spodní meze. Neměli byste tedy tvrdit, že nějaká operace trvá tolik a tolik, ale že teoreticky musí trvat nejméně takto. Tzn. upozornit v testu na to, že se jedná o spodní mez, ale že to vůbec neznamená, že takový alogirtmus existuje. Nemusí. Snad to dává smysl, Tvrdík za to bral body.

Určete spodní mez na uzlové zatížení (load) vnoření 3-D mřížky <math>M(z_1, z_2, z_3)</math> do 2-D toroidu <math>K(w_1, w_2)</math>.

★ Bylo ve zkoušce: 2013-01-30, 2013-12-20

Dle mého názoru se jedná o obecnou spodní mez pro load, který vnikne vnořením jednoho grafu do druhého.

Takže jednoduše poměr počtu uzlů grafu vnořovaného (M(…)) k počtu uzlů grafu, do kterého vnořujeme (K(…)).

<math>max(1, \fracz_1_cdot_z_2_cdot_z_3w_1_cdot_w_2) == \text{load}\left(\varphi,\xi\right)\geq\left\lceil \frac{\left|V\left(G\right)\right|}{\left|V\left(H\right)\right|}\right\rceil = \lceil \fracz_1_cdot_z_2_cdot_z_3w_1_cdot_w_2 \rceil</math>

Edit: Kdyz tam das horni celou cast, uz nemusis resit nejaky max(1,…), vzdy ten <math>\lceil zlomek \rceil</math> vyjde minimalne 1

★ Bylo ve zkoušce: 2014-01-13

Stejně jak předchozí, akorát s jinými hodnotami

- Motýlek dimenze n má více uzlů než mřížka M(n,n), proto uzlové zatížení musí být nutně větší nebo rovno poměru počtu uzlů obou grafů:
<math>|V(wBF_n)| = n*2^n
|V(M(n,n))| = n*n
load(\varphi , \xi ) \geq \lceil \frac{|V(wBF_n)|}{|V(M(n,n))|} \rceil = \lceil \frac{n*2^n}{n*n} \rceil = \lceil \frac{2^n}{n} \rceil</math>

<math>\frac{2^n}{n} \geq 2</math>, proto není třeba dělat max(1, load)

Jaká je spodní mez počtu kroků nekombinujícího AAB na Q_n. Všeportový. Odvoďte.

• V jednom kroku lze informovat max. n sousedů (kde n je dimenze)
• Každý uzel musí dostat <math>N-1</math> zpráv, <math>N=2^n</math>
• Spodní mez na počet kroků k obdržení všech zpráv je tedy <math>\lceil \frac{2^n-1}{n} \rceil</math>

Trocha teorie:

• AAB - kolektivní komunikační operace typu vysílání všichni-všem
• Přednáška 2014/10 slide 6 bod 2

Jaká je spodní mez počtu kroků nekombinujícího OAB na Q_n. Všeportový. Odvoďte.

<math>\rho_{OAB}^{SF}\left(Q_{n},s\right)=\text{diam}\left(Q_{n}\right)=n</math>

Zdroj pošle paket všem sousedům a jakýkoli jiný uzel obdržený paket zkopíruje a pošle ho zbývajícím sousedům.

Jaká je spodní mez počtu kroků nekombinujícího OAS na Q_n. Všeportový. Odvoďte.

• Uzel musí postupně kontaktovat všechny ostatní uzly <math>2^{n}-1</math>. Ale za jeden krok může poslat pouze <math>n</math> zpráv. Nejrychleji tedy odešle všechny zprávy v <math>\lceil \frac{2^n-1}{n} \rceil</math> krocích.

<math> \rho_{OAS,k}^{SF}\left(G,s\right)=\left\lceil \frac{\left|V\left(G\right)\right|-1}{k}\right\rceil =\left\lceil \frac{2^{n}-1}{n}\right\rceil </math>

Jaká je spodní mez počtu kroků nekombinujícího AAS na Q_n. Všeportový. Odvoďte.

• Každý uzel <math>2^{n}</math> musí postupně kontaktovat všechny ostatní uzly <math>2^{n-1}</math>. Jedna zpráva z uzlu půjde alespoň dimenzi kroků. V jednom globálním kroku však může každý uzel <math>2^{n}</math> odeslat pouze zprávu do každé dimenze <math>n</math>. <math>(2^{n-1} \cdot 2^{n} \cdot n )/(2^{n} \cdot n)= 2^{n-1}</math>

dotaz: Opravdu je tohle zduvodneni korektni? Vzdyt preci neni pravda, ze ostatnich uzlu je <math>2^{n-1}</math>. Ostatnich uzlu je <math>2^{n}-1</math>. Kdyz vezmu i samotny zdrojovy uzel (ve vzdalenosti 0) je pak prumerna vzdalenost od zdroje k <math>2^{n}</math> cilum <math>n/2</math>. Zpravy potrebuje rozesilat vsech <math>2^{n}</math> uzlu, ale v jednom kroku <math>2^{n}</math> uzlu zaroven odesila zpravy do <math>n</math> smeru. Vyjde to stejne, ale jak rikam, jde mi hlavne o ten duvod, kteremu dost nerozumim. (bliznjan)

Opravdu to má být <math>2^{n-1}</math>? Já si spíš myslím, že když každý krok můžu vyslat maximálně <math>n*2^n</math> zpráv a obdržet celkem potřebuji <math>(2^{n}-1)*2^n</math> zpráv, tak by výsledek měl být spíš <math>¹⁾</math>. Uzlová symetrie je dána vlastnostmi kartézského součinu, který uzlovou symetrii zachovává (a kružnice je uzlově symetrická).

Toroid je hranově symetrický, jen pokud má všechny dimenze stejně veliké - existuje automorfismus rotace. To je dáno tím, že k-ární n-toroid vznikne kartézskou mocninou kružnice o délce n, <math>K_n^k</math>, a kartézská mocnina zachovává i hranovou symetrii (4 přednáška, slide 7, video cca 2:10:00 konrétně pro toroid). Vlastnosti toroidu v PDF 4. přednášky na slajdu č. 30 (MI-PAR 2011/2012).

Dodatek Graf je uzlove symetricky, pokud pro kazde dva uzly existuje automorfismus.
Automorfismus

• je mapovani mnoziny uzlu na mnozinu ulzu,
• zachovava vzdalenosti

Automorfismus rotace o jeden uzel, na K(4) je namapovani uzlu 1→2, 2→3, 3→4, 4→1

Dukaz automorfismu : pro libovolne dva sousedni uzly aplikujem automorfismus a ve vysledku jsou opet sousedni. Proste staci namalovat rotaci kruznice.

Pozor, pokud do písemky napíšete jako zdůvodnění pouze automorfizmus pro K(z) a to, že kartézský součin zachovává uzlovou symetrii, Tvrdík vám to za plný počet neuzná. To, že kartézský součin zachovává automorfismus by se totiž muselo ještě samostatně dokázat. Chce to asi(?) opravdu přímo tam ten příklad automorfismu pro 2D napsat.

pozn.: k tomu dokazování - stačí aspoň ten důkaz naznačit, když uvidí, že víte jak na to, tak vám ty body dá:) Tzn. vyjít z automorfismů jednotlivých kružnic + definice kart. součinu a napsat si automorfismus pro uzly (u1,u2) a (v1,v2) a naznačit tam, že se využije těch automorfismů např. pro K(z1) a K(z2). Viz video z prosemináře.

Automorfismy hyperkrychle Q_n, kolik jich je a vysvětlit proč.

★ Bylo ve zkoušce: 2012-01-24

Viz CZ skripta [2006] str. 59 nebo záznam 7. prosemináře, čas 22:40

Q_n má 2ⁿ uzlů (roven počtu n-bitových binárních řetězců), tudíž máme 2ⁿ možností odkud definovat počátek souřadného systému (tj. do kterého uzlu umístit nulu). Dále máme n! možností, jak uspořádat pořadí dimenzí (tj. který směr bude souřadnice X, Y atd.).

Formálněji řečeno, pro Q_n existuje 2ⁿ přeložení (translací) a každé má n! permutací dimenzí.

• Přeložení je automorfismus <math>\tau_{u \mapsto v}(x)= x\oplus (u \oplus v) = x\oplus y</math>, kde <math>\oplus</math> je bitová nonekvivalence (XOR).
• Počet všech permutací n-bitového řetězce je <math>n!</math>

Celkový počet automorfismů je tedy <math>2^n\cdot {n!}</math>

Zdůvodněte proč nelze na CBT_n pro n > 1 vnořit do Q_n+1 s load = dil = 1.

★ Bylo ve zkoušce: 2012-01-10

Viz přednáška 5 slide 19 nebo CZ skripta [2006] str. 79, EN skripta [2009] str. 59

• počet uzlů <math>CBT_n = 2^{n+1}-1</math>
• počet uzlů <math>Q_{n+1}=2^{n+1}</math>
• jestliže existuje vnoření <math>CBT_n</math> do <math>Q_{n+1}</math> s parametry load=dil=1, pak <math>CBT_n</math> musí být podgraf <math>Q_{n+1}</math>
• protože <math>CBT_n</math> není podgrafem <math>Q_{n+1}</math>, vnoření nemůže existovat.
• <math>Q_{n+1}</math> je vyvážený bipartitni graf ⇒ má stejný počet černých a bílých uzlů
• <math>CBT_n</math> není vyvážený bipartitní graf

<math>\text{|bilych|} = 1+2^2 + 2^4 + … + 2^{2k}</math>

<math>\text{|cernych|} = 2+2^3 + 2^5 + … + 2^{2k+1} = 2 \cdot {\underbrace{(1+ 2^2 + 2^4 + … + 2^{2k})}_{\text{bile}}}</math>

• |bílých| ≠ |černých| ⇒ <math>CBT_n</math> skutečně není vyvážený bipartitní graf.

<math>CBT_n</math> není vyvážený bip. graf a tudíž není podgrafem <math>Q_{n+1}</math>, nelze tedy vnořit <math>CBT_n</math> do <math>Q_{n+1}</math> s load=dil=1.

Nápad na jednodušší důkaz respektive interpretaci:

• <math>CBT_n</math> má <math>2^n</math> listů, což si spočítáme jako rozdíl počtu uzlů <math>CBT_n</math> a <math>CBT_{n-1}</math>, ty listy jsou od kořene ve vdálenosti n.
• Tak si najdeme, kolik uzlů je od libovolného uzlu v takové vzdálenosti v <math>Q_{n+1}</math>
• když použijeme důkaz, který je o něco málo níže, zjistíme, že těch uzlů, na které by se měli namapovat listy je pouze <math>n+1</math>.
• Což pro <math>n=1</math> ukazuje, že vnoření s danými parametry je možné, ale pro vyšší hodnoty už ne.
• Tudíž nemůže být podgraf a nemůže dojít k vnoření s takovými parametry.

Pozn. by Vity: Obecně si namalujte strom, kde v každé úrovni obarvěte uzly jinou barvou a všimněte si, že s každou další úrovní má mnohem více uzlů poslední barvě než té předešlé barvy.

Otazka: Zda se mi, ze se tu operuje s myslenkou: “(Graf A je vyvazeny bipartitni a graf B je nevyvazeny bipartitni) ⇒ graf B nemuze byt podgrafem grafu A”. To mi ale prijde jako blabol (nebo to alespon neplati obecne) - napr. kdyby graf A byl Q3 a graf B by vzniknul z grafu A odsranenim jednoho uzlu.

Trocha teorie:

• CBT - úplný binární strom

Mřížku M(x, y, z) mapujeme do krychle Q_n. Určete n a nalezněte zobrazovací fci [x,y,z] → Q_n, dil = load = 1.

Viz skripta CZ [2006] str. 83 nebo přednáška 5, FIT slide 25, FEL slide 16, EN skripta [2009] strana 64 Lemma 4.24

<math>\normalsize M(x, y, z)</math> je podgrafem hyperkrychle <math>\normalsize Q_n, \:n= \lceil\log{x}\rceil+\lceil\log{y}\rceil+\lceil\log{z}\rceil,\: x, y, z \ge 2</math>. Toto vnoření je optimální pokud <math>\normalsize \lceil\log{x}\rceil+\lceil\log{y}\rceil+\lceil\log{z}\rceil=\lceil\log(x \cdot y \cdot z)\rceil</math>.

Mřížku rozdělíme na kartézský součin <math>\normalsize M(x)\times M(y)\times M(z)</math>. Každou z jednorozměrných mřížek <math>\normalsize M(a)</math> namapujeme do krychle <math>\normalsize Q_{\lceil {\log{a}} \rceil}</math>. Výsledné vnoření je dáno kartézským součinem <math>\normalsize Q_{\lceil {\log{x}} \rceil}\times{Q_{\lceil {\log{y}} \rceil}}\times {Q_{\lceil {\log{z}} \rceil}}</math>, tedy <math>\normalsize n=\lceil\log{x}\rceil+\lceil\log{y}\rceil+\lceil\log{z}\rceil=\lceil\log(x \cdot y \cdot z)\rceil</math>

Mapovací funkce je dána zřetězením mapovacích fcí pro jednorozměrné mřížky. Mapovací funkce jednorozměrné mřížky <math>M(a)</math> do krychle <math>Q_{\lceil{\log{N}\rceil}}</math> je nějaký Grayův kód.

Grayův kód pro vnoření je definování jako: (CZ skripta 79str. lepe)

nechť je b=b_n-1…b₀ bin. číslo pak BRGC (Binary reflected gray code) G_n pro b je definován jako:

1) b_n-1=g_n-1

2) b_i=g_n-1 +₂ … g_i+1 +₂ g_i pro i=n-2, … , 0

V přednáškách 2015/16 přednáška 5, slide 17 je definice BRGC takováto: BRGC zakódování binárního čísla b = b_n-1…b₀ je Gn(b) = g_n−1…g₀, kde

1) <math>g_{n-1}=b_{n-1}</math>,

2) <math>g_{i}=b_{i+1}\mathtt{\,XOR\,}b_{i}</math> pro <math>i=n-2,\ldots,0</math>.

Je tu obecny popis “ze by se to delalo zretezenim mapovacich funkci”, ale chtelo by to dat vsechny tyhle informace dohromady a napsat tu finalni funkci

Dokažte, že do libovolného souvislého grafu G lze vnořit kružnice s n uzly s load = 1, dil ≤ 3.

★ Bylo ve zkoušce: 2012-01-31 4b

Viz přednáška 5 FIT [2012] slide 41, skripta CZ [2006] str. 89 nebo EN [2009] str. 72

1. Najdeme kostru <math>{T_g}</math> (libovolnou) grafu G
2. Procházíme kostru <math>{T_g}</math> do hloubky. Uzly v liché hloubce přidáme při prvním vstupu do daného uzlu, uzly v sudé hloubce přidáme při posledním vstupu do daného uzlu.
   

Load je vždy 1, protože do každého uzlu přidáme max. jeden uzel.
Dilatace je max. 3 a to pouze při přechodu mezi podstromy přes společný kořen. Důkaz, že dilatace nikdy nemůže být horší než 3 je indukcí za použití faktu, že stromy jsou rekurzivní.

Dokažte, že 2D toroid T(z₁, z₂) je výpočetně ekvivalentní s 2D mřížkou M(z₁, z₂).

★ Bylo ve zkoušce: 2012-01-17 a 2015-01-06 (ale obecně pro (z₁, …, z_n))

Viz přednáška 5, FIT slide 27, FEL slide 20 nebo CZ skripta [2006] str. 85

• Sítě G a H jsou kvaziizometrické pokud G může být vnořen do H a naopak s konstantními měřítky vnoření.
• G a H jsou výpočetně ekvivalentní pokud jedna může simulovat druhou s konstantním zpomalením.
• Jsou-li sítě kvaziizometrické, tak jsou i výpočetně ekvivalentní (opačně to neplatí, protože vnoření nemohou postihnout dynamické chování aplikací na cílové síti).

<math>M(z_1,z_2)</math> se vnoří do <math>T(z_1,z_2)</math> s load = dil = ecng = 1, protože <math>M(z_1,z_2)</math> je podgraf <math>T(z_1,z_2)</math>.

<math>T(z_1,z_2)</math> lze vnořit do <math>M(z_1,z_2)</math> s load=1, dil=ecng=2 takto:

1. provedeme dekompozici <math>T(z_1,z_2)</math> na <math>T(z_1)\times{T(z_2)}</math>
2. vnořím dekomponové toroidy <math>T(x)</math> do dekomponovaných mřížek <math>M(x)</math>
3. první polovinu <math>T(x)</math> uzlů namapuji na liché uzly <math>M(x)</math> a druhou polovinu uzlů <math>T(x)</math> namapuji na sudé uzly <math>M(x)</math>.

Na liché uzly mapuji vzestupně a na sudé sestupně.

V podstatě je to stejné jako mapování kružnice na kostru, která je pouze lineárním seznamem. Viz předchozí úkol. Důkaz možnosti vnoření kružnice do libovolného G s load=1, dil⇐3.

Trocha teorie:

• dil - dilatace - maximální délka obrazů zdrojových hran v cílové siti
• load - zatížení - max počet zdrojových vrcholů mapovaných na 1 uzel
• ecng - linkové zahlcení - maximální počet obrazů zdrojových hran procházejících skrz cílové linky, tj. kolik cest vede přes 1 hranu

Kolik udělá permutací nepřímá síť, která má k úrovní, N čísel na vstupu, jeden přepínač 2 × 2.

★ Bylo ve zkoušce: 2012-01-03 a 2015-01-06

Viz přednáška 4, slide 37 FEL; slide 42 FIT; EN skripta [2010] str. 48

V každé úrovni je <math>\normalsize {\Large\lceil} \frac{N}{2} {\Large\rceil}</math> přepínačů. Pokud je N liché, tak poslední nemůže přepínat, takže se použije jen <math>\normalsize {\Large\lfloor} \frac{N}{2} {\Large\rfloor}</math>. Každý přepínač se může vyskytovat v jednom ze dvou stavů – rovně nebo křížem (=, ×). Každá úroveň tedy může vytvořit <math>\normalsize 2^large_lfloor_frac_n_2_large_rfloor</math> permutací. Protože síť má k úrovní, může tedy vytvořit <math>\normalsize {\rm min}\bigl(2^{\lfloor\frac{N}{2}\rfloor k}, N!\bigr)</math> permutací (N! je maximální počet permutací N prvků).

V přednášce 4, slide 39 (2011), je “Přepínače 2 x 2 mohou být v 1 ze 4 stavů”, proč tady se tedy píše jen o dvou stavech?

Po použití druhých dvou stavů (upper/lower broadcast) by již něslo o permutaci. Ztratil bych totiž jeden ze vstupů.

Odvodit průměr na oBFn.

Viz přednáška 4/2014, FIT slide 37

diam(oBFN) = 2*n

Stačilo pouze vysvětlit, že je to vzdálenost mezi nejvzdálenějšími uzly.

Já tam (za 2 body) napsal něco takového + nakreslil <math>oBF_3</math>. Předpokládám, že bez posledního odstavce by to tedy takto šlo použít i pro <math>wBF_n</math>:

<math>wBF_n</math> vzniká z <math>Q_n</math> nahrazením každého uzlu kružnicí <math>K(n)</math> a zároveň zdvojením hyperkubických hran tak, že nespojují jen dva stejnolehlé uzly, ale uzly sousední, jak nalevo, tak napravo. Průměr je vzdálenost mezi nejvzdálenějšími uzly, u <math>wBF_n</math> je tedy tvořen průměrem <math>Q_n</math>, což je <math>n</math> a průměrem <math>K(n)</math>, což je <math>\lfloor \frac{n}{2} \rfloor</math>.

<math>oBF_n</math> vzniká z <math>wBF_n</math> tak, že se “horní” uzel kružnice v rozdělí na dva a kružnice se vlastně nahradí mřížkou <math>M(n+1)</math>. Průměr <math>oBF_n</math> je tedy tvořen průměrem původní <math>Q_n</math>, což je <math>n</math> a průměrem <math>M(n+1)</math>, což je rovněž <math>n</math>.

⇒

<math>diam(oBF_n) = 2n</math>

★ Bylo ve zkoušce: 2015-01-28

Odvodit průměr na wBFn.

★ Bylo ve zkoušce: 2012-02-03

Viz přednáška 4, FIT slide 35, FEL slide 35 nebo skripta CZ [2006] str. 66, EN [2009] str. 47

Uzel ve <math>wBFn</math> je dvojice <math>(i,x), 0\leq{i}< n, x=B^n, B=\lbrace0,1\rbrace</math>.
Hrana je definována mezi uzly <math>(i,x)</math> a <math>(j,y)</math> pokud

• a) <math>x=y</math> a <math>j=i\oplus_n{1}</math> (pohyb po kružnici)
• b) <math>j=i\oplus_n{1}</math> a <math>y=neg_i{x}</math> (pohyb po hyperkubických hranách)
  

⇒ pokud se <math>{x}</math> a <math>{y}</math> liší v <math>{n}</math> bitech, je zapotřebí <math>{n}</math> hyperkubických hran ke změně <math>{x}</math> na <math>{y}</math>, teda z uzlu <math>(i,x)</math> se dostanu do <math>(i\oplus_n{n},y)=(i,y)</math>
V nejhorším případě musí ještě udělat <math>\left\lfloor {\frac{n}{2}} \right\rfloor</math> kroků v této kružnici ⇒ <math>n + \left\lfloor {\frac{n}{2}} \right\rfloor</math> kroků
⇒ <math>\phi(wBF_n)=n + \left\lfloor {\frac{n}{2}} \right\rfloor</math>

Pozn. by Vity: Ty pohyby po topologii možná vypadají děsně, ale podívejte se přitom na obrázek a co to dělá s těmi hranami - jak se mění index řádku <math>{i}</math> a index sloupce <math>{x}</math> (což je de facto sloupeček s tou kružnicí) a zjistíte, že to už dávno umíte.

Pozn. Když jsem si to zkoušel na obrázku pro n=3, zarazilo mě, že se nemůžu dostat po hyperkubických hranách do 010, jak tedy dokážu, že je výše zmíněný průměr správně? Musím se dostat za n tahů do správného sloupce. To udělám tak, že procházím bity odzadu. Pokud se shodují, udělám pohyb po kružnici, jinak udělám pohyb po hyperkubické hraně. Poté kontroluji další bit.

<math>wBF_n</math> je uzlově symetrický, proto je tato vzdálenost pro všechny uzly stejná

Viz přednáška 4, FIT slide 25, FEL slide 20 nebo CZ skripta [2006] str. 59 a EN [2010] str. 41

• Pro všechny uzly ve vzdálenosti i od našeho uzlu v Q_n platí, že se jejich adresa liší v i bitech (dimenzích). Počet uzlů ve vzdálenosti i je <math>{n \choose i}</math>, tj. všechny možné kombinace i bitů.
• Na vše se můžeme podívat stylem, že máme uzel, jehož adresa má samé nuly = n nul. Ve vzdálenosti i jsou uzly, jejichž adresa má (n - i) nul a i jedniček. Takže se ptáme, kolik existuje kombinací i jedniček a (n - i) nul ve vektoru délky n, tj. <math>{n \choose i}</math>.
• Krychle je uzlově symetrická, z každého uzlu vypadá graf stejně, takže pro každý uzel platí to samé.

★ Bylo ve zkoušce: 2012-12-18 2012-05-18

Poloměr je minimum z excentricit. Excentricita pro uzel udává, jak je od něj vzdálený nejvzdálenější uzel. 2D toroid nemusí být hranově symetrický, protože může mít různě dlouhé dimenze, ale je uzlově symetrický. Rozložit si ho lze na kartézský součin kružnic. Má-li kružnice <math>z</math> uzlů, nejvzdálenější v ní je ve vzdálenosti <math>\lfloor\frac{z}{2}\rfloor</math> – tedy je někde v pomyslné polovině, přičemž tam půjdu tou kratší stranou. Nejvzdálenější uzel ke každému uzlu bude takový, když se v každé dimenzi hnu o těch <math>\lfloor\frac{z}{2}\rfloor</math> – tedy excentricity všech uzlů by měly vyjít stejně, a to jako suma <math>\lfloor\frac{z_i}{2}\rfloor</math> přes všechny dimenze, tzn. ve 2D <math>\lfloor\frac{z_1}{2}\rfloor + \lfloor\frac{z_2}{2}\rfloor</math>, kde to <math>z</math> se mění a je to počet uzlů v dané dimenzi. Poloměr by měl být minimum z těchto stejných hodnot, takže je to to samé.

Domněnka by voho: uzlově symetrické grafy mají excentricitu všech uzlů stejnou.

Edit by plech.d: Ano a to navíc znamená, že u US grafů je poloměr roven průměru.

Obecně:

<math>\text{radius}\left(K\left(z_{1},z_{2},\dots,z_{n}\right)\right)=\text{diam}\left(K\left(z_{1},z_{2},\dots,z_{n}\right)\right)=\sum_{i=1}^{n}\left\lfloor \frac{z_{i}}{2}\right\rfloor</math>

Poloměr grafu je minimum z excentrit. Excentricita uzlu je nejkratší možná vzdálenost do nejvzdálenějšího uzlu. Krychle je uzlově symetrická, všechny uzly budou mít stejnou excentricitu – nejvzdálenější uzel od zvoleného uzlu je ve vzdálenosti n – jde o to, že mám n dimenzí, a všechny musím zinvertovat. Hledáme minimum z hodnot, které jsou všechny n, takže výsledek by měl být n.

Ještě jinak: excentricita(u) = maximální vzdálenost z uzlu u na kraj grafu. Což v případě <math>Q_n=n</math> (vždycky)
poloměr = minimální excentricita (ze všech uzlu)
průměr = maximální excentricita (ze všech uzlu)
Takže poloměr v <math>Q_n</math> = průměr = n

Domněnka by voho: uzlově symetrické grafy mají excentricitu všech uzlů stejnou.

Důkaz sporem by wabbit: Nechť G je uzlově symetrický graf a mějme automorfismus <math>f:f(v)=u</math>, předpokládejme že:

<math>\exists u, v \in V(G): exc(u) \gt exc(v)</math> potom by platilo že <math>exc(u) \gt exc(f(v))=exc(u)</math> což neplatí

★ Bylo ve zkoušce: 2016-05-26

<math>\text{radius}\left(M\left(a,b,c\right)\right)=\left\lceil \frac{a}{2}\right\rceil +\left\lceil \frac{b}{2}\right\rceil +\left\lceil \frac{c}{2}\right\rceil </math>

(sry za špatné formátování, ale je to třikrát horní část)

EDIT: podle mýho dolní celá část.

★ Bylo ve zkoušce: 2014-02-12

Dimenze k = počet *, např. 101*0* je dvourozměrná podkrychle

počet podkrychlí = (kolika způsoby můžeme rozmístit hvězdičky) * (počet kombinací zbývajících 0 a 1)

<math>n_choose_k{\cdot}2^{(n-k)}</math>

Podrobněji

Všimněmě si, že se jedná o zobecnění tvrzení o počtu hran na <math>Q_{n}</math>, kde se tvrdí, že to je <math>n\cdot2^n</math>, což odpovídá tomuto vztahu. Dimenze nám definuje jaké podkrychle hledáme. Dimenze 0 tedy znamená, že hledáme vrcholy a dimenze 1 počet hran.

Pokud hledáme vyšší dimenze, tak bereme v potaz dvě operace. Kolik kombinací dimenzí můžeme “zafixovat” (např pro dimenzy 2 jde o: <math>(d_1,d_2),(d_1,d_3),…(d_{n-1},d_n)</math>). Pro každé toto zafixování generujeme všechny možné variace s opakováním jedniček a nul. Máme však už jen omezené množství dimenzí. (Například pro dimenzi 2 už máme pouze <math>n-2</math> volných pozic pro variace. Na ty pozice postupně generujeme všechny možné variace: <math>(0,0…0),(0,0…0,1),…(1,1…1))</math>. Jejich význam je takový, že nám každá konkrétní variace definuje jednu konkrétní podkrychli.

Příklad

Mějme dimenzi 3, tudíž krychli.

1. k=0, (body), každá variace definuje konkrétní souřadnice bodu [0,0,0] je bod
2. k=1, (hrany), každá variace definuje konkrétní dva body, které tvoří hranu [0,0,*] ⇒ umožňuje dosadit [0,0,0] a [0,0,1], což nám jednoznačně určuje hranu
3. k=2, (čtverec), každá variace definuje konkrétní 4 body, které dohromady tvoří čtverec [0,*,*] ⇒ umožňuje dosadit [0,0,0], [0,0,1], [0,1,0] a [0,1,1], což nám jednoznačně určuje čtverec
4. k=3, (krychle), ta je v krychli jen jedna, neboť 3 proměnné dávají pouze jednu možnost [*,*,*] ⇒ umožňuje dosadit [0,0,0], [0,0,1], [0,1,0], [0,1,1], [1,0,0], [1,0,1], [1,1,0] a [1,1,1], což nám jednoznačně určuje krychli

Možností na zafixování dimenzí odpovídá problému “kolik kombinací k dimenzí můžu vybrat z n” ⇒ kombinace bez opakování

Kolik takových podkrychlí existuje odpovídá “kolik je možností jak zapsat 1 a 0 do <math>n-k</math> pozic” ⇒ variace s opakováním

Uvažujte bijekci <math>f: V(Q_7) \to V(Q_7)</math>, o níž pouze víme, že f(0101110) = 1010110 a f(1101010) = 0101111. Může být f automorfismem hyperkrychle Q₇? Svoji odpověď zdůvodněte.

★ Bylo ve zkoušce: 2013-01-23, 2012-06-26, 2014-02-04

Automorfismy v krychli vzniknou přeložením a permutace a nebo kombinací obojího. Ani jedna operace nemění hammingovu vzdálenost vzorů a obrazů (musí platit, že hammingova vzdálenost dvou obrazů odpovídá vzdálenosti jejich vzorů - aneb sousedi zůstávají sousedy!). Když si spočtu vzdálenost obrazů a vzorů, vyjde pro oba automorfismy jiná (vzory mají 2 a obrazy 5). Nejedná se o stejný automorfismus na krychli, neboť původně byli v krychli vzdálení 2 dimenze (cesta 2 hran) a v automorfismu by byli vzdáleni 5 (cesta o 5 hranách).

Nemůže - automorfismy hyperkrychle nastávají při kombinaci permutací a negací adresových bitů.
Když se ty dvě posloupnosti napíšou pod sebe, tak originální adresy mají 5 stejných sloupců. Nové adresy ale mají jen 2 stejné sloupce, což by nemělo nastat.

Pozn. by Kugel: Ja si myslím, že jednoduchšie to je takto: Povedzme, že prvé <math> f </math> nám definuje automorfizmus, teda je to buď posun alebo rotácia. Rotácia to určite nie je, pretože 0101110 má 3 jedničky po sebe a 1010110 nemá, takže rotácie určite nie. Ešte by to mohol byť posun. Definovaný takto: <math>{f}_{u \rightarrow v}(x) = x \oplus (u \oplus v)</math> teda <math>{f}_{u \rightarrow v}(1101010) = 1101010 \oplus (0101110 \oplus 1010110) = 0010010</math>, čo teda rozhodne nie je 0101111 ako ukazuje druhé <math> f </math> v zadaní. Pozn: Aby se zachoval automorfizmus musí se zachovat sousednost uzlů - sousedé musí zůstat sousedy, čehož docílíme aplikováním stejných operací na adresy uzlů. 7. proseminář, čas 22:40+

Pozor! Nestačí rotace nebo posun, ale může to také být jejich kombinace! Takže je třeba si vyzkoušet nalézt takovou funkci, XOR sám nestačí.

Info přímo od Tvrdíka od zkoušky: Stačí aby byla stejná Hammingova vzdálenost vzorů a obrazů. Tečka. Na vzdálenosti změněnejch bitů nezáleží.

+1, dneska jsem to přesně tak napsal a dal mi dva body ještě než jsem si sednul

Jakou adresu a dimenzi má průnik dvou podkrychlí s1 = * 0 1 * * 0 * * 1 a S2 = 1 * * 1 * 0 1 * 0 v hyperkrychli Q₉, Zdůvodněte.

★ Bylo ve zkoušce: 2012-01-31

Formálněji: sloučení vznikne použitím této funkce f na jednotlivé bity:

• f(0,0) = 0
• f(1,1) = 1
• f(0,1) = f(1,0) = prazdna množina
• f(x,0) = f(0,x) = 0
• f(x,1) = f(1,x) = 1
• f(x,x) = x

Lidsky:

Pro každou dimenzi se snažíme vyhovět oběma krychlím. Pokud jedna použije “Jokera” neboli * tak tam může být jak 0 tak 1. Jestliže se krychle liší v nějaké dimenzi, tak potom nemají průnik. Pokud k takové situaci nedojde, tak výsledek je počet hvězdiček v průniku.

Dimenze je 0 ( tím je myšleno Ø tedy žádný průnik ), neboť se krychle liší v poslední dimenzi. Výsledek znázorňuje dva protější čtverce, ale nemají průnik, neboť je každý v trochu jiné dimenzi.

Kdyby bylo zadání: <math>s_1 = *0101</math> a <math>s_2 = 1**1*01*1</math>

1. sloučíme dohromady: <math>s = s_1 \cap s_2 = 1011*01*1</math>
2. dimenze průniku je 2
3. Průnik jsou body [1,0,1,1,[0|1],0,1,[0|1],1]

škola zkoušky s_řešením