Wykres królowej

Wykres królowej
Wykres królowej
7	7
6	6
5	5
4	4
3	3
2	2
1	1
Wierzchołki
Liczba chromatyczna	n jeśli
Nieruchomości	Podwójnie spójny , hamiltonian
	Tabela wykresów i parametrów

W matematyce wykres hetmana to wykres przedstawiający wszystkie dozwolone ruchy hetmana — figury szachowej — na szachownicy . Na wykresie każdy wierzchołek reprezentuje kwadrat na szachownicy, a każda krawędź to legalny ruch, jaki może wykonać królowa, czyli ruch poziomy, pionowy lub ukośny o dowolną liczbę pól. Jeśli szachownica ma wymiary $indukowany$ wykres nazywa ${\ Displaystyle m \ razy n}$ wykres królowej.

Niezależne zestawy wykresów odpowiadają rozmieszczeniu wielu hetmanów, w których żadne dwie hetmany nie atakują się nawzajem. Są badane w $ośmiu$ hetmanów , w którym nieatakujących hetmanów jest umieszczanych na standardowej . Zestawy dominujące reprezentują układy hetmanów, w których każde pole jest atakowane lub zajmowane przez hetmana; pięć królowych $, ale nie$ , może szachownicę

Kolorystyka wykresów przedstawia sposoby pokolorowania każdego kwadratu, tak aby hetman nie mógł poruszać się między dowolnymi dwoma kwadratami tego samego koloru; do $szachownicy$ potrzebnych jest $szachownicy potrzebnych$ najmniej kolorów do .

Nieruchomości

istnieje cykl Hamiltona , a grafy są połączone dwukierunkowo (pozostają połączone , jeśli usunie się dowolny pojedynczy wierzchołek). Szczególne przypadki wykresów królowej i $\$ { $displaystyle 2 \ razy 2$ }

Niezależność

	A	B	C	D	mi	F	G	H
8									8
7									7
6									6
5									5
4									4
3									3
2									2
1									1
	A	B	C	D	mi	F	G	H

Niezależny zestaw o rozmiarze 8 na

takie

zestawy z konieczności również dominują)

Niezależny zestaw wykresu odpowiada umieszczeniu kilku hetmanów na szachownicy w taki sposób, że żadne dwie hetmany nie atakują się nawzajem. Na $n wierzchołków$ niezależny zestaw zawiera co najwyżej , ponieważ żadne dwie królowe nie mogą znajdować się w tym samym rzędzie lub kolumnie Tę górną granicę można osiągnąć dla wszystkich n z wyjątkiem n = 2 i n = 3. W przypadku n=8 jest to tradycyjna łamigłówka z ośmioma hetmanami.

Dominacja

Dominujący zestaw wykresu hetmana odpowiada takiemu umieszczeniu hetmanów, że każde pole na szachownicy jest albo atakowane, albo zajmowane przez hetmana. 8 ${\ Displaystyle 8 \ razy 8$ szachownicy, pięć hetmanów może dominować i jest to minimalna możliwa liczba (cztery hetmany pozostawiają co najmniej dwa pola bez ataku). Takich położeń pięciu hetmanów jest 4860, w tym takie, w których hetmany kontrolują również wszystkie zajęte pola, czyli atakują lub bronią się nawzajem. W tej podgrupie są też pozycje, w których hetmany zajmują pola tylko na głównej przekątnej (np. od a1 do h8) lub wszystkie na podprzekątnej (np. od a2 do g8).

	A	B	C	D	mi	F	G	H
8									8
7									7
6									6
5									5
4									4
3									3
2									2
1									1
	A	B	C	D	mi	F	G	H

Dominujący (i niezależny) zestaw w rozmiarze 5.

	A	B	C	D	mi	F	G	H
8									8
7									7
6									6
5									5
4									4
3									3
2									2
1									1
	A	B	C	D	mi	F	G	H

Zestaw dominujący na głównej przekątnej.

	A	B	C	D	mi	F	G	H
8									8
7									7
6									6
5									5
4									4
3									3
2									2
1									1
	A	B	C	D	mi	F	G	H

Dominujący zestaw na podprzekątnej.

$torusem$ poprzez zastąpienie niezapętlonej prostokątnej lub walcem zmniejsza minimalny rozmiar zestawu dominującego do czterech

Kwadraty kropkowane sąsiadują ze środkowym kwadratem. 8 niesąsiadujących ze sobą kwadratów sąsiaduje ze sobą na odpowiednim wykresie skoczka .

Wykres królowej ${\ displaystyle 3 \ razy 3}$ jest zdominowany przez pojedynczy wierzchołek na środku planszy. Środkowy wierzchołek $wykresu$ królowej przylega do wszystkich wierzchołków z wyjątkiem 8: tych , które sąsiadują ze środkowym wierzchołkiem wykresu rycerskiego $Displaystyle 5 \ razy 5$ .

Liczby dominacji

Zdefiniuj liczbę dominacji d ( n ) $wykresu$ hetmana jako rozmiar najmniejszego zestawu dominującego, a przekątną liczbę dominacji ) jako rozmiar najmniejszego zestawu dominującego zbiór będący podzbiorem długiej przekątnej. Zauważ, że ${\ Displaystyle d (n) \ równoważnik dd (n)}$ dla wszystkich n . Granica jest osiągnięta dla $\ Displaystyle d (8) = dd (8) = 5}$ , ale nie dla ${\ Displaystyle d (11 )=5,dd(11)=7}$ .

