Rooks graf

Rook's graph
8x8 Rook's graph
Vertices	nm
Kanter	nm ( n + m )/2 - nm
Diameter	2
Omkrets	3 (om max( n , m ) ≥ 3 )
Kromatiskt nummer	max( n , m )
Spektrum	{ m + n − 2, m − 2, n − 2, −2}
Egenskaper	väsentlig perfekt regelbunden vertextransitiv väl täckt
Tabell över grafer och parametrar

I grafteorin är ett torns graf en oriktad graf som representerar alla lagliga drag av tornets schackpjäs på ett schackbräde . Varje hörn på ett torns graf representerar en ruta på ett schackbräde, och varje kant förbinder två rutor på samma rad (rang) eller på samma kolumn (fil) som varandra, de rutor som ett torn kan röra sig mellan. Dessa grafer kan konstrueras för schackbräden av vilken rektangulär form som helst, och kan definieras matematiskt som den kartesiska produkten av två kompletta grafer , som de tvådimensionella Hamming-graferna , eller som linjegraferna för kompletta tvådelade grafer .

Rooks grafer är mycket symmetriska, med symmetrier som tar varje vertex till varannan vertex. I tornets grafer definierade från fyrkantiga schackbräden, ännu starkare, är varannan kanter symmetriska, och varje par av hörn är symmetriska med vartannat par på samma avstånd (således är de distanstransitiva ) . För rektangulära schackbräden vars två sidolängder är relativt prime i förhållande till varandra, är tornets grafer cirkulerande grafer . Med ett undantag kan tornets grafer särskiljas från alla andra grafer genom antalet trianglar som varje kant tillhör och genom att det finns en 4 -cykel som förbinder varje icke intilliggande hörnpar.

Rooks grafer är perfekta grafer , vilket betyder att varje delmängd av schackbrädsrutor kan färgas så att inga två rutor i en rad eller kolumn har samma färg, och så att antalet färger är lika med det maximala antalet rutor från delmängden i någon enskild rad eller kolumn ( klicknumret för en inducerad subgraf) . Graferna som bildas på detta sätt från delmängder av kvadrater i ett torns graf bildar en av nyckelkomponenterna i en nedbrytning av perfekta grafer som används för att bevisa den starka perfekta grafsatsen som kännetecknar alla perfekta grafer. Oberoendetalet och dominanstalet för ett torns graf, eller med andra ord det maximala antalet torn som kan placeras så att de inte attackerar varandra eller så att de attackerar alla återstående brädrutor, båda är lika med den minsta av schackbrädets två dimensioner, och dessa är väl täckta grafer , vilket betyder att placering av icke-attackerande torn ett i taget aldrig kan fastna förrän en uppsättning av maximal storlek har uppnåtts.

Definition och matematiska konstruktioner

En n × m torns graf representerar dragen av ett torn på ett n × m schackbräde. Dess hörn representerar kvadraterna på schackbrädet och kan ges koordinater ( x , y ) , där 1 ≤ x ≤ n och 1 ≤ y ≤ m . Två hörn med koordinater ( x ₁ , y ₁ ) och ( x ₂ , y ₂ ) är angränsande om och endast om antingen x ₁ = x ₂ (de två rutorna tillhör samma fil på schackbrädet och är förbundna med en vertikal torndrag) eller y ₁ = y ₂ (de två rutorna tillhör samma rang och är förbundna med ett horisontellt drag).

Inom en enda rang eller en enda fil på schackbrädet kan alla rutor nås från varandra, så dessa rutor bildar en klick , en delmängd av hörn som bildar en komplett graf . Hela tornets graf för ett n × m schackbräde kan bildas av dessa två typer av klickar som den kartesiska produkten av graferna K _n ◻ K _m . Eftersom tornets graf för ett fyrkantigt schackbräde är den kartesiska produkten av lika stora klickar, är det ett exempel på en Hamming-graf . Dess dimension som en Hamming-graf är två, och varje tvådimensionell Hamming-graf är en tornsgraf för ett fyrkantigt schackbräde. Fyrkantiga torns grafer kallas också latinska kvadratgrafer , eftersom hörnen på en sådan graf beskriver kvadraterna på en latinsk kvadrat och dess kanter beskriver par av kvadrater som inte kan innehålla samma värde. Sudoku -graferna är supergrafer av tornets grafer med några extra kanter, som förbinder rutor i ett Sudoku-pussel som borde ha olika värden.

