---
# System prepended metadata

title: Domácí úkol 5.2 - ddim

---

# Domácí úkol 5.2 - ddim
## Průměrný stupeň:
Sousední vrchol má právě jednu souřadnici změněnou. Změnit mohu $d$ souřadnic a každou přávě jedním způsobem ($0$ - $1$), takže každý vrchol má $d$ sousedů, což je zároveň průměrný stupeň.
## Počet vrcholů:
Každá souřadnice existuje ve dvou podobách ($0$ nebo $1$), a jelikož na jejich pořadí záleží, dostávám variace s opakováním - $2^d$.
## Počet hran:
Existuje $2^d$ vrcholů, každý má stupeň $d$, počet hran je poloviční oproti celkovému součtu stupňů vrcholů. Celkem je jich tedy $\frac{2^d * d}{2} = d*2^{d-1}$.
## Délka nejkratší kružnice:
Kružnici délky 4 mohu poskládat z vrcholů $\{0,0,...\},\{0,1,...\},\{1,1,...\},\{1,0,...\}$ (ostatní souřadnice jsou stejné).
Teoreticky nejkratší kružnice by mohla mít 3 vrcholy, ne ovšem v tomto případě (např. vrcholy $\{1,0,...\}$ a $\{0,1,...\}$ spolu nesousedí, takže nelze vést hranu "napříč" kružnicí.
## Délka nejdelší ind. cesty