Wykres biskupa
W matematyce wykres biskupa to wykres przedstawiający wszystkie legalne ruchy pionka szachowego gońca na szachownicy . Każdy wierzchołek reprezentuje pole na szachownicy, a każda krawędź reprezentuje legalny ruch gońca; to znaczy, istnieje krawędź między dwoma wierzchołkami (kwadratami), jeśli zajmują one wspólną przekątną. szachownica ma wymiary indukowany wykres
Nieruchomości
Fakt, że szachownica ma kwadraty dwóch kolorów, powiedzmy czerwonego i czarnego, tak że kwadraty sąsiadujące poziomo lub pionowo mają przeciwne kolory, oznacza, że graf gońca ma dwa połączone elementy, których zbiorami wierzchołków są kwadraty czerwone i czarne, odpowiednio. Powodem jest to, że ukośne ruchy gońca nie pozwalają mu na zmianę kolorów, ale jednym lub kilkoma ruchami goniec może przejść z dowolnego pola na inne w tym samym kolorze. Te dwa składniki są izomorficzne, jeśli plansza ma bok o parzystej długości, ale nie, jeśli oba boki są nieparzyste.
Składnik wykresu gońca można traktować jako wykres wieży na karo, jeśli oryginalna szachownica jest kwadratowa, ponieważ jeśli czerwone kwadraty (powiedzmy) zostaną obrócone o 45 stopni, ruchy gońca staną się poziome i pionowe, tak jak ruchy wieży .
Dominacja
Mówi się, że pole jest atakowane przez gońca, jeśli goniec może dostać się na to pole dokładnie jednym ruchem. Zestaw dominujący to taki układ gońców, że każde pole jest atakowane lub zajmowane przez jednego z tych gońców. Niezależny zestaw dominujący to zestaw dominujący, w którym żaden goniec nie atakuje żadnego innego. Minimalna liczba gońców potrzebnych do zdominowania kwadratowej planszy o boku n wynosi dokładnie n i jest to również najmniejsza liczba gońców, która może utworzyć niezależny zestaw dominujący. Z kolei zestaw totalnej dominacji, który jest zestawem dominującym, w którym każde pole, w tym te zajmowane przez gońce, jest atakowane przez jednego z gońców, wymaga większej liczby gońców; kwadratowej n całego _ 1/3 większy niż minimalny zestaw dominujący.