Liczba dominacji jest liniowa w n , z granicami określonymi przez:

{\ Displaystyle {\ Frac {n-1} {2}} \ równoważnik d (n) \ równoważnik n- \ lewo \ lfloor {\ Frac {n} {3}} \ prawo \ rfloor.}

Początkowe wartości re ( n ) dla ${\ Displaystyle n = 1,2,3, \ kropki}$ , to 1, 1, 1, 2, 3, 3, 4, 5, 5, 5, 5 (sekwencja A075458 w OEIS ).

Niech K _n $_$ rozmiarem podzbioru każda i trzy liczby tworzą ciąg arytmetyczny (zbiór jest „bez punktu środkowego”). Ukośna $hetmana$ to ${\ displaystyle n-K_ {n}}$ .

identyfikator niezależnej dominacji ( n ) jako rozmiar najmniejszego niezależnego, dominującego zestawu na wykresie królowej ${\ displaystyle n \ razy n} .$ Wiadomo, że ${\ Displaystyle ID (n) <0,705n + 0,895}$ .

Kolorowanie

9- kolorowanie wykresu królowej

{\ displaystyle 8 \ razy 8} .

Zauważ, że każda para pól tego samego koloru nie znajduje się w tym samym szeregu, linii lub przekątnej, więc hetman nie może poruszać się bezpośrednio między kwadratami.

Kolorowanie grafu królowej to przypisanie kolorów do każdego wierzchołka w taki sposób, że żadne dwa sąsiednie wierzchołki nie mają tego samego koloru . Na przykład, jeśli a8 jest pokolorowane na czerwono, to żadne inne pole na linii a , ósmym rzędzie lub długiej przekątnej nie może być pokolorowane na czerwono, ponieważ hetman może przemieścić się z pola a8 na dowolne z tych pól. Liczba chromatyczna wykresu to najmniejsza liczba kolorów, których można użyć do jego pokolorowania.

W przypadku $wykresu królowej$ co najmniej n kolorów, ponieważ w rankingu lub pliku wymaga innego koloru (tj. wiersze i kolumny to kliki ). Liczba chromatyczna wynosi dokładnie n , jeśli $)$ tj. jest niż

Liczba chromatyczna $wykresu$ 9

Nieredundancja

Zbiór wierzchołków jest zbędny, jeśli usunięcie dowolnego wierzchołka ze zbioru zmienia sąsiedztwo zbioru , tj. dla każdego wierzchołka istnieje sąsiedni wierzchołek, który nie sąsiaduje z żadnym innym wierzchołkiem w zbiorze. Odpowiada to zestawowi królowych, z których każda w unikalny sposób kontroluje co najmniej jedno pole. Maksymalny rozmiar $wykresie$ ( n ) zbędnego zestawu na królowej jest trudny do znane wartości obejmują ${\ Displaystyle IR (5) = 5, IR (6) = 7, IR (7) = 9, IR ( 8)=11.}$

Gra pościg – unik

Rozważ grę pościg-unik na $wykresie$ hetmana rozgrywaną zgodnie z następującymi zasadami: biały hetman zaczyna w jednym rogu, a czarny hetman w Gracze naprzemiennie poruszają się, które polegają na przesunięciu hetmana do sąsiedniego wierzchołka, do którego można dotrzeć bez przechodzenia (poziomo, pionowo lub ukośnie) lub lądowania na wierzchołku sąsiadującym z przeciwległym hetmanem. Ta gra może być wygrana przez białe ze strategią parowania .

Zobacz też