Drottningens graf

Drottningens graf
a b c d e f g h 8 8 7 7 6 6 5 5 4 4 3 3 2 2 1 1 a b c d e f g h I en $8\times 8$ drottningsgraf är varje ruta på schackbrädet ovan en vertex . Det finns en kant mellan vilka två hörn som helst som en drottning kan röra sig mellan; som ett exempel är hörnen intill d4 markerade med en vit prick (dvs det finns en kant från d4 till varje markerad vertex).
Vertices	$mn$
Kromatiskt nummer	n om $m=n\equiv 1,5{\pmod {6}}$
Egenskaper	Biconnected , Hamiltonian
Tabell över grafer och parametrar

I matematik är en drottningsgraf en graf som representerar alla lagliga drag av drottningen - en schackpjäs - på ett schackbräde . I grafen representerar varje vertex en ruta på ett schackbräde, och varje kant är ett lagligt drag som drottningen kan göra, det vill säga ett horisontellt, vertikalt eller diagonalt drag med valfritt antal rutor. Om schackbrädet har dimensionerna $m\times n$ kallas den inducerade grafen för $m\times n$ drottningsgrafen.

Oberoende uppsättningar av graferna motsvarar placeringar av flera damer där inga två damer attackerar varandra. De studeras i pusslet med åtta damer , där åtta icke-attackerande damer placeras på ett standard $8\times 8$ schackbräde. Dominerande set representerar arrangemang av damer där varje ruta attackeras eller ockuperas av en dam; fem damer, men inte färre, kan dominera $8\times 8$ schackbrädet.

Färger på graferna representerar sätt att färglägga varje ruta så att en dam inte kan flytta mellan två rutor av samma färg; minst n färger behövs för ett $n\times n$ schackbräde, men 9 färger behövs för $8\times 8$ -brädet.

Egenskaper

Det finns en Hamilton-cykel för varje drottnings graf, och graferna är dubbelkopplade (de förblir sammankopplade om någon enda vertex tas bort). Specialfallen av $1\times n$ och $2\times 2$ drottningens grafer är kompletta .

Oberoende

	a	b	c	d	e	f	g	h
8									8
7									7
6									6
5									5
4									4
3									3
2									2
1									1
	a	b	c	d	e	f	g	h

En oberoende uppsättning av storlek 8 för ett $8\times 8$ schackbräde (sådana set är nödvändigtvis också dominerande).

Huvudartikel: Pussel med åtta drottningar

En oberoende uppsättning av grafen motsvarar en placering av flera damer på ett schackbräde så att inte två damer attackerar varandra. I ett $n\times n$ schackbräde innehåller den största oberoende uppsättningen högst n hörn, eftersom inga två damer kan vara i samma rad eller kolumn. Denna övre gräns kan uppnås för alla n utom n =2 och n =3. I fallet med n=8 är detta det traditionella pusslet med åtta damer.

Herravälde

En dominerande uppsättning av drottningens graf motsvarar en placering av damer så att varje ruta på schackbrädet antingen attackeras eller ockuperas av en dam. På ett $8\times 8$ schackbräde kan fem damer dominera, och detta är minsta möjliga antal (fyra damer lämnar minst två rutor oangripna). Det finns 4 860 sådana placeringar av fem damer, inklusive sådana där damerna kontrollerar också alla ockuperade rutor, dvs de attackerar respektive skyddar varandra. I den här undergruppen finns det också positioner där damerna endast upptar rutor på huvuddiagonalen (t.ex. från a1 till h8), eller alla på en subdiagonal (t.ex. från a2 till g8).

a b c d e f g h 8 8 7 7 6 6 5 5 4 4 3 3 2 2 1 1 a b c d e f g h En dominerande (och oberoende) uppsättning av storlek 5.

a b c d e f g h 8 8 7 7 6 6 5 5 4 4 3 3 2 2 1 1 a b c d e f g h En dominerande uppsättning på huvuddiagonalen.

a b c d e f g h 8 8 7 7 6 6 5 5 4 4 3 3 2 2 1 1 a b c d e f g h En dominerande uppsättning på en subdiagonal.

