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\}\).

Obtížnost: Středně těžká úloha
Úloha vyžadující neobvyklý trik nebo nápad
En translation
	Zaslat komentář k úloze