Odvoďte maximální y takové, že mřížku M(3,y) lze vnořit do mřížky M(11,10) s dil = 1 a load = 2. Příslušné vnoření popište algebraicky nebo schématickým obrázkem. Odvoďte hodnotu hranového zahlcení.

★ Bylo ve zkoušce: 2013-01-16 a 2012-01-24

Viz skripta CZ [2006] str. 87 nebo EN [2009] str. 70

Řešení 58 lze dosáhnout tak, že šneka z předchozího řešení (57) přetočíme o 90 stupňů a neuděláme poslední ohyb. Uprostřed tak zbyde 5 volných míst s load 0, což je stejné jako v současném řešení, ale nebudou tam ta tři místa s load 1.

Hnědé mají load 2, červené load 1, černé load 0. Celkem tedy 23*2 + 4*3 = 58 (by stadlmic)

Asi nejlepší: 57 (ještě lepší je 58)
Vezmu si šneka z obrázku (PCMaster&kodovac, puvodni delka 36). Všude kde jsou na obrázku rovné pásy ze světle červených uzlů (load=1) udělám load=2 tak, že prohnu každou trojici pásu jako harmoniku. Tedy místo jedné trojice uzlů tam bude vždy ležet šetice. To bude pro každou tu rovinu. Pak dostanu y = 57.

Dodatek : Jak namapovat část mřížky o šířce 3 na šneka v oněch ohybech. Černý uzly jsou ty s load 2 :

56 - fialové uzly mají na sobě 2 následující sloupce hada (eg. harmonika), vínové (load=2) a červené (load=1) se používjí, když se nedá zdvojit celý sloupec.
y = 36, ecng = load = 2 (v místech přeložení jsou dvě hrany na jedný a dva uzly v jednom) nejlepší pro pochopení je ustřihnout si čtverečkovanej papírek a přeložit si ho tak jako na př.5/sl.25, kde je ostatně k tomuhle jasnej obrázek. Tady se víc hodí ten zatočenej šnek. Využije se tím víc místa, ten had vyjde jenom na (32 nebo 33)

Vrchný obrázok ukazuje “hada” dĺžky 32 (zaradom 10 + 10 + 10 + 2), spodný “slimáka” (šneka) dĺžky 36 (zaradom je to: 10 + 8 + 7 + 5 + 4 + 2). Biele uzly majú load 0, červené 1 a hnedé 2. Dilatácia je všade 1, hranové zahltenie 1-2.

Pozn.: Když už máme povolený load 2, proč šneka ještě neprodloužit přes tu část, která má load 1? Délka se tak protáhne na 39, resp. dokonce až na 41. Pokud šnek nezačne na nultém, ale na šestém řádku (půjde směrem vzhůru na nahoře se otočí), lze počáteční část také dvakrát vytížit a zvýšit délku na 46. Konečně prohozením mapování os x a y se dá dosáhnout prodloužení ještě na 47.

Pozn. 2: Najlepsi pripad je S-ko s prelozenymi koncami. Vysledne y je potom 50.

Pozn. 3: Kdekoliv mimo ohyb mapuju dva uzly do jednoho - Horni “rovinka” v Sku: 2*8, prostredni rovinka v Sku 2*5, dolni rovinka v Sku 2*8. Pak tam jsou 2 ohyby = 2*6. Dohromady 2*8+6+2*5+6+2*8=16+6+10+6+16 = 32 + 12 + 10 = 54.

viz obrázek:

V modré části mapuji vždy 2 uzly na sebe.

Pozn. 4: IMHO nebylo by náhodou možný jeden z těch zelených přehybů prodloužit ještě o jeden řádek ? Dostali bychom tak y ještě o jedno větší, tedy 55… (kibitzer)

Pozn. 5: IMHO to co navrhl Kibitzer + použít na tomto místě harmoniku a dostanem 56 (BzabA - ludacrad & koznama1 souhlasí)

PS, pro představu co to je “harmonika” - Představte si schody. Na ty schody dejte koberec. Ten koberec je původní graf. Když se pak na to celé podíváte zeshora jakoby půdorys, je to ten nový graf. Na koncích každého schodu jsou vlastně nad sebou namapovány dva sousední uzly, spojené hranou o délce 0.

Cik-cak had - 58

Muzeme udelat jeste moznost soupajiciho se hada. Zacneme ve vrcholu [1,1][2,1][3,1] a šoupneme se dolu na [2,1][3,1][4,1]. Abychom neporusili podminku na load musíme se šoupnout horizontálně. [2,2][3,2][4,2]. Poté se šoupeme zase nahoru. Takhle to děláme až do konce kde hada otočíme. Uděláme si tam jednu přestávku pro dva sloupce M a pak dokončíme otočku. Opět se šoupeme akorát zpět k počátku.

Výhodou je, že vzniklé uzly s load 1 ted dostanou další load z druhé strany, takže je plně obsazeno. Navíc se nám zjednoduší na konci otočka. Takto pokračujeme až do konce. Všude je load 2 a diletace 1 nebo 0.

Soucty pod sloupcema znamenaji load jednotlivých nodů. 58 podělí sumu 3. Číslo pod tím 46 je “neefektivnost řešení, čili jaký potenciál loadu je nevyužit. Neboli v každém sloupci je 2*10-Suma.

Odvoďte minimální y takové, že mřížku M(8,8) vnoříme do mřížky M(3,y) s dil ≤ 2 a load = 2. Příslušné vnoření popište algebraicky nebo schématickým obrázkem. Odvoďte hodnotu hranového zahlcení.

Viz skripta CZ [2006] str. 87 nebo EN [2009] str. 70 nebo přednášky 2015/5 slide 34

3 sloupce = 2 hadi (2 hadi vezmou 3 sloupce)
potřebujem umístit 8 hadů ⇒ y = 12
hranové zahlcení : ecng = 4
Pozn.: ecng by imho melo byt 3, protoze za prve je ve skriptech i slajdech vzorec ecng = 1 + dil a za druhe ta hrana cislo 2 na obrazku zde neexistuje.
Reakce na pozn.: Tak ja tam vidim nasledujici hrany:

1. Hrana 1-1 ze sousednich sloupcu M(8,8)
2. Hrana 6-7 ze stejneho sloupce
3. Hrana 6-6 ze sousednich sloupcu
4. Hrana 7-7 ze sousednich sloupcu

ecng=3, hodnota 4 je špatně, viz
Pozn.: Tak ano, v tom jednom miste jsou namapovany 3 hrany, ale nas zajima maximalni ecng a to je tam kam ukazuje ta sipka.

