Počet věží

počet věží

Počet věží 8x8
Vrcholy nm
žebra nm ( n + m )/2- nm
Průměr 2
obvod 3 (pokud max( n , m ) ≥ 3)
Chromatické číslo max ( n , m )
Vlastnosti pravidelný
vertex-tranzitivní
dokonalý
dobře pokrytý
 Mediální soubory na Wikimedia Commons

V teorii grafů je věžový graf graf , který představuje všechny povolené tahy věže na šachovnici  - každý vrchol představuje buňku na šachovnici a hrany představují možné tahy. Věžové grafy jsou vysoce symetrické dokonalé grafy  – lze je popsat počtem trojúhelníků , ke kterým hrana patří, a existencí cyklu délky 4, který zahrnuje libovolné dva nesousedící vrcholy.

Definice

Graf n  ×  m věží představuje povolené pohyby věže na desce n  ×  m . Vrcholy grafu mohou mít souřadnice ( x , y ), kde 1 ≤  x  ≤  n a 1 ≤  y  ≤  m . Dva vrcholy ( x 1 , y 1 ) a ( x 2 , y 2 ) sousedí právě tehdy, když buď x 1  =  x 2 nebo y 1  =  y 2 . Tedy pokud leží na stejné buněčné linii (horizontální nebo vertikální).

Pro n  ×  m věžový graf je celkový počet vrcholů nm . Pro čtvercovou desku n  ×  n je počet vrcholů věžového grafu roven a počet hran roven . V druhém případě je graf znám jako dvourozměrný Hammingův graf .

Rookův graf na desce n  ×  m lze definovat jako přímý součin dvou úplných grafů K n K m . Doplňkem 2× n věžového grafu  je koruna .

Symetrie

Věžové grafy jsou vertex-tranzitivní a ( n  +  m  − 2) -regulární . Toto je jediná třída pravidelných grafů, které lze sestavit na základě tahů standardních šachových figurek [1] . Je-li m  ≠  n , jsou symetrie věžového grafu tvořeny nezávislými permutacemi řádků a sloupců grafu. Pokud n  =  m , graf má další symetrie, které zaměňují řádky a sloupce. Věžový graf pro čtvercovou šachovnici je symetrický .

Jakékoli dva vrcholy ve věžovém grafu jsou od sebe buď jeden nebo dva, v závislosti na tom, zda sousedí nebo ne. Libovolné dva nesousedící vrcholy lze mapovat na libovolné dva další nesousedící vrcholy pomocí grafové symetrie. Pokud věžový graf není čtvercový, dvojice sousedních vrcholů se rozdělí na dva orbity skupiny symetrií podle jejich sousedství - vodorovně nebo svisle, ale v případě čtvercového grafu lze libovolné dva sousední vrcholy přenést z jednoho na druhý pomocí symetrie, a proto je graf vzdálenostně tranzitivní .

Jestliže m a n jsou relativně prvočísla , pak grupa symetrie S m × S n rookova grafu obsahuje jako podgrupu cyklickou grupu C mn  =  C m × C n , která působí cyklickou permutací mn vrcholů. V tomto případě je tedy věžův graf obíhající .

Dokonalost

Věžový graf lze považovat za spojnicový graf úplného bipartitního grafu K n , m . To znamená, že má vrchol pro každou hranu Kn , ma dva vrcholy věžového grafu sousedí právě tehdy, když odpovídající hrany úplného bipartitního grafu mají společný vrchol. Z tohoto pohledu hrana bipartitního grafu spojující vrchol i jedné strany s vrcholem j druhé strany odpovídá šachovnicové buňce se souřadnicemi ( i , j ).

Jakýkoli bipartitní graf je podgrafem úplného bipartitního grafu, což znamená, že jakýkoli spojnicový graf bipartitního grafu je vygenerovaným podgrafem rookova grafu. Spojnicové grafy bipartitních grafů jsou dokonalé  - v nich a v každém z jeho generovaných podgrafů je počet barev potřebných pro jakékoli obarvení vrcholů roven počtu vrcholů v největší klikě . Spojnicové grafy bipartitních grafů tvoří důležitou rodinu dokonalých grafů, jednu z mála rodin používaných Chudnovskou a kol . Zejména věžové grafy jsou perfektní.

