Graf Kinga

Wykres króla
${\ Displaystyle 8 \ razy 8}$ wykres króla
Wierzchołki	${\ displaystyle nm}$
Krawędzie	${\ Displaystyle 4nm-3 (n + m) + 2}$
Obwód	${\ Displaystyle 3}$ , kiedy ${\ Displaystyle \ min (m, n)> 1}$
Liczba chromatyczna	${\ Displaystyle 4}$ , kiedy ${\ Displaystyle \ min (m, n)> 1}$
Indeks chromatyczny	${\ Displaystyle 8}$ , kiedy ${\ Displaystyle \ min (m, n)> 2}$
Tabela wykresów i parametrów

W teorii grafów graf króla to wykres przedstawiający wszystkie legalne ruchy figury szachowej króla na szachownicy , gdzie każdy wierzchołek reprezentuje kwadrat na szachownicy, a każda krawędź jest legalnym ruchem. Dokładniej, $m}$$razy$ { \ To jest wykres mapy utworzona z kwadratów szachownicy przez utworzenie wierzchołka dla każdego kwadratu i krawędzi dla każdych dwóch kwadratów, które mają wspólną krawędź lub róg. Można go również skonstruować jako silny iloczyn dwóch wykresów ścieżkowych .

W przypadku ${\ displaystyle nm$ całkowita liczba wierzchołków wynosi $}$ , a liczba krawędzi wynosi $\ displaystyle 4nm -3(n+m)+2}$ . W przypadku kwadratu $króla upraszcza się to$ że całkowita liczba wierzchołków wynosi ${\ displaystyle n ^ {2}}$ a całkowita liczba krawędzi wynosi ${\ Displaystyle (2n-2) (2n-1)}$ .

Sąsiedztwo wierzchołka w grafie króla odpowiada sąsiedztwu Moore'a dla automatów komórkowych. Uogólnienie wykresu króla, zwane wykresem królewskim , jest tworzone z wykresu kwadratowego (wykresu planarnego, w którym każda ograniczona ściana jest czworobokiem, a każdy wierzchołek wewnętrzny ma co najmniej czterech sąsiadów) przez dodanie dwóch przekątnych każdej czworobocznej ściany wykresu kwadratowego .

Na rysunku wykresu króla uzyskanym z $szachownicy$ są $-1)}$ - 1) ( , ale możliwe jest uzyskanie rysunku z mniejszą liczbą przecięć , łącząc dwóch najbliższych sąsiadów każdego kwadratu narożnego za pomocą krzywej poza szachownicą zamiast ukośnego odcinka linii. W ten sposób ${\ Displaystyle (n-1) (m-1) -4}$ zawsze są możliwe. W przypadku królewskiego wykresu małych szachowni inne rysunki prowadzą do jeszcze mniejszej liczby skrzyżowań; w szczególności $wykres$ jest wykresem planarnym Jednakże, gdy zarówno $\ displaystyle n},$ jak i $wynoszą$ co najmniej cztery, a nie oba są równe czterem, ${\ Displaystyle (n-1) (m-1) -4}$ to optymalna liczba skrzyżowań.

Zobacz też

• Wykres rycerza
• Wykres królowej
• Wykres Wieży
• Wykres biskupa
• Wykres kratowy
•  Portal szachowy