3-3 duoprism , en fyrdimensionell konvex polytop med en 3 × 3 tornsgraf som skelett

Geometriskt kan tornets grafer bildas av uppsättningar av hörn och kanter (skeletten ) av en familj av konvexa polytoper , de kartesiska produkterna av par av grannpolytoper . Till exempel 3-3-duoprismen en fyrdimensionell form bildad som den kartesiska produkten av två trianglar , och har en 3 × 3 tornsgraf som skelett.

Regelbundenhet och symmetri

Stark regelbundenhet

Moon (1963) och Hoffman (1964) observerar att $m\times n$ tornets graf (eller motsvarande, som de beskriver det, linjegrafen för den kompletta tvådelade grafen $K_ {m,n}$ ) har alla följande egenskaper:

• Den har $mn$ hörn, en för varje kvadrat på $m\times n$ schackbrädet. Varje vertex ligger intill $m+n-2$ kanter, vilket ansluter den till $m-1$ rutorna på samma rang och $n- 1$ rutor på samma fil.
• Trianglarna i tornets graf bildas av trippel kvadrater inom en enda rang eller fil. När $m\neq n$ , hör exakt $n{\tbinom {m}{2}}$ kanter (de som förbinder kvadrater på samma rang) till $m-2$ trianglar; de återstående $m{\tbinom {n}{2}}$ kanterna (de som förbinder kvadrater på samma fil) tillhör $n-2$ trianglar. När $m=n$ tillhör varje kant $m-2=n-2$ trianglar.
• Varje två hörn som inte gränsar till varandra tillhör en unik $4$ -vertexcykel , kopplade till varandra genom de andra två hörnen som använder en kombination av samma två rankningar och filer .

Som de visar, förutom i fallet $m=n=4$ , kännetecknar dessa egenskaper tornets graf. Det vill säga, tornets grafer är de enda graferna med dessa antal hörn, kanter, trianglar per kant, och med en unik 4-cykel genom var och en av två icke-intilliggande hörn.

När $m=n$ , kan dessa villkor förkortas genom att ange att en $n\times n$ torns graf är en starkt regelbunden graf med parametrarna $\operatörsnamn {srg} (n^{2},2n-2,n-2,2)$ . Dessa parametrar beskriver antalet hörn, antalet kanter per hörn, antalet trianglar per kant och antalet delade grannar för två icke intilliggande hörn, respektive. Omvänt måste varje starkt regelbunden graf med dessa parametrar vara en $n\times n$ tornsgraf, om inte $n=4$ .

Shrikhande -grafen inbäddad på en torus. Detta är inte ett torns graf, utan är mycket regelbundet med samma parametrar som $4\times 4$ torns graf.

När $n=4$ finns det en annan starkt regelbunden graf, Shrikhande-grafen , med samma parametrar som $4\times 4$ tornsgraf. Shrikhande-grafen följer samma egenskaper som anges av Moon och Moser. Det kan särskiljas från $4\times 4$ tornsgrafen genom att grannskapet för varje vertex i Shrikhande-grafen är kopplat till en $6$ -cykel . Däremot, i $4\times 4$ tornsgrafen bildar grannskapet för varje vertex två trianglar, en för dess rangordning och en annan för dess fil, utan några kanter från en del av grannskapet till den andra . Ett annat sätt att skilja $4\times 4$ torngrafen från Shrikhande-grafen använder klicktäckningsnummer : $n=4$ tornets graf kan täckas av fyra klicker (de fyra leden eller de fyra filerna på schackbrädet) medan sex klick behövs för att täcka Shrikhande-grafen.

Symmetri

