Konstrukce regulárních grafů
Úloha číslo: 3625
Pro každá dvě přirozená čísla \(k,n\) taková, že \(k<n\) a součin \(kn\) je sudý, najděte příklad \(k\)-regulárního grafu na \(n\) vrcholech.
Nápověda
Zaměřte se nejprve na sudá \(k=2{,}4,…\)
Řešení
Uvědomte si nejprve, že obě podmínky jsou nutné: Maximální stupeň v grafu na \(n\) vrcholech je \(n-1\). Dále, z principu sudosti nemůže existovat graf na lichém počtu vrcholů, kde by všechny stupně byly liché.
Pro konstrukci zvolme \(V_G=\{1,…,n\}\).
Je-li \(k\) sudé, spojíme hranou vrcholy, jejichž čísla se liší nejvýše o \(\frac{k}2\), formálně \(E_G=\{(u,v): |u-v|\le \frac{k}2\}\).
Je-li \(k\) liché, potom \(n\) je sudé. Hranou spojíme vrcholy, jejichž čísla se liší nejvýše o \(\frac{k-1}2\) (tyto přidají každému vrcholu \(k-1\) sousedů) nebo právě o \(\frac{n}2\) (protilehlé vrcholy). Formálně \(E_G=\{(u,v): |u-v|\le \frac{k-1}2 \vee |u-v|=\frac{n}2\}\).