Note by meba: Řešení vychází z přednášky 5, slajd 34 - vnoření čtverce do obdélníku, kde obdélník má jeden rozměr o mnoho větší než ten první rozměr. Představte si čtverec, jeho každý sloupec je had. M(8,8) - 8 sloupců, tzn. máme 8 hadů, které tam musíme narvat. Teď si udělejte velkou mřížku s 3 řádky a mnoho sloupců. Vemte jeden had, tzn. 8 uzlů spojených hranami a postupně je kreslete do obdélníku. Když dojedu na konec řádku, otočím se a jedu nahoru. Když skončím hada, začínám z nového sloupce. Takhle můžu nakreslit celou mříž a jsem hotov. ALE - takhle se mi to nevejde - plýtvám uzly. Proto vím, že load může být 2 a já prostě hady kreslím tak, abych některé sloupce překryl.

Tento obrázek by mohl znázorňovat to samé jinak. Jde jen o část řešení. Velký obrázek je část úzké mřížky, malý obrázek část čtvertové mřížky.

Trocha teorie:

• ecng - linkové zahlcení je max. počet obrazů zdrojových hran procházejících skrz cílové linky

Pozorování

jkabelka: Vykoukal jsem, že když má had (řádek/sloupec z původní mřížky) vnořenou šířku 2, tak ecng = 4? A když má šířku 3 (úlohy za 6 b.), tak ecng = 6? Obecně to tedy svádí k tomu říci, že ecng = dil * šířka hada. Může to někdo ověřit/vyvrátit?

Odvoďte maximální y takové, že mřížku M(2,y) vnoříme do mřížky M(4,5) s dil = 1 a load = 2. Příslušné vnoření popište algebraicky nebo schématickým obrázkem. Odvoďte hodnotu hranového zahlcení.

pozn by plysovej_kaktus: co takhle tu mrizku prehnout podelne, aby z ni byl had o sirce 1 a load=2 ? potom ho tam nasoukejte, jak chcete, ale je to 20 :)) juchuuuu.

To je blbost ne? Ked prehnes podelne tak nezachovas dil = 1 (Kugel) IMHO je to dobře: bude ecng 2, ale dil zustane 1, protoze sousednosti jsou zachovany (Chajak)

IMHO je to řešení s přehnutím na půl špatně, protože je zadaná dil = 1 a při přehnutí bude třeba dilatace těch dvou krajních uzlů 0, protože se překryjí a hrana mezi nimi nebude… (shid007) to jo, ale dil je stejně jako load definovaná jako max ze všech, čili pokud je někde méně než 1 není to problém (chajak) (MiKe) - ovsem je to spatne, protoze nezachovas dilataci rovnou 1… tady je problem s dilataci mezi 2 a tretim hadem (had v tomto pripade myslim 1D mrizku o velikosti (2,5)… )… ; Imho je to správně, dilatace vnoření je definována jako max dilatací, kde při přeložení do 1D mřížky (z (2, 20) na 1 (1,20)) a hadovité nasoukání na jakoukoli jinou mřížku bude dilatace vyšší jak 1? (libik) Souhlasím s plysovej_kaktus, chajakem i libikem, dilatace vnoření je MAXIMUM dilatací všech zdrojových hran. Nemáme-li jiné omezení, není důvod nepřehnout mřížku a neudělat z ní 1-D. ecng bude rovno také 2. (plech.d)

přímo 10 + přehyby 6 ⇒y = 16
hranové zahlcení : ecng = 2

Jiný obrázek, stejné řešení. V podstatě to samé, jako první příklad:

Červené uzly mají load=2, modré load=1.

Odvoďte maximální y takové, že mřížku M(3,y) vnoříme do mřížky M(7,9) s dil = 1 a load = 2. Příslušné vnoření popište algebraicky nebo schématickým obrázkem. Odvoďte hodnotu hranového zahlcení.

přímo 21 + přehyby 8 ⇒y = 29
hranové zahlcení : ecng = 2

Note: podle mne to bude 30, je tam harmonika v druhém “řádku”
Jagu: souhlasím s 30, stejný postup ale ne po radcich, ale ohybejte po sloupcích
Jagu: Přidávám ještě jednu variantu, jakmile překládáte hada na posledním řádku, tak jelikož je pod mím ještě řádek místa, přeložte ho až na tento poslední řádek. Získáte o jedno lepší řešení. Tedy 31! Rozpis: 6*2 za rovny usek s loadem 2, +3 za ohyb(load2), +1 rovný úsek s load 1, +3 za ohyb(load2), + 6*2 za rovny úsek s load 2 celkem tedy: (6*2)*2 +3*2 +1 = 31 Složte si kostičkovanej papír a pak už to jde samo :) BTW na ZK si beru nastříhanej papír
qoop: ad Jagu: ten 1 rovny usek dolu se muze zdvojit na load 2, tzn jeste o 1 lepsi reseni: 32
Savannah: Pokud to uděláte jako písmeno U, tzn. začnete vlevo nahoře, 6x dolu zdvojeně (12*y), otočka na východ (3*y), 1x vpravo zdvojeně (harmonika) (2*y), otočka na sever (3*y) a 6x nahoru zdvojeně (12*y). Celkem 12 + 3 + 2 + 3 + 12 = 32. (goop: byls rychlejší :) Ale je to jiné řešení a trochu líp se pamatuje)
Jagu: Souhlasím s 32, je pravda že ten rovný úsek jde harmonikovat. Jinak obecně pro tyto problémy. S-ko vždy lze aplikovat na tyto problémy, a to tak že se snažím vždy využít delší hrany obdelníka kam mapuju tak, abych konec ska co nejvíc přehnul, pak je to jediné řešení pro všechny případy, a vždy vychází maximum zde popsané. Opravdu příklad za body zdarma…

Trochu jiný obrázek, y=32. Červené uzly mají load=2, modré load=1, ecng=2.

Vnoření dvojrozměrného toroidu <math>T(z1,z2)</math> do kružnice <math>K(z1*z2)</math>. Určit hranové zahlcení, dilataci.

★ Bylo ve zkoušce: 2013-01-23, 2015-01-20

Viz CZ skripta [2006] str. 86, EN skripta [2009] str. 68 nebo FIT přednáška 5 slajd 32

Jedná se o vnoření 2-D toroidu do 1-D toroidu.

Představme si 2-D toroid jen jako mřížku. Dále tuto mřížku rozdělme po sloupcích ( v případě že z1 < z2 ). Sloupce za sebe poskládáme do jednoho dlouhýho hada. Začátek a konec hada spojíme, tím vznikne kružnice.

Vzniklá kružnice není nikde přeložená, takže <math>load = 1</math>
Dilatace je rovna počtu prvků ve sloupci <math>dil = z1</math> , respektive <math>min( z1,z2 )</math>
Hranové zahlcení <math>ecng = dil + 2</math>
Podmínka <math>z_1 \neq z_2</math>

Pozn. 1: Bacha, tady se rozchazeji ceska a anglicka skripta!