Rooks grafer är vertextransitiva , vilket betyder att de har symmetrier som tar varje vertex till varannan vertex. Detta innebär att varje vertex har lika många kanter: de är $(m+n-2)$ - regelbundna . Tornets grafer är de enda vanliga graferna som bildas från dragen av vanliga schackpjäser på detta sätt. När $m\neq n$ , bildas symmetrierna för tornets graf genom att oberoende permutera grafens rader och kolumner, så att grafens automorfismgrupp har $m!n!$ element. När $m=n$ , har grafen ytterligare symmetrier som byter rader och kolumner, så antalet automorfismer är $2n!^{2}$ .

Alla två hörn i ett torns graf är antingen på avstånd ett eller två från varandra, beroende på om de är intilliggande respektive icke-angränsande. Alla två icke-angränsande hörn kan omvandlas till vilka andra två icke-angränsande hörn som helst genom en symmetri av grafen. När tornets graf inte är kvadratisk, faller paren av intilliggande hörn i två omloppsbanor i symmetrigruppen beroende på om de är intill varandra horisontellt eller vertikalt, men när grafen är kvadratisk kan två intilliggande hörn också mappas in i varandra av en symmetri och grafen är därför distanstransitiv .

När $m$ och $n$ är relativt primtal , innehåller symmetrigruppen $S_{m}\ gånger S_{n}$ i tornets graf som en undergrupp den cykliska grupp $C_{mn}=C_{m}\ gånger C_{n}$ som verkar genom att cykliskt permutera $mn$ hörn. Därför, i det här fallet, är tornets graf en cirkulerande graf .

Fyrkantiga torns grafer är anslutna-homogena , vilket betyder att varje isomorfism mellan två anslutna inducerade subgrafer kan utökas till en automorfism av hela grafen.

Övriga fastigheter

Fullkomlighet

3×3-tornets graf (grafen för 3-3-duoprismen ), färgad med tre färger och visar en klick med tre hörn. I denna graf och var och en av dess inducerade subgrafer är det kromatiska talet lika med klicknumret, så det är en perfekt graf.

Ett torns graf kan också ses som linjediagrammet för en komplett tvådelad graf K _{n , m} — det vill säga den har en vertex för varje kant på K _{n , m} , och två hörn av tornets graf ligger intill om och endast om motsvarande kanter på den fullständiga tvådelade grafen delar en gemensam slutpunkt. I den här vyn motsvarar en kant i den kompletta tvådelade grafen från den i: te ( i , j ) vertexen på ena sidan av bipartitionen till den j :te vertexen på den andra sidan en schackbrädsruta med koordinater .

Varje tvådelad graf är en subgraf av en komplett tvådelad graf, och på motsvarande sätt är varje linjegraf i en tvådelad graf en inducerad subgraf av ett torns graf. Linjediagrammen för tvådelade grafer är perfekta : i dem, och i alla deras inducerade subgrafer, är antalet färger som behövs i någon vertexfärgning detsamma som antalet hörn i den största kompletta subgrafen . Linjediagram av tvådelade grafer bildar en viktig familj av perfekta grafer: de är en av ett litet antal familjer som används av Chudnovsky et al. (2006) för att karakterisera de perfekta graferna och för att visa att varje graf utan udda hål och inget udda antihål är perfekt. I synnerhet är tornets grafer perfekta.

Eftersom ett torns graf är perfekt, är antalet färger som behövs i valfri färgning av grafen bara storleken på dess största klick. Klickorna i ett torns graf är delmängder av en enstaka rad eller en enda kolumn, och den största av dessa har storleken max ( m , n ) , så detta är också grafens kromatiska nummer. En n -färgning av ett n × n torns graf kan tolkas som en latinsk kvadrat : den beskriver ett sätt att fylla raderna och kolumnerna i ett n × n rutnät med n olika värden på ett sådant sätt att samma värde inte visas två gånger i valfri rad eller kolumn. Även om det är enkelt att hitta en optimal färgning av ett torns graf är det NP-komplett att avgöra om en partiell färgläggning kan utökas till en färgning av hela grafen (detta problem kallas förfärgningsförlängning ). På motsvarande sätt är det NP-komplett att avgöra om en partiell latinsk kvadrat kan kompletteras till en hel latinsk kvadrat.

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 icke-attackerande placering av åtta torn på ett schackbräde, som bildar en maximal oberoende uppsättning i motsvarande torns graf

