Souvislost konkrétních grafů

Úloha číslo: 3814

Určete vrcholovou a hranovou souvislost následujících grafů:

  • Varianta

    Stromů.

  • Varianta

    Cyklů a jejich doplňků.

  • Varianta

    Úplných bipartitních grafů \(K_{m,n}\).

  • Varianta

    Platónských těles.

  • Varianta

    Hyperkrychle \(Q_d\) dimenze \(d\).

    Vrcholy \(Q_d\), jehož vrcholy jsou všechny posloupnosti \(d\) nul a jedniček a dva vrcholy jsou spojené hranou, pokud se jejich posloupnosti liší na právě jedné pozici.

  • Varianta

    Toroidní mřížky \(T_d(n)\) dimenze \(d\) pro \(n\gg d\).

    Vrcholy \(T_d(n)\) jsou \(d\)-složkové vektory nad tělesem \(Z_n\). Dva vektory jsou spojené hranou, má-li jejich rozdíl v právě jedné složce \(\pm 1\) a všude jinde nuly.

    \(T_1(n)\) je tedy kružnice na \(n\) vrcholech, \(T_2(n)\) je mřížka \(n\times n\) s levým okrajem slepeným s pravým a horním slepeným s dolním.

Obtížnost: Snadná úloha (řešená úvahou nebo přímo z definic)
Úloha na dokazování, ověřování
En translation
	Zaslat komentář k úloze