Pozn. 2, krejcpa8: Sám Tvrdík mi říkal, že podmínka <math>z_1 \neq z_2</math> je blbost. Je tam nešikovně napsaná - platí zkrátka <math>dil = min( z1,z2 )</math>

EN skripta: <math>z_1 >= z_2</math> - column wise mapping, <math>z_1 < z_2</math> - row wise mapping

Pozn. 3: V určení, kdy mapovat po sloupcích a kdy po řádcích (porovnání z1 - počet sloupců a z2 - počet řádků) je zde chyba (stejně tak ve slidech (ZS 2015) a nejspíš i českých skriptech). Za sebe se samozřejmě skládají “hadi” s kratším rozměrem, aby se dosáhlo menší dilatace a zahlcení. Pokud je tedy méně řádků → jsou kratší sloupce, mapuje se po sloupcích. Je to jasně vidět z obrázku.

Věta 22, přednáška 2015/5, slide 32: Pro <math>z_{1}\neq z_{2}</math>, <math>\exists</math> optimální vnoření <math>K\left(z_{1},z_{2}\right)\overset{\text{emb}}{\mapsto}K\left(z_{1}\mathtt{*}z_{2}\right)</math> s <math>\mathtt{load}=1</math> , <math>\mathtt{dil}=\min\left(z_{1},z_{2}\right)</math> , <math>\mathtt{ecng}=\mathtt{dil}+2</math>. .

★ Bylo ve zkoušce: 2013-01-09, 2012-06-26

Odvoďte spodní mez dilatace vnoření úplného binárního stromu CBT_n do 2D toroidu <math>K(2^{\lceil(n+1)/2\rceil},2^{\lfloor(n+1)/2\rfloor})</math> s load = 1.

Na plný počet bodů prý dnes stačilo napsat, že dilataci odvodím jako průměr grafu, do kterého vnořuji, lomeno průměr vnořovaného grafu.

<math>\text{dil}\left(\varphi,\xi\right)\geq\left\lceil \frac{\text{diam}\left(H\right)}{\text{diam}\left(G\right)}\right\rceil</math>

Jinak já to zkusil takhle:

Počet uzlů <math>CBT_n = 2^{n+1} - 1</math>

Počet uzlů toroidu <math>K(2^{\lceil(n+1)/2\rceil},2^{\lfloor(n+1)/2\rfloor}) = 2^{\lceil(n+1)/2\rceil} * 2^{\lfloor(n+1)/2\rfloor} = 2^{\lceil(n+1)/2\rceil+\lfloor(n+1)/2\rfloor} = 2^{n+1} </math>

(jestliže n+1 dělím dvěma, jednou vezmu horní a jednou dolní část, tak dohromady mám stále n+1) takže strom má o jeden uzel méně a teoreticky se do toroidu vejde. Víc mě nezajímá.

Dva nejvzdálenější uzly v <math>CBT_n</math> jsou jakékoli dva listy z různých podstromů, cesta přes kořen je dlouhá <math>2n</math>.

V <math> K </math> bude vzdálenost rovna součtu menších polovin kružnic obou rozměrů.

<math> = (2^{\lceil(n+1)/2\rceil} + 2^{\lfloor(n+1)/2\rfloor})/2 = (2^{\lceil(n-1+2)/2\rceil} + 2^{\lfloor(n-1+2)/2\rfloor})/2 = (2^{\lceil(n-1)/2\rceil+1} + 2^{\lfloor(n-1)/2\rfloor+1})/2 =
= (2*2^{\lceil(n-1)/2\rceil} + 2*2^{\lfloor(n-1)/2\rfloor})/2 = (2^{\lceil(n-1)/2\rceil} + 2^{\lfloor(n-1)/2\rfloor})</math>.

Takže teď mám oba průměry, jejichž podíl prohlásím za dilataci. Jen ještě čitatel zmenším o 1, protože v toroidu je o jedno místo víc, než strom pro své uzly potřebuje. Strom v něm tedy nemusím natáhnout úplně maximálně.

<math>dil = ( (2^{\lceil(n-1)/2\rceil} + 2^{\lfloor(n-1)/2\rfloor}) - 1 ) / 2n</math>

