Tornräkning
| tornräkning | |
|---|---|
| Rook Count 8x8 | |
| Toppar | nm |
| revben | nm ( n + m )/2 - nm |
| Diameter | 2 |
| Omkrets | 3 (om max( n , m ) ≥ 3) |
| Kromatiskt nummer | max( n , m ) |
| Egenskaper |
regelbunden vertex-transitiv perfekt vältäckt |
| Mediafiler på Wikimedia Commons | |
I grafteorin är en torngraf en graf som representerar alla tillåtna drag av ett torn på ett schackbräde - varje vertex representerar en cell på brädet , och kanterna representerar möjliga drag. Rook-grafer är mycket symmetriska perfekta grafer - de kan beskrivas i termer av antalet trianglar som en kant tillhör och förekomsten av en cykel med längd 4 som inkluderar två icke-angränsande hörn.
Definition
n × m torngrafen representerar tillåtna tornrörelser på ett n × m bräde . Grafens hörn kan ges koordinater ( x , y ), där 1 ≤ x ≤ n och 1 ≤ y ≤ m . Två hörn ( x 1 , y 1 ) och ( x 2 , y 2 ) är intilliggande om och endast om antingen x 1 = x 2 eller y 1 = y 2 . Det vill säga om de ligger på samma cellinje (horisontell eller vertikal).
För en n × m torngraf är det totala antalet hörn nm . För en kvadratisk tavla n × n är antalet hörn på torngrafen lika och antalet kanter är lika med . I det senare fallet är grafen känd som en tvådimensionell Hamming-graf .
En torns graf på en n × m bräda kan definieras som en direkt produkt av två kompletta grafer K n K m . Komplementet av en 2× n torns graf är en krona .
Symmetri
Rook-grafer är vertextransitiva och ( n + m − 2) -regelbundna . Detta är den enda klassen av vanliga grafer som kan konstrueras baserat på dragen av vanliga schackpjäser [1] . Om m ≠ n , bildas torngrafens symmetri av oberoende permutationer av grafens rader och kolumner. Om n = m , har grafen ytterligare symmetrier som byter rader och kolumner. Torndiagrammet för ett fyrkantigt schackbräde är symmetriskt .
Varje två hörn i en torngraf är antingen en eller två från varandra, beroende på om de ligger intill eller inte. Alla två icke-angränsande hörn kan mappas till vilka två andra icke-angränsande hörn som helst med hjälp av grafsymmetri. Om torngrafen inte är kvadratisk, delas par av angränsande hörn i två banor av symmetrigruppen beroende på deras närhet - horisontellt eller vertikalt, men i fallet med en kvadratisk graf kan två intilliggande hörn överföras från en till en annan med symmetri och därmed är grafen avståndstransitiv .
Om m och n är relativt primtal , så innehåller symmetrigruppen S m × S n i tornets graf som en undergrupp den cykliska gruppen C mn = C m × C n , som verkar genom att permutera mn hörn cykliskt. I det här fallet är alltså tornets graf cirkulerande .
Perfektion
Torngrafen kan betraktas som linjegrafen för den kompletta tvådelade grafen K n , m . Det vill säga, den har en vertex för varje kant K n , m och två hörn på torngrafen ligger intill om och endast om motsvarande kanter på den kompletta tvådelade grafen har en gemensam vertex. Ur denna synvinkel motsvarar en kant på en tvådelad graf som förbinder vertex i på ena sidan med vertex j på den andra sidan en schackbrädescell med koordinater ( i , j ).
Varje tvådelad graf är en subgraf till en komplett tvådelad graf, vilket betyder att vilken linjegraf som helst i en tvådelad graf är en genererad subgraf av ett torns graf. Linjediagrammen för tvådelade grafer är perfekta - i den och i någon av dess genererade subgrafer är antalet färger som behövs för färgning av hörn lika med antalet hörn i den största klicken . Linjegrafer av tvådelade grafer bildar en viktig familj av perfekta grafer, en av ett litet antal familjer som används av Chudnovskaya et al . [2] för att beskriva perfekta grafer och för att visa att alla grafer utan udda hål och antihål är perfekta. I synnerhet torngraferna är perfekta.
Eftersom torngraferna är perfekta är antalet färger som behövs för att färglägga grafen lika med storleken på den största klicken. Klickorna i ett torns graf är delmängder av dess rader och kolumner, och den största av dem har storleken max( m , n ), så detta nummer är grafens kromatiska nummer. En n -färgning av en n × n torngraf kan ses som en latinsk kvadrat — den beskriver ett sätt att fylla raderna och kolumnerna i ett n × n gitter med n olika värden, så att inget värde visas två gånger i raderna och kolumner.
En oberoende uppsättning i en torngraf är en uppsättning hörn varav två hör till samma rad eller kolumn i grafen. När det gäller schack motsvarar detta ett arrangemang av torn, varav inte två attackerar varandra. Perfekta grafer kan också beskrivas som grafer där, för alla genererade subgrafer, storleken på den största oberoende uppsättningen är lika med antalet klickar i nedbrytningen av grafens hörn till det minsta antalet klicker. I en torngraf bildar uppsättningen av rader eller kolumner (den som är minst) en sådan optimal nedbrytning. Storleken på den största oberoende mängden är alltså min( m , n ). Varje optimal färgläggning i en torngraf är en maximal oberoende uppsättning.
Beskrivning
Moon [3] beskriver grafen m × n torn som den enda grafen som har följande egenskaper:
- Den har mn hörn, som var och en faller in mot n + m − 2 kanter.
- mn ( m − 1)/2 kanter tillhör m − 2 trianglar, och de återstående mn ( n − 1)/2 kanterna tillhör n − 2 trianglar.
- Alla två icke-angränsande hörn hör till en enda cykel med 4 hörn.
Om n = m , kan dessa villkor förenklas för att säga att n × n torngrafen är en starkt regelbunden graf med parametrarna srg( n 2 , 2 n − 2, n − 2, 2), och att varje starkt regelbunden graf med sådana parametrar måste vara en n × n torngraf om n ≠ 4. Om n = 4 finns det en annan starkt regelbunden graf, nämligen Shrikhande-grafen , som har samma parametrar som 4×4-tornsgrafen. Shrikhande-grafen skiljer sig från 4×4-tornsgrafen genom att grannskapet till valfri hörn på Shrikhande-grafen är sammankopplad i en cykel med längden 6, medan de i torngrafen tillhör två trianglar.
Dominans
Grafens dominansnummer är den minsta uppsättningsstorleken bland alla dominerande uppsättningar. I en torngraf är en uppsättning hörn en dominant uppsättning om och endast om någon cell på brädet antingen tillhör uppsättningen eller är ett drag bort från ett element i uppsättningen. För en m × n bräda är dominanstalet min( m , n ) [4] .
För en torngraf är den k -dominanta mängden uppsättningen av hörn vars motsvarande celler attackerar alla andra celler (med en tornrörelse) minst k gånger. Den k -faldiga dominerande uppsättningen för en torngraf är uppsättningen av hörn vars motsvarande celler attackerar alla andra celler (med tornets rörelse) minst k gånger och attackerar sina egna celler minst k − 1 gånger. Minsta storlek bland alla k -dominanta uppsättningar och k -faldiga dominanta uppsättningar är k - dominanta tal respektive k -faldiga dominanta tal. På en kvadratisk tavla, för jämn k , är k -dominanttalet nk /2 för n ≥ ( k 2 − 2 k )/4 och k < 2 n . På liknande sätt är det k -faldiga dominanta talet n ( k + 1)/2 när k är udda och mindre än 2n [5] .
Se även
Anteckningar
- ↑ Elkies, 2004 .
- ↑ Chudnovsky, Robertson, Seymour, Thomas, 2006 .
- ↑ Månen, 1963 .
- ↑ Yaglom och Yaglom, 1987 .
- ↑ Burchett, Lane, Lachniet, 2009 .
Litteratur
- Jan Beka. K n -nedbrytning av linjegraferna för kompletta tvådelade grafer // Octogon Mathematical Magazine. - 2001. - T. 9 , nr. 1A . — S. 135–139 .
- Bekmetjev, Airat & Hurlbert, Glenn (2004), The pebbling threshold of the square of cliques, arΧiv : math.CO/0406157 [math.CO].
- Berger-Wolf, Tanya Y. & Harris, Mitchell A. (2003), Sharp bounds for bandwidth of clique products, arΧiv : cs.DM/0305051 [cs.DM].
- Paul Burchett, David Lane, Jason Lachniet. K-dominans och k-tupeldominans på tornets graf och andra resultat // Congressus Numerantium . - 2009. - T. 199 . - S. 187-204 .
- Maria Chudnovsky, Neil Robertson, Paul Seymour, Robin Thomas. The strong perfect graph theorem // Annals of Mathematics . - 2006. - T. 164 , nr. 1 . - S. 51-229 . doi : 10.4007 / annals.2006.164.51 .
- Noam Elkies . Grafteori ordlista. – 2004.
- AJ Hoffman. På linjediagrammet för den kompletta tvådelade grafen // Annals of Mathematical Statistics . - 1964. - T. 35 , nr. 2 . - S. 883-885 . - doi : 10.1214/aoms/1177703593 .
- van der Hofstad, Remco & Luczak, Malwina J. (2008), Random subgraphs of the 2D Hamming graph: the supercritical phase, arΧiv : 0801.1607 [math.PR].
- Renu Laskar, Charles Wallis. Schackbrädegrafer, relaterade mönster och dominansparametrar // Journal of Statistical Planning and Inference. - 1999. - T. 76 , nr. 1-2 . - S. 285-294 . - doi : 10.1016/S0378-3758(98)00132-3 .
- van der Hofstad, Remco; Luczak, Malwina J. & Spencer, Joel (2008), Den näst största komponenten i den superkritiska 2D Hamming-grafen, arΧiv : 0801.1608 [math.PR].
- G. MacGillivray, K. Seyffarth. Klasser av linjediagram med små cykliska dubbla omslag // Australasian Journal of Combinatorics. - 2001. - T. 24 . - S. 91-114 .
- JW Moon. På linjediagrammet för den fullständiga bigrafen // Annals of Mathematical Statistics . - 1963. - T. 34 , nr. 2 . - S. 664-667 . - doi : 10.1214/aoms/1177704179 .
- D. de Werra, A. Hertz. Om fullkomlighet av summor av grafer // Diskret matematik . - 1999. - T. 195 , nr. 1-3 . - S. 93-101 . - doi : 10.1016/S0012-365X(98)00168-X .
- Yaglom A. M., Yaglom I. M. Icke-elementära problem i en elementär presentation. — Dover, 1987.
Länkar
- Weisstein, Eric W. Lattice Graph (engelska) på Wolfram MathWorld- webbplatsen .