Protože věžové grafy jsou dokonalé, počet barev potřebných k vybarvení grafu se rovná velikosti největší kliky. Kliky věžova grafu jsou podmnožiny jeho řádků a sloupců a největší z nich má velikost max( m , n ), takže toto číslo je chromatické číslo grafu. n -barvení n × n věžového grafu lze považovat za latinský čtverec  — popisuje způsob, jak vyplnit řádky a sloupce mřížky n × n různými hodnotami, takže žádná hodnota se v řádcích neobjeví dvakrát. a sloupce.

Nezávislá množina ve věžovém grafu je množina vrcholů, z nichž žádné dva nepatří do stejného řádku nebo sloupce grafu. Z hlediska šachu to odpovídá uspořádání věží, z nichž žádné dvě na sebe neútočí. Dokonalé grafy lze také popsat jako grafy, ve kterých je pro jakýkoli vygenerovaný podgraf velikost největší nezávislé množiny rovna počtu kliků při rozkladu vrcholů grafu na minimální počet kliků. Ve věžovém grafu tvoří množina řádků nebo sloupců (podle toho, co je menší) takový optimální rozklad. Velikost největší nezávislé množiny je tedy min( m , n ). Jakékoli optimální vybarvení ve věžovém grafu je maximální nezávislá množina.

Popis

Moon [3] popisuje m × n věžový graf jako jediný graf, který má následující vlastnosti:

Pokud n  =  m , lze tyto podmínky zjednodušit tak, že n × n věžový graf je silně regulární graf s parametry srg( n 2 , 2 n  − 2,  n  − 2, 2), a že jakýkoli silně regulární graf s takové parametry musí být n × n věžový graf , pokud n ≠ 4. Pokud n = 4, existuje další silně pravidelný graf, a to Shrikhandeho graf , který má stejné parametry jako věžový graf 4×4. Shrikhandeho graf se od věžového grafu 4×4 liší tím, že okolí libovolného vrcholu Shrikhandeho grafu je spojeno v cyklu délky 6, zatímco ve věžovém grafu patří do dvou trojúhelníků.

Dominance

Číslo dominance grafu je minimální velikost sady mezi všemi dominujícími sadami. Ve věžovém grafu je množina vrcholů dominantní množinou tehdy a jen tehdy, když kterákoli buňka na šachovnici buď patří do množiny, nebo je o jeden tah vzdálena od prvku množiny. Pro desku m × n je číslo dominance min( m , n ) [4] .

Pro věžový graf je k -dominantní množina množina vrcholů, jejichž odpovídající buňky útočí na všechny ostatní buňky (s pohybem věže) alespoň kkrát . K -násobná dominující množina pro věžový graf je množina vrcholů, jejichž odpovídající buňky útočí na všechny ostatní buňky (s tahem věže) alespoň kkrát a na své vlastní buňky alespoň k  − 1krát. Minimální velikost mezi všemi k -dominantními množinami a k ​​-násobně dominantními množinami je k -dominantní číslo a k -násobně dominantní číslo. Na čtvercové desce je pro sudé k k -dominantní číslo nk /2 pro n  ≥ ( k 2  − 2 k )/4 ak <  2 n . Podobně je k - násobné dominantní číslo n ( k  + 1)/2, když k je liché a menší než 2n [5] .

Viz také

Poznámky

  1. ↑ Elkies, 2004 .
  2. ↑ Chudnovsky, Robertson, Seymour, Thomas, 2006 .
  3. ↑ Měsíc, 1963 .
  4. ↑ Yaglom a Yaglom, 1987 .
  5. ↑ Burchett, Lane, Lachniet, 2009 .

Literatura

Odkazy