EDIT: probuh, ty tve matematicke upravy jsou hrozne … ale korektni… ale mohl si to uz dokoncit a napsat vysledek ”<math>(2^{\lceil(n+1)/2\rceil}/2n</math>“

Tak jsem se vyřádil, ale u zkoušky mi bylo řečeno, že stačí dát do podílu průměry , neni potřeba se zahazovat s jedničkama, když je celej rok škrtáme.

Podľa CZ skrípt str. 78 v prípade, že load=1 platí: dil >= diam(H) / diam(G).
teda průmer toroidu / průmer stromu.

IMHO je finální výsledek:

<math>\mathtt{dil}\left(\right)\geq\frac{2^{\left\lceil \frac{\left(n-1\right)}{2}\right\rceil }}{n}</math>

Jaká bude spodní mez dilatace při vnoření Q_2n do toroidu T(2ⁿ,2ⁿ) s load = 1?

★ Bylo ve zkoušce: 2011-05-19 (CBTn do 2D Toroidu) a 2012-01-24

Viz přednáška 5, slajd 22 + slajd 5 (FIT 5 přednáška sl. 30), věta 4 nebo skripta EN [2009] str. 67

Rozhodující je jaké uzly se mapují na nejvzdálenější uzly v toroidu <math>T(2^n,2^n)</math>.
Protože <math>|V(T) | = |V(Q) |</math> a load = 1, musí být dva nejvzdálenější uzly v toroidu obsazené uzly z hyperkrychle. Nejlepší případ je, pokud se nám podaří na nejvzdálenější uzly v T namapovat ty nejvzdálenější z <math>Q_{2n}</math> _{[cs skripta str. 78]}
Maximální vzdálenost v T (tedy průměr) je <math>\phi (T) = \sum_{i=1}^n \left \lfloor \frac{z_i}{2} \right \rfloor \Rightarrow \phi(T(2^n,2^n)) = 2\cdot \frac { 2^n} {2} = 2^n </math>
Maximální vzdálenost v hyperkrychli je <math>\phi (Q_{2n}) = 2n \Rightarrow dil \geq \frac {2^n} {2n}</math>

Popište algoritmus konstrukce Hamiltonovské kružnice v obecném souvislém grafu G = (V(G),E(G)) s dilatací nejvýše 3 a dokažte jeho korektnost.

★ Bylo ve zkoušce: 2012-01-31, 2013-02-06, 2014-02-04, 2016-01-15

EN skripta str. 72, česká skripta str. 89 a 91

Viz Důkaz možnosti vnoření kružnice do libovolného G s load=1, dil<=3

N -uzlová kružnice C může být vnořena do jakékoli N -uzlové sítě G s load = 1, dil ≤ 3 a ecng = 2.

Důkaz.

1. Zkonstruuj kostru T_G grafu G.
2. Rozděl její uzly na uzly sudé úrovně (V₀) - zelené uzly a liché úrovně (V₁) - fialové uzly.
3. Procházej T_G do hloubky zleva doprava (DFS) a umísťuj postupně uzly C do T_G ⇔

• momentálně navštívený uzel je ve V1 a je to první návštěva tohoto uzlu,
• momentálně navštívený uzel je ve V0 a je to poslední návštěva tohoto uzlu.

Tyto podmínky zajišťují, že každý uzel T_G bude mít load = 1. Obrázek ukazuje, že dil = 3 vzniká při přechodech z jednoho podstromu do sousedního podstromu přes společný kořen.

Jedná se vlastně o konstrukci zobecněné Hamiltonovské kružnice s dilatací 3.

- důkaz na obrázku nestačí (2b z 4). Důkaz je konstrukční, čili popsání algoritmu + je dobrý se tam zmínit, proč nemůže být nikdy dilatace větší než 3 - na obrázku to ukázat a říct, že nikdy nemůže nastat horší případ, protože strom je rekurzivní struktura

Odvoďte počet různých automorfismů Qn tak, že nějaký daný uzel u se zobrazí na uzel v, tedy φ(u) = v, a odpověď dokažte (konstrukčně)

Kombinací permutace dimenzí a přeložení můžu vytvořit celkem n! automorfismů, protože libovolnou permutaci n dimenzí poté „dorovnám“ přiXORováním správného řetězce tak, aby z u vyšlo požadované v.

Stačí toto? Nemusíme dokazovat, že permutace + přeložení je automorfismus (že zachovává sousednost)? (plech.d)

Poznamka 1: Nie je spravna odpoved <math>n! * 2^n</math>? <math>n!</math> pre permutaciu dimenzii a kazda permutacia ma <math>2^n</math> prelozeni? (polakluk)

polakluk: To co píšeš je pravda, ale jelikož máme daný zobrazení z u na v, tak tam nepotřebujeme všech <math>2^n</math> přeložení. (vlasaj)

Takže ten původní text ale pravdivý není, i když obsahuje správný výsledek, ne? Protože obecně kombinací permutace dimenzí a přeložení se zachováním sousednosti uzlů můžu vyvořit celkem <math>n! * 2^n</math>, ale přeložení (kterých je jinak <math>2^n</math>) je dáno pouze jediné tím zadáním fi(u)=v, takže zbývají jen permutace dimenzí, kterých mohu vytvořit celkem n!. (bliznjan)

Dneska Byla opět tato otázka, a ten původní text, resp věta na 1 řádek, sice v zásadě říká pravdu, ale tak stručně to zkrátka nestačí. Chtěl zhruba takto: Obecně by bylo automorfismů tolik, kolik by bylo kombinací permutace dimenzí (kterých je <math>n!</math>) a přeložení souřadnic (<math>2^n</math>), takže celkem <math>n! * 2^n</math>, ALE: Vzhledem k zadanému zobrazení <math>u</math> na <math>v</math> můžeme nejdříve permutovat dimenze, to je těch <math>n!</math>, ale potom už máme jedinou možnou volbu pro přeložení aby se <math>u</math> zobrazilo na <math>v</math>, takže následně použijeme operaci XOR se stejným jedním bitovým řetězcem na adresy všechny uzlů tak, aby adresa <math>u</math> po permutaci dimenzí XOR ten náš jeden řetězec vyšla jako <math>v</math>. Přeložení je tedy takto dané a mohli jsme si vybrat jen těch <math>n!</math> permutací dimenzí. Jakmile tam člověk nenapsal to, že nejdřív permutujeme dimenze a pak s těma adresama po permutaci uděláme stejný XOR tak, aby se tohle “zpermutovaný” <math>u</math> zobrazilo na <math>v</math>, a že tenhle jeden stejný bitový řetězec XORem použijeme shodně na všechny uzly, tak strhával body (dával 2-3). (bliznjan)

Odvoďte výraz pro průměrnou vzdálenost v n-rozměrné hyperkrychli Q_n.

Pozor na rozlišování průměru grafu (největší vzdálenost mezi libovolnými dvěma uzly) a průměrné vzdálenosti v grafu (která se počítá jako normální průměr, tedy součet hodnot položek lomeno počet položek).

N = počet uzlů, n = dimenze.

průměrná vzdálenost = (suma všech vzdáleností od všech uzlů) / (počet všech cest mezi uzly)
- počítají se jen nejkratší vzdálenosti

Od libovolného uzlu je <math>\begin{pmatrix}n
i \end{pmatrix} </math> uzlů ve vzdálenosti <math>{i}</math> ⇒
<math>\sum_{i=1}^n i*\begin{pmatrix}n
i \end{pmatrix}</math> = suma všech vzdáleností od jednoho uzlu ⇒
<math>N*\sum_{i=1}^n i* \begin{pmatrix}n
i \end{pmatrix}</math> = suma všech vzdáleností od všech uzlů (protože plati uzlová symetrie, všechny uzly jsou stejný)

V každém grafu je celkem <math>N*(N-1)</math> dvojic uzlů u,v, kde <math>u \neq v</math>, u kterých počítáme jejich vzdálenost.

Definice skripta CZ [2006] str. 55 nebo EN [2009] str. 37 - průměrná vzdálenost v N-uzlovém grafu G je:

<math> \overline{dist} (G) = \frac{ \sum_{u,v} dist_G (u,v) }{ N \cdot (N-1) }</math>

Výpočet:

<math>\overline{dist} (G) = \frac{ \sum_{u,v} dist_G (u,v) }{ N \cdot (N-1) } = \frac{ N \cdot \sum_{i=1}^n i \cdot {n \choose i} }{ N \cdot (N-1) } = \frac{ \sum_{i=1}^n i \cdot {n \choose i} }{ 2^n -1 } = \frac{ n \cdot 2^{n-1} }{ 2^n - 1 } \approx {\Large\lceil}\frac{n}{2}{\Large\rceil}</math>

Vzoreček z http://en.wikipedia.org/wiki/Binomial_coefficient#Series_involving_binomial_coefficients.

Pozn.: Tuto variantu mi Tvrdík neuznal, vadila mu závislost na N (i když se vykrátilo). Cituji „Co je tohle? To je velké N? Tak to je špatně.“

Pozn.2: <math>{ N \cdot (N-1) }</math> je v jeho definici, viz výše, musí to platit. (marekkoznar)

Pozn.3: Qn je uzlove symetricka, zavislost na N tedy vazne neni potreba, protoze staci pocitat vzdalenosti od jednoho uzlu, tedy zacit rovnou krokem <math>\frac{ \sum_{i=1}^n i \cdot {n \choose i} }{ 2^n -1 }</math>

Edit: Pro ty, kteří tam nevidí, jak se to zkrátilo. Trik spočívá v tom, že započítáme i cestu od počátku k sobě samému, která je sice 0, ale pak se to hezky zkrátí.

<math>\overline{\text{dist}}\left(G\right)=\frac{\cancel{N}*\sum_{i=1}^{n}i*\binom{n}{i}}{\cancel{N}*\left(N-1\right)}=\frac{\sum_{i=0}^{n}i*\binom{n}{i}}{2{}^{n}\cancel{-1}}=\frac{n*\cancel{2^{n-1}}}{2^{\cancel{n}}}=\boxed{\underline{\underline{\left\lceil \frac{n}{2}\right\rceil }}}\text{.}</math>

Viz CZ skripta [2006] str. 59 nebo EN [2009] str. 41

V hyperkrychli platí uzlová symetrie, takže problém stačí řešit z pohledu jednoho uzlu (nakonec by se to stejně vykrátilo).

Od libovolného uzlu je <math>n \choose i</math> uzlů ve vzdálenosti <math>{i}</math>. Pro kombinační číslo platí rovnost <math>{n \choose i} = {n \choose n-i}</math>. To znamená, že ve vzdálenostech <math>{i}</math> a <math>\normalsize {n-i}</math> je vždy stejný počet uzlů. Jinak řečeno, pokaždé lze vykrátit kratší cestu s delší. Například:

• ve vzdálenosti <math>\normalsize i = 1</math> a <math>\normalsize i = n-1</math> je <math>{n \choose 1} = {n \choose n-1}</math> uzlů a jejich průměrná vzdálenost je <math>\frac{1+(n-1)}{2} = \frac{n}{2}</math>
• ve vzdálenosti <math>\normalsize i = 2</math> a <math>\normalsize i = n-2</math> je <math>{n \choose 2} = {n \choose n-2}</math> uzlů a jejich průměrná vzdálenost je <math>\frac{2+(n-2)}{2} = \frac{n}{2}</math>,
• atd.

Celková průměrná vzdálenost je tedy <math>\frac{n}{2}</math>.

Pozn. (bangom): Opravdu tam musíte napsat, jak jste k tomu došli. Nestačí mu, že to je n/2… Jinak máte jen polovinu bodů (v lepším případě). Takže to musíte vysvětlit přes tu sumu (dotáhnout do konce!) nebo jednodušeji přes rovnost kombinatorických vzorců.

Pozn. (jkabelka): Jestli to chápu správně, tak rozdíl oproti řešení 1 je v pohledu na nejvzdálenější prvek (jeden) a počáteční uzel. Nejvzdálenější uzel, který je ve vzdálenosti n, tady podle mě není započítán. Když ho ale započítáme, tak zároveň můžeme vezmeme i vzdálenost od počátku k sobě samému (tedy vzdálenost 0), aby nám to nerozhodilo průměr, takže po zprůměrování je to opět <math>\frac{n}{2}</math>. Ten jeden uzel (ten počáteční) dělá rozdíl oproti výsledku v prvním řešení. Tam kdyby se neodečetla jednička ve jmenovateli (a suma by byla od nuly, což je stejné jako od jedné), tak to vyjde stejně, rovných <math>\frac{n}{2}</math>.

V M(11,6,13) určete počet hran a b_we.

Viz přednáška 4 slide 10 a 23

Počet hran v mřížce: <math>\sum_{\forall{i}}^{}(z_i-1)\prod_{\forall{j, j\ne{i}}}z_j</math>

Dle vzorce vychází pro M(3,2,5): (2 x 10) + (1 x 15) + (4 x 6) = 59 hran. Pro ověření na M(3,3) je to: (2 x 3) + (2 x 3)= 12 hran.
Pro zadání M(11,6,13) je to tedy: (10 x 78) + (5 x 143) + (12 x 66) = 2287 hran.

Intuitivnější způsob:
Počet hran mřížky lze vyvodit z věty o žebříku („Počet příček žebříku a počet děr mezi nimi liší se o jedničku.“)

• 1D mřížka: <math>|E(M(z_1))| = z_1 - 1</math>
• 2D mřížka: <math>|E(M(z_1, z_2))| = (z_1 - 1)\cdot z_2 + z_1 \cdot (z_2 - 1)</math>
• 3D mřížka: <math>|E(M(z_1, z_2, z_3))| = [(z_1 - 1)\cdot z_2 + z_1 \cdot (z_2 - 1)] \cdot z_3 + z_1 \cdot z_2 \cdot (z_3 - 1)</math>
• nD mřížka rekurzivně: <math>|E(M(z_1…z_n))| = |E(M(z_1…z_{n-1}))| \cdot z_n + |V(M(z_1…z_{n-1}))| \cdot (z_n -1)</math>

Pro zadání M(11, 6, 13) je tedy počet hran: (10 * 6 + 11 * 5) * 13 + 11 * 6 * 12 = 2287

Bisekční šířka je minimální počet hran, které je třeba odebrat aby se graf rozpadl na 2 stejné poloviny (rozdělit počty uzlů takto: <math> \left \lfloor \frac{N}{2} \right \rfloor + \left \lceil \frac{N}{2} \right \rceil</math>)

Pokud je <math>max_{i}(z_i)</math> sudé, tak <math>b_{we}=\prod_{j\ne i}{z_j}</math>.
V opačném případě je přesně možné určit <math>b_{we}</math> pro 3D mřížku.

Tady trochu lépe nakreslené:

Pozn.: Je to trochu magie. Chápu to tak, že prostě řežu napůl, dokud nenarazim na hranu o sudé velikosti, která už to rozdělení udělá rovnoměrně. Tzn. kdyby ta 3. hrana nebyla velikosti 6, ale třeba 7, tak budu muset dělat ještě další výběžek. Ale třeba kdyby 2. hrana nebyla velikosti 11, ale třeba 10, tak bych už ten třetí výběžek dělat nemusel? Jo a asi se postupuje tak, že se vždycky vysunuje tam, kam se v předchozím řezu dalo míň.

Každopádně mi to přijde celý trochu divný, protože bisekční šířka má rozdělovat uzly na N/2 dolní a N/2 horní (tzn. rozdíl max. o jedničku a to tady IMHO nevychází, zkuste si to vynásobit. Ale jiný řešení mě nenapadá, tak asi ok. – Musíš nějak ukázat, co přesně ti nevychází, jinak je to trochu výkřik do tmy. A ono to vychází. Rozřízneš největší (z) stranu nejlíp, jak to jde, ale zbyde ti v jedné “půlce” o obdélník xy více uzlů než v druhé. Tak ten řez ohneš tak, aby se ti ještě tento obdélník rozříznul nejlépe, jak to jde, podle druhé největší strany (y). Nyní máš v jedné půlce o úsečku délky x více uzlů, než v druhé. Tak na závěr ještě uděláš jeden malý ohyb, abys rozřízl tuto úsečku nejlíp, jak to jde. Pak už bude mít jedna půlka grafu maximálně o jeden uzel více než druhá.

Důležité je taky uvědomit si, že ten souvislý řez, tak jak je na obrázcích, neprochází uzly, nýbrž hranami. Uzly jsou naopak všude na obou jeho stranách. Není špatný nápad si na svém obrázku kolem toho řezu okolní uzly a hrany mezi nimi všechny jinou barvou nakreslit. Je pak lépe vidět, co se vlastně deje. Ale pro samotný výpočet je nejlepší postupovat tak, jak je hezky zobrazeno na tříkrokovém obrázku níže a popsáno o odstavec výše.

Jiný pohled na <math>M(9,7,5)</math>

Bisekční šířka 3D mřížky obecně pro libovolné hodnoty (tak jak ji odvodili experimentálně Pavel&Michal © 2007):

Nechť <math>x < y < z</math>, <math>{L}</math> značí lichou a <math>{S}</math> sudou velikost, pak:

• <math>*LL</math> → <math>b_{we}=xy+x+1</math>
• <math>*SL</math> → <math>b_{we}=xy+x</math>
• <math>S</math> → <math>b_{we}=xy</math> Pozn.: Tvrdík to stejně bude chtít nejspíše nakreslit, ale pro kontrolu to může být dobré.
  ====== Teorie ====== ===== Je zabalený motýlek wBFn bipartitní graf? ===== Je, a případně za jakých podmínek, zabalený motýlek wBFn bipartitní graf? Svoji odpověď konstrukčně dokažte. ★ Bylo ve zkoušce: 2012-01-03 ==== Řešení ==== Viz skripta EN [2009] str. 46 nebo FIT [2012] přednáška 4 slide 35 wBFn je bipartitní pokud je n sudé. Důkaz: Jednodušší vysvětlení (plech.d): Prosím, je to opravdu snadné. Uzly v wBFn se skládají ze dvou složek, jedna určuje umístění na kružnici, čili řekněme řádek, druhá určuje, na které kružnici jsme, čili sloupec. Zkuste se na ty dvě složky dívat zcela odděleně. Vezmeme-li v úvahu jen první složku, jen řádky, pak jdou oba druhy hran v motýlkovi vlastně stejně, podíváte-li se na definici hran, první složka je u obou druhů hran vždy x+1 mod n. Motýlek se nám tedy z hlediska sloupců “splácne” do jedné kružnice, po které všechny hrany běhají pěkně postupně dokolečka. Z toho plyne, že stačí obarvit všechny sloupce stejně a jediná podmínka je, aby n bylo sudé, aby se na těch kružnicích mohly ty dvě barvy správně střídat. Vše lze odvodit ze zápisu množiny hran v wBFn. (slajd p4.34). Každá hrana vede mezi uzly s různou paritou i (různé “stupně” motýlka). Jedinou výjimkou jsou hrany které dotváří kružnice a to v případě, že dimenze n je lichá. Pak totiž například pro n=3 máme i = 0,1,2 a hranu mezi 2 a 0 (2 + 1 mod 3 = 0). V takovém případě není možné vytvořit bipartitní barvení. Z toho plyne i triviálně bipartita oBFn - nemá onu “kružnicovou” hranu. PS: snad je to dobře. Nevím co myslí “konstrukčním důkazem” ale tohle by snad mohlo stačit. PS2. Osobne bych tam nakreslis ten obrazek ze skript - kytku, z toho je to dobre videt. PS3. Konstrucni dukaz je takovy, ktery dokaze takovy graf zkonstruovat. Tedy pro liche to nejde viz. vyse. Pro sude to lze a to nasledujici uvahou. V SUDEM wBFn existuji hrany pouze takove, ze kdyz prechazis z uzlu (i, b) do jineho uzlu, tak se i vzdy zvysi nebo snizi o (i+1)mod n nebo o (i-1)mod n. Tedy pokud bylo i sude, pak se stane liche a naopak. Pak uz staci vsechny uzly, ktere maji i sude obarvit cervene a ty ktere maji i liche modre. Dodatek by voho: Tady jsou obrázky pro představu - bipartitní jsou pouze “sudí motýlkové” wBF a všechny motýlky oBF. PS4: Vsechno co je tu uvedene se urcite mota kolem spravne odpovedi, ale nejsem si jist, jestli cokoliv z vyse uvedeneho je konstrukcni dukaz. To, ze graf neni bipartitni IMHO dokazu kontrukcne tak, ze v nem sestavim kruznici liche delky. Jeden krok po libovolne hrane znamena, ze menim paritu prvni souradnice uzlu. Jedinou vyjimkou je situace, kdy prechazim z uzlu (n-1) do uzlu 0, kdy se parita nemeni prave tehdy, kdyz je n liche. Teto informace vyuziju tedy takto: - V pripade lichych n se proste projdu po jedne kruznici dokola ⇒ mam kruznici liche delky ⇒ wBFn neni pro licha n bipartitni. - V pripade sudych n to znamena, ze se nemohu na lichy pocet kroku dostat do uzlu, jehoz prvni souradnice ma stejnou paritu jako prvni souradnice vychoziho uzlu ⇒ nemohu sestavit kruznici liche delky ⇒ wBFn je pro suda n bipartitni ===== Definujte uzlovou symetrii a dokažte, že je K(z1,z2) uzlově symetrický ===== ★ Bylo ve zkoušce: 2013-01-02 ==== Řešení ==== Uzlově symetrický graf: Daný graf G je uzlově symetrický právě tehdy, když pro libovolnou dvojici uzlů u a v existuje automorfismus, který zobrazí u na v. _{[cs skripta 2006 str. 54]} Důkaz vychází z toho, že kružnice je uzlově symetrická – přeložení <math>\normalsize k_1 = k_1 (+)_n ( k_2 (-)_n k_1 )</math> (nebo znázorněte na obrázku) – a že <math>\normalsize K(z_1,z_2) = K(z_1) \times K(z_2)</math>, přičemž kartézský součin zachovává uzlovou symetrii. Viz také podobný příklad Uzlová a hranová symetrie 3D toroidu. === Důkaz že kartézský součin zachovává uzlovou symetrii === Podle záznamu 5. prosemináře. Uzlově symetrický graf <math>{G}</math> je takový, ve kterém pro všechny libovolné dva uzly existuje automorfismus, který je zobrazí na sebe; <math>\forall a, b \in V_{\tiny G} \: \exists f: \: V_{\tiny G} \to^{\small \text{autom.}} V_{\tiny G} : \: f(a) = b</math> Kartézský součin dvou grafů <math>{G}</math> a <math>{H}</math> je definovaný takto: <math>V_{\tiny{G \times H}} = V_{\tiny G} \times V_{\tiny H} = \left{ (a_{\tiny G}, a_{\tiny H}), \: a_{\tiny G} \in V_{\tiny G},\: a_{\tiny H} \in V_{\tiny H} \right}</math> (1) <math>E_{\tiny G \times H} = \left{ \left\langle (a_{\tiny G}, w),\: (b_{\tiny G}, w)\: \right\rangle,\: \left\langle a_{\tiny G}, b_{\tiny G} \right\rangle \in E_{\tiny G},\: w \in V_{\tiny H} \right} \cup \left{ \left\langle (z, a_{\tiny H}),\: (z, b_{\tiny H})\: \right\rangle,\: \left\langle a_{\tiny H}, b_{\tiny H} \right\rangle \in E_{\tiny H},\: z \in V_{\tiny G} \right} </math> (2) Musíme tedy dokázat, že: <math>\forall (a_{\tiny G}, a_{\tiny H}),\: (b_{\tiny G}, b_{\tiny H}) \in V_{\tiny G \times H} \: \exists f: \: V_{\tiny G \times H} \to^{\small \text{autom.}} V_{\tiny G \times H}: \: f[ (a_{\tiny G}, a_{\tiny H}) ] = (b_{\tiny G}, b_{\tiny H})</math> Předpokládáme, že platí: <math>f[ (a_{\tiny G}, a_{\tiny H}) ] = [ f_{\tiny G} (a_{\tiny G}), f_{\tiny H} (a_{\tiny H}) ] = (b_{\tiny G}, b_{\tiny H})</math> A to ověříme tak, že dokážeme platnost automorfismu na <math>\normalsize G \times H</math>, tedy že každé dva původně sousední uzly zůstávají sousední a žádné nové uzly nepřibyly. <math>\forall e_1 = \left\langle (a_{\tiny G}, w), (b_{\tiny G}, w)\: \right\rangle,\: {\small\text{kde}} \: \langle a_{\tiny G}, b_{\tiny G} \rangle \in E_{\tiny G},\: w \in V_{\tiny H}</math> <math>f(e_1) = \left\langle f(a_{\tiny G}, w),\: f(b_{\tiny G}, w) \right\rangle = \left\langle [ f_{\tiny G}(a_{\tiny G}), f_{\tiny H}(w) ],\: [ f_{\tiny G}(b_{\tiny G}), f_{\tiny H}(w) ] \right\rangle = e_2</math> Jelikož platí: <math>\left\langle f_{\tiny G}(a_{\tiny G}), f_{\tiny G}(b_{\tiny G}) \right\rangle \in E_{\tiny G}</math> a zřejmě <math>f_{\tiny H}(w) = f_{\tiny H}(w)</math> Tak jsme dokázali, že: <math>f(e_1) = e_2 \in E_{\tiny G \times H}</math> Správně bychom ještě měli ověřit platnost i pro druhou složku (2), postup bude stejný, pouze se prohází indexy. ==== Řešení 2 – přímé ==== Tento důkaz je konstruován přímo na základě triviální hypotézy o vzorečku pro automorfismus: <math> f_{u,v}¹⁾ = (x_1 \oplus_{z_1} ( v_1 \ominus_{z_1} u_1 ), x_2 \oplus_{z_2} ( v_2 \ominus_{z_2} u_2) ) </math> Kde <math>(x_1, x_2)</math> jsou složky uzlu <math>x</math> a <math>\oplus_{a}</math> je binární komutativní operace sčítání modulo <math>a</math>. Je to skutečně automorfismus? Musí zachovávat sousednost. To znamená, že obraz každého mého souseda se musí rovnat sousedovi obrazu mého. První cesta tedy hledá obrazy sousedů uzlu x. Předpokládejme, že souřadnice souseda jsou o <math>\delta_x_1</math> a <math>\delta_x_2</math> jiné, než mé. <math>\delta</math> je z množiny <math>\{ -1, 0, 1 \}</math>, to ale nehraje roli. Obraz mého souseda bude mít souřadnice: <math> f_{u,v}²⁾ = (x_1 \oplus_{z_1} \delta_x_1 \oplus_{z_1} ( v_1 \ominus_{z_1} u_1 ), x_2 \oplus_{z_2} \delta_x_2 \oplus_{z_2} ( v_2 \ominus_{z_2} u_2) ) </math> Druhá cesta hledá sousedy mého obrazu. Cílem je, aby se výše a níže uvedený vzorec pro cílový uzel rovnaly. Výraz pro souseda mého obrazu je: <math> (x_1 \oplus_{z_1} ( v_1 \ominus_{z_1} u_1 ) \oplus_{z_1} \delta_x_1, x_2 \oplus_{z_2} ( v_2 \ominus_{z_2} u_2) \oplus_{z_2} \delta_x_2 ) </math> Díky komutativitě operace sčítání resp. odčítání modulo jsou si výrazy rovny a hypotéza je dokázána. ===== Co je to e-cube směrování ===== Co je to e-cube směrování a proč nemůže při WH na hyperkrychli s e-cube směrováním více paketů dojít k jejich zablokování? ==== Řešení ==== Viz CZ skripta [2006] str. 61, EN skripta str. 86 E-cube je minimální směrování na hyperkrychli. Cestu mezi uzly u a v konstruujeme tak, že porovnáme uzly u a v od LSB k MSB (nejméně významného bitu k tomu nejvíce významnému). Pokud se u a v liší v bitu i, cesta se rozšíří o hranu v dimenzi i ⇒ délka minimální cesty je určena počtem bitů, ve kterých se uzly u a v** liší.

Je odolné vůči zablokování, protože cesta se konstruuje ve směru rostoucí dimenze. Tím nemůže dojít k vytvoření cyklu, protože cesta blokující hrany vyšší dimenze nemůže žádat o hrany nižší dimenze.

<math>indBF</math> obousměrný, odvodit vztah pro průměrnou vzdálenost

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

trik je v tom ze indBfn je symetricky. Staci spocitat prumernou vzdalenost pomoci jedineho uzlu

EDIT: Nemáte někdo nějaký hint? Nedá se to počítat s negováním bitů, tzn. jako u hyperkrychle, takže by to pak bylo n/2?

luptarad: tak teoreticky takto: budem predpokladať, že vzdialenosť je počet hran po ktorých sa musí ísť.

1. pre BF1 (len 2 uzly a jeden prepinac): vzdialenosť prvého uzlu od druhého je 2
   1. (0 → prepinace0 → 1)
2. pre BF2 (4 uzly): vzdialenosti od jednoho uzlu sú: 1*2 a 2*4 (jeden uzol je vo vzdialenosti 2, 2 uzly sú vo vzdialenosti 4).
   1. (00 → prepinace0 → 01)
   2. (00 → prepinac0 → prepinac1 → prepinac0 → 11)
   3. (00 → prepinac0 → prepinac1 → prepinac0 → 10)
3. pre BF4 (16 uzlov): 1*2 + 2*4 + 4*6 + 8*8
   
   1. (0000 → prepinace0 → 0001)
   2. (0000 → prepinac0 → prepinac1 → prepinac0 → 0001)
   3. (0000 → prepinac0 → prepinac1 → prepinac0 → 0011)
   4. (0000 → prepinac0 → prepinac1 → prepinac2 → prepinac1 → prepinac0 → 0100)
   5. (0000 → prepinac0 → prepinac1 → prepinac2 → prepinac1 → prepinac0 → 0101)
   6. (0000 → prepinac0 → prepinac1 → prepinac2 → prepinac1 → prepinac0 → 0110)
   7. (0000 → prepinac0 → prepinac1 → prepinac2 → prepinac1 → prepinac0 → 0111)
   8. (0000 → prepinac0 → prepinac1 → prepinac2 → prepinac3 → prepinac2 → prepinac1 → prepinac0 → 1000)
   9. (0000 → prepinac0 → prepinac1 → prepinac2 → prepinac3 → prepinac2 → prepinac1 → prepinac0 → 1001)
   10. (0000 → prepinac0 → prepinac1 → prepinac2 → prepinac3 → prepinac2 → prepinac1 → prepinac0 → 1010)
   11. (0000 → prepinac0 → prepinac1 → prepinac2 → prepinac3 → prepinac2 → prepinac1 → prepinac0 → 1011)
   12. (0000 → prepinac0 → prepinac1 → prepinac2 → prepinac3 → prepinac2 → prepinac1 → prepinac0 → 1100)
   13. (0000 → prepinac0 → prepinac1 → prepinac2 → prepinac3 → prepinac2 → prepinac1 → prepinac0 → 1101)
   14. (0000 → prepinac0 → prepinac1 → prepinac2 → prepinac3 → prepinac2 → prepinac1 → prepinac0 → 1110)
   15. (0000 → prepinac0 → prepinac1 → prepinac2 → prepinac3 → prepinac2 → prepinac1 → prepinac0 → 1111)

celkom by sa to možno dalo spočítať ako: suma od i=1 do n: 2*i / 2^(i-1)

Edit: Souhlasím, je to <math>\sum_{i=1}^n (2^{i-1} 2 i) = \sum_{i=1}^n i 2^i</math>

teda vzdialenosti / počet uzlov na danej vzdialenosti

Edit: Součet vezmeme z každého uzlu (díky uzlové symetrii je vždy stejný) a vydělíme výsledek počtem všech uspořádaných dvojic (u,v). To je hledaná průměrná vzdálenost.

<math>\overline{dist}(indBFn) = \frac{2^n \sum_{i=1}^n i 2^i}{2^n(2^n - 1)} = \frac{\sum_{i=1}^n i 2^i}{2^n - 1}</math>

EDIT: Proč je počet uspořádaných dvojic (2 na n)-1? - Graf je uzlove symetricky, takže nám to stačí spočítat pro jeden konkrétní uzel (jinak bychom to museli násobit a dělit <math>2^n</math> abychom pocitali pro vsecky. Coz je zbytecne teda, nebot by se to vykratilo.

EDIT: Možná blbnu, ale jak jste přišli na to, že je indBFn uzlově symetrický? Vždyť ta struktura vychází z oBFn, jenom má místo uzlů přepínače. oBFn rozhodně uzlově symetrický neni ~ narozdíl od wBFn sou tu uzly s různými stupni. Díky tomu, pokud se nemýlim, nelze průměrnou vzdálenost odvodit pomocí generalizace z jednoho uzlu jako u Qn, ale musim brát v potaz všechny možné uzly. Teoreticky se tu nepohybuju po vnitřních uzlech ale asi mne zajímají jenom vzdálenosti vstup → libovolný výstup a ty jsou pravda vždycky stejné, ale vzhledem k tomu, že mám oboustrannýho motýlka si myslim, že mě zajímá i vstup → libovolný jiný vstup, tzn. tohle taky padá a nezbejvá než počítat.

Sorry, asi sem to zblbnul. U oboustranných indBFn bereme v potaz jenom vstup → jiný vstup, a z toho pohledu dost možná uzlově symetrické budou, upřímně nevim.

★ Bylo ve zkoušce: 2013-01-30

Odvodit počet nejkratších cest v obousměrném indBFn mezi uzly <math>u=u_{n-1}, u_{n-2}, … ,u_0 </math> a<math> v=v_{n-1}, v_{n-2}, … ,v_0</math>

Pro lepší představivost byl zadán obrázek, spočítat se to ale mělo obecně

ENG skripta 52, FIT přednáška 4 slide 46

Vyplývá z toho, že motýlek je rekurzivní struktura

i = index nejlevějšího bitu ve kterém se oba uzly liší

výsledek: <math>2^i</math>

např. uzly 01001 a 01101 se liší ve 2. bitu (indexuje se od 0) ⇒ <math>2^2</math>

EDIT: kulikdav: nerekl bych, zkus si uzly 000 a 100 na obrazku, podle tveho je jen 2^0 cest, ma to byt 2^(d-1) kde d je MSB ve kterem se lisi. uznal mi to tak za plno, ani necetl ten wall of text co jsem tam k tomu psal.V tech predchozich bitech je ti jedno jak to je ( jdes v tom strome do te d dimenze a zpatky takze vsechny nize se jdou 2x) at uz invertujes ( tedy 1x = a 1x X prepinac ) nebo neinvertujes ( 2x = nebo 2x X prepinac ) vzdy mas 2 moznosti, celkem co sem psal.

EDIT: bezy: podle mého výpočtu to vychází 2^2 protože se bity indexujou od LSB k MSB (zprava doleva) :) Tak jak sem to napsal výše mi také bylo uznáno za plno.

EDIT: takze medzi 000 a 001 je jedna cesta s delkou 2 (vede pres jeden prepinc) a mezi 000 a 100 su 4 cesty (2^2) cez 5 prepinacov - Pismenka znamenaji sloupec zleva pismenovano a cisla poradi smerovace cislovano od nuly

1. (000 → prepinacA0 → prepinacB0 → prepinaC0 → prepinaB2 → prepinaA2 → 100)
2. (000 → prepinacA0 → prepinacB0 → prepinaC2 → prepinaB2 → prepinaA2 → 100)
3. (000 → prepinacA0 → prepinacB1 → prepinaC1 → prepinaB3 → prepinaA2 → 100)
4. (000 → prepinacA0 → prepinacB1 → prepinaC3 → prepinaB3 → prepinaA2 → 100)