Kungens graf

Kungens graf
$8\ gånger 8$ kungens graf
Vertices	$nm$
Kanter	$4nm-3(n+m)+2$
Omkrets	$3$ när $\min(m,n)>1$
Kromatiskt nummer	$4$ när $\min(m,n)>1$
Kromatiskt index	$8$ när $\min(m,n)>2$
Tabell över grafer och parametrar

I grafteorin är en kungsgraf en graf som representerar alla lagliga drag av kungens schackpjäs på ett schackbräde där varje hörn representerar en ruta på ett schackbräde och varje kant är ett lagligt drag . Mer specifikt är en $n\times m$ kungskurva en kungsgraf av ett $n\times m$ schackbräde. Det är kartdiagrammet bildas av rutor på ett schackbräde genom att göra en vertex för varje ruta och en kant för varje två rutor som delar en kant eller ett hörn. Den kan också konstrueras som den starka produkten av tvåvägsgrafer .

För en $n\times m$ kungskurva är det totala antalet hörn $nm$ och antalet kanter är $4nm -3(n+m)+2$ . För en kvadrat $n\times n$ kungens graf förenklar detta så att det totala antalet hörn är $n^{2}$ och det totala antalet kanter är $(2n-2)(2n-1)$ .

Området för en vertex i kungens graf motsvarar Moore-området för cellulära automater. En generalisering av kungens graf, kallad en kunggraf , bildas från en kvadratgraf (en plan graf där varje avgränsad yta är en fyrhörning och varje inre vertex har minst fyra grannar) genom att addera de två diagonalerna för varje fyrsidig yta på kvadratgrafen .

I ritningen av en kungsgraf som erhållits från ett $n\times m$ schackbräde finns det $(n-1)(m-1)$ korsningar , men det är möjligt att få en ritning med färre korsningar genom att förbinda de två närmaste grannarna till varje hörnruta med en kurva utanför schackbrädet istället för med ett diagonalt linjesegment. På detta sätt, $(n-1)(m-1)-4$ korsningar är alltid möjliga. För kungens graf över små schackbräden leder andra teckningar till ännu färre korsningar; i synnerhet varje $2\times n$ är kungens graf en plan graf . Men när både $n$ och $m$ är minst fyra, och de båda inte är lika med fyra, $(n-1)(m-1)-4$ är ​​det optimala antalet korsningar.

Se även

• Riddarens graf
• Drottningens graf
• Rooks graf
• Biskopens graf
• Gitterdiagram
•  Schackportal