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.