Att modifiera grafen genom att ersätta det icke-loopande rektangulära $8\times 8$ schackbrädet med en torus eller cylinder minskar den minsta dominerande setstorleken till fyra.

Prickade rutor ligger i anslutning till mitttorget. De 8 icke-intilliggande rutorna ligger intill i motsvarande riddargraf .

3 $3\times 3$ drottningens graf domineras av den enda vertexen i mitten av brädet Mittpunkten på $5\times 5$ drottningens graf ligger intill alla utom 8 hörn: de hörn som gränsar till mittpunkten på $5\times 5$ riddargrafen .

Dominansnummer

Definiera dominanstalet d ( n ) för en $n\times n$ drottningsgraf till att vara storleken på den minsta dominerande uppsättningen, och det diagonala dominanstalet dd ( n ) som storleken på den minsta dominerande mängd som är en delmängd av den långa diagonalen. Observera att $d(n)\leq dd(n)$ för alla n . Gränsen uppnås för ${\displaystyle d(8)=dd(8)=5} ,$ men inte för $d(11)=5,dd(11)=7$ .

Dominanstalet är linjärt i n , med gränser som ges av:

${\frac {n-1}{2}}\leq d(n)\leq n-\left\lfloor {\frac {n}{3}}\right\rfloor .$

Inledande värden för d ( n ), för $n=1,2,3,\dots$ , är 1, 1, 1, 2, 3, 3, 4, 5, 5, 5, 5 (sekvens A075458 i OEIS ).

Låt K _n vara den maximala storleken på en delmängd av $\{1,2,3,\dots ,n\}$ så att varje tal har samma paritet och ingen tre tal bildar en aritmetisk progression (mängden är "mittpunktsfri"). Det diagonala dominanstalet för en $n\times n$ drottningsgraf är $n-K_{n}$ .

Definiera det oberoende dominansnumrets ID ( n ) så att det är storleken på den minsta oberoende, dominanta mängden i en $n\times n$ drottningsgraf. Det är känt att ${\displaystyle ID(n)<0,705n+0,895$ .

Färg

En 9- färgning av $8\times 8$ drottningens graf. Lägg märke till att varje par av rutor med samma färg inte är på samma rang, fil eller diagonal, så en dam kunde inte flytta direkt mellan rutor.

En färgning av drottningens graf är en tilldelning av färger till varje vertex så att inga två närliggande hörn får samma färg. Till exempel, om a8 är färgad röd kan ingen annan ruta på a- filen , åttonde rangen eller lång diagonal färgas röd, eftersom en dam kan flytta från a8 till någon av dessa rutor. Grafens kromatiska nummer är det minsta antal färger som kan användas för att färga den.

I fallet med en $n\times n$ drottningsgraf krävs minst n färger, eftersom varje ruta i en rang eller fil behöver en annan färg (dvs. raderna och kolumnerna är klickar ). Det kromatiska talet är exakt n om $n\equiv 1,5{\pmod {6}}$ (dvs n är en mer eller en mindre än en multipel av 6).

Det kromatiska talet för en $8\times 8$ drottningsgraf är 9.

Irredundans

En uppsättning hörn är irredundant om man tar bort någon vertex från mängden ändrar grannskapet till mängden , dvs. för varje vertex finns det en angränsande vertex som inte ligger intill någon annan vertex i mängden. Detta motsvarar en uppsättning damer som var och en unik kontrollerar minst en ruta. Den maximala storleken IR ( n ) för en irredundant uppsättning på $n\times n$ drottningens graf är svår att karakterisera; kända värden inkluderar $IR(5)=5,IR(6)$

Förföljelse-undvikande spel

Betrakta jakten–undandragningsspelet på en $8\times 8$ damgraf som spelas enligt följande regler: en vit dam börjar i ett hörn och en svart dam i det motsatta hörnet. Spelare alternerande drag, som består av att flytta drottningen till en intilliggande vertex som kan nås utan att passera (horisontellt, vertikalt eller diagonalt) eller landa på en vertex som ligger intill den motsatta drottningen. Detta spel kan vinnas av vit med en parningsstrategi .

Se även

• Kungens graf
• Riddarens graf
• Rooks graf
• Biskopens graf
•  Schackportal