En oberoende uppsättning i ett torns graf är en uppsättning hörn, varav inte två hör till samma rad eller kolumn i grafen; i schacktermer motsvarar det en placering av torn varav två attackerar varandra. Perfekta grafer kan också beskrivas som de grafer där, i varje inducerad subgraf, storleken på den största oberoende uppsättningen är lika med antalet klick i en uppdelning av grafens hörn i ett minsta antal klicker. I ett torns graf bildar uppsättningarna av rader eller uppsättningarna av kolumner (beroende på vilken som har färre uppsättningar) en sådan optimal partition. Storleken på den största oberoende mängden i grafen är därför min ( m , n ) . Varje färgklass i varje optimal färgning av ett torns graf är en maximal oberoende uppsättning.

Rooks grafer är väl täckta grafer : varje oberoende uppsättning i ett torns graf min( m , n ) kan utökas till en maximal oberoende uppsättning, och varje maximal oberoende uppsättning i ett torns graf har samma storlek, .

Herravälde

Dominansnumret för en graf är den lägsta kardinaliteten bland alla dominerande uppsättningar . På tornets graf är en uppsättning hörn en dominerande uppsättning om och endast om deras motsvarande rutor antingen upptar, eller är ett torns rörelse bort från, alla rutor på m × n - brädet . För m × n -brädan är dominanstalet min( m , n ) .

På tornets graf är en k -dominerande uppsättning en uppsättning hörn vars motsvarande rutor attackerar alla andra rutor (via ett torns drag) minst k gånger. En k -tuppel som dominerar uppsättningen på tornets graf är en uppsättning hörn vars motsvarande rutor attackerar alla andra rutor minst k gånger och själva attackeras minst k − 1 gånger. Minsta kardinalitet bland alla k -dominerande och k -tupeldominerande uppsättningar är k -dominationsnumret respektive k -tupelns dominansnumret. På den fyrkantiga brädan, och för jämn k , är k - dominanstalet nk /2 när n ≥ ( k ² − 2 k )/4 och k < 2 n . På liknande sätt k -tupeldominanstalet n ( k + 1)/2 när k är udda och mindre än 2 n .

Hamiltonicitet

Varje torns graf innehåller en Hamiltonsk cykel . Dessa cykler kan dock innebära rörelser mellan rutor som är långt ifrån varandra inom en enda rad eller kolumn på schackbrädet. Istället har studiet av "rook's tours", i schackets matematik, i allmänhet koncentrerats på ett specialfall av dessa Hamilton-cykler där tornet är begränsat till att endast röra sig till intilliggande rutor. Dessa enstegs tornsturer finns bara på brädor med ett jämnt antal rutor. De spelar en central roll i beviset för Gomorys teorem att om två rutor med motsatta färger tas bort från ett standardschackbräde, kan de återstående rutorna alltid täckas av dominobrickor. De visas tillsammans med riddarturer i det första verket för att diskutera schackturer, 800-talets sanskrit Kavyalankara av Rudrata .

Spektrum

Spektrum för ett torns graf ( egenvärdena för dess närliggande matris ) består av de fyra egenvärdena ${\displaystyle m+n-2} ,$ n m − $displaystyle m-2} ,$$\ displaystyle n-2}$ och $-2$ . Eftersom dessa alla är heltal, är tornets grafer integralgrafer . Det finns bara tre klasser av grafer (och ändligt många exceptionella grafer) som kan ha fyra egenvärden där ett av de fyra är − $\displaystyle -2}$ ; en av de tre klasserna är klassen av tornets grafer. För de flesta kombinationer av $m$ och $n$$\displaystyle m\times n}$ × tornet spektralt unik: ingen annan graf har samma spektrum. Detta gäller särskilt när $n=2$ eller $n=m-1$ , eller när de två talen $m$ och $n$ summa till minst 18 och har inte formen $2t^{2}\pm t$ .

Se även

• Kungens graf , riddarens graf , drottningens graf och biskopens graf , fyra andra grafer definierade från dragen av schackpjäser
• Gittergraf , grafen över horisontella och vertikala angränsande rutor på ett schackbräde

externa länkar

• Weisstein, Eric W. , "Rook Graph" , MathWorld