Kingsův graf - Kings graph - Wikipedia

Kingův graf
${ displaystyle 8 krát 8}$ králův graf
Vrcholy	${ displaystyle nm}$
Hrany	${ displaystyle 4nm-3 (n + m) +2}$
Obvod	${ displaystyle 3}$ když ${ displaystyle min (m, n)> 1}$
Chromatické číslo	${ displaystyle 4}$ když ${ displaystyle min (m, n)> 1}$
Chromatický index	${ displaystyle 8}$ když ${ displaystyle min (m, n)> 2}$
Tabulka grafů a parametrů

v teorie grafů, a králův graf je graf který představuje všechny legální pohyby král šachy kus na šachovnice kde každý vrchol představuje čtverec na šachovnici a každá hrana je legální tah. Přesněji řečeno, ${ displaystyle n krát m}$ královský graf je královským grafem ${ displaystyle n krát m}$ šachovnice.^[1] To je mapový graf vytvořené ze čtverců šachovnice vytvořením vrcholu pro každý čtverec a hranou pro každé dva čtverce, které sdílejí hranu nebo roh. Lze jej také zkonstruovat jako silný produkt ze dvou grafy cesty.^[2]

Pro ${ displaystyle n krát m}$ královský graf je celkový počet vrcholů ${ displaystyle nm}$ a počet hran je ${ displaystyle 4nm-3 (n + m) +2}$. Za čtverec ${ displaystyle n krát n}$ královský graf, celkový počet vrcholů je ${ displaystyle n ^ {2}}$ a celkový počet hran je ${ displaystyle (2n-2) (2n-1)}$.^[3]

The sousedství vrcholu v králově grafu odpovídá Moore sousedství pro mobilní automaty.^[4]Zobecnění královského grafu, zvaného a kinggraph, je tvořen z a squaregraph (rovinný graf, ve kterém každá ohraničená plocha je čtyřúhelník a každý vnitřní vrchol má nejméně čtyři sousedy) přidáním dvou úhlopříček každé čtyřúhelníkové plochy čtvercového grafu.^[5]

Viz také

• Rytířský graf
• Rookův graf
• Příhradový graf

Reference