Věžový graf - Rooks graph - Wikipedia

Rookův graf
Graf věže 8x8
Vrcholy	nm
Hrany	nm(n + m)/2 − nm
Průměr	2
Obvod	3 (li max (n, m) ≥ 3)
Chromatické číslo	max (n, m)
Vlastnosti	pravidelný, vrchol-tranzitivní, perfektní dobře zakryté
Tabulka grafů a parametrů

v teorie grafů, a věžní graf je graf, který představuje všechny legální pohyby havran šachy kus na šachovnice. Každý vrchol grafu věže představuje čtverec na šachovnici a každá hrana představuje legální tah z jednoho čtverce na druhý. Stejné grafy lze definovat matematicky jako Kartézské výrobky ze dvou kompletní grafy nebo jako spojnicové grafy z kompletní bipartitní grafy.

Rookovy grafy jsou vysoce symetrické. U čtvercových šachovnic jsou vzdálenosti-tranzitivní grafy a vzdálenost-pravidelné grafy, zatímco pro obdélníkové šachovnice s relativně špičkovými rozměry jsou oběhové grafy Mohou být charakterizovány z hlediska počtu trojúhelníků, ke kterým každá hrana patří, a existencí a 4-cyklus spojující každý nesousedící pár vrcholů.

Rookovy grafy jsou perfektní grafy, což znamená, že jejich indukované podgrafy (spojnicové grafy bipartitních grafů) všechny mají chromatické číslo rovná se jejich číslo kliky Indukované podgrafy grafů věže tvoří jednu z klíčových složek rozkladu dokonalých grafů používaných k prokázání silná dokonalá věta o grafu charakterizující všechny dokonalé grafy číslo nezávislosti a dominantní číslo grafu věže se rovná menší z jeho dvou dimenzí, a ty jsou dobře pokryté grafy což znamená, že každý nezávislá sada lze rozšířit na a maximální nezávislá sada.

Definice

An n × m graf věže představuje pohyby věže na n × m šachovnice.^[1]Jeho vrcholy mohou být uvedeny souřadnice (X, y), kde 1 ≤ X ≤ n a 1 ≤ y ≤ m. Dva vrcholy (X₁, y₁) a (X₂,y₂) sousedí, pokud a jen pokud X₁ = X₂ nebo y₁ = y₂; to znamená, že pokud patří ke stejné hodnosti nebo ke stejnému souboru šachovnice.^[1]

Pro n × m graf věže je celkový počet vrcholů jednoduše nm. Pro n × n graf věže je celkový počet vrcholů jednoduše n² a celkový počet hran je n³ − n²; v tomto případě je graf také známý jako dvourozměrný Hammingův graf^[2] nebo a Latinský čtverec graf.^[3]

Graf věže pro n × m šachovnici lze také definovat jako kartézský součin ze dvou kompletní grafy K._n a K._m, vyjádřeno v jednom vzorci jako K._n ◻ K._m. The doplňkový graf a 2 × n graf věže je a korunový graf.

Silná pravidelnost

Měsíc (1963) a Hoffman (1964) pozorovat, že ${ displaystyle m krát n}$ graf věže má všechny následující vlastnosti:

• Má to ${ displaystyle mn}$ vrcholy, z nichž každý sousedí s ${ displaystyle m + n-2}$ hrany.
• Když ${ displaystyle m neq n}$, přesně ${ displaystyle n { tbinom {m} {2}}}$ hrany patří ${ displaystyle m-2}$ trojúhelníky a zbývající ${ displaystyle m { tbinom {n} {2}}}$ hrany patří ${ displaystyle n-2}$ trojúhelníky. Když ${ displaystyle m = n}$, každá hrana patří ${ displaystyle m-2 = n-2}$ trojúhelníky.
• Každé dva vrcholy, které k sobě nesousedí, patří k jedinečnému ${ displaystyle 4}$-vrchol cyklus.

Jak ukazují, kromě případu ${ displaystyle m = n = 4}$, tyto vlastnosti jednoznačně charakterizují graf věže. To znamená, že grafy věže jsou jedinými grafy, které splňují všechny tyto vlastnosti.^[4][5]

Když ${ displaystyle m = n}$lze tyto podmínky zkrátit uvedením, že an ${ displaystyle n krát n}$ graf věže je a silně pravidelný graf s parametry${ displaystyle operatorname {srg} (n ^ {2}, 2n-2, n-2,2)}$.^[1] Naopak každý silně pravidelný graf s těmito parametry musí být ${ displaystyle n krát n}$ graf věže, pokud ${ displaystyle n = 4}$.^[4][5]

The Shrikhandův graf vložený do torusu. Toto není graf věže, ale je silně pravidelný se stejnými parametry jako ${ displaystyle 4 krát 4}$ věžní graf.

Když ${ displaystyle n = 4}$, existuje další silně pravidelný graf, Shrikhandův graf, se stejnými parametry jako ${ displaystyle 4 krát 4}$ věžní graf.^[6]Shrikhandův graf se řídí stejnými vlastnostmi, jaké uváděli Moon a Moser. Lze jej odlišit od ${ displaystyle 4 krát 4}$ graf věže v tom sousedství každého vrcholu v grafu Shrikhande je spojen do tvaru a ${ displaystyle 6}$-cyklus. Naproti tomu v ${ displaystyle 4 krát 4}$ graf věže, sousedství každého vrcholu tvoří dva trojúhelníky, oddělené od sebe navzájem.^[7] Alternativně je lze odlišit podle klikový obal čísla: ${ displaystyle n = 4}$ graf věže lze zakrýt čtyřmi klikami (čtyři řádky nebo čtyři sloupce grafu), zatímco k pokrytí grafu Shrikhande je potřeba šest klik.^[6]

Symetrie

Rookovy grafy jsou vrchol-tranzitivní a ${ displaystyle (m + n-2)}$-pravidelný; jsou to jediné pravidelné grafy vytvořené z tahů standardních šachových figur tímto způsobem.^[8] Když ${ displaystyle m neq n}$, symetrie grafu věže jsou tvořeny nezávislou permutací řádků a sloupců grafu, takže skupina automorfismu grafu má ${ displaystyle m! n!}$ elementy. Když ${ displaystyle m = n}$, graf má další symetrie, které zaměňují řádky a sloupce, takže počet automorfismů je ${ displaystyle 2n! ^ {2}}$.^[9]

Jakékoli dva vrcholy v grafu věže jsou buď ve vzdálenosti jeden nebo dva od sebe, podle toho, zda sousedí, nebo nesousedí. Libovolné dva nesousedící vrcholy mohou být transformovány na jakékoli další dva nesousedící vrcholy symetrií grafu. Pokud graf věže není čtvercový, páry sousedních vrcholů se rozpadnou na dva oběžné dráhy skupiny symetrie podle toho, zda sousedí vodorovně nebo svisle, ale když je graf čtvercový, mohou být do sebe navzájem mapovány také dva sousední vrcholy pomocí symetrie a graf je tedy vzdálenost-tranzitivní.^[10]

Když ${ displaystyle m}$ a ${ displaystyle n}$ jsou relativně prime, skupina symetrie ${ displaystyle S_ {m} krát S_ {n}}$ grafu věže obsahuje jako podskupinu cyklická skupina ${ displaystyle C_ {mn} = C_ {m} krát C_ {n}}$ že činy cyklickou permutací ${ displaystyle mn}$ vrcholy; proto je v tomto případě graf věže a oběhový graf.^[11]

Grafy čtvercové věže jsou připojeno-homogenní, což znamená, že každý izomorfismus mezi dvěma spojenými indukovanými podgrafy lze rozšířit na automorfismus celého grafu.^[12]

Dokonalost

Graf věže 3 × 3 (graf 3-3 duoprism ), zbarvený třemi barvami a zobrazující kliku tří vrcholů. V tomto grafu a v každém z jeho indukovaných podgrafů se chromatické číslo rovná číslu kliky, takže je to dokonalý graf.

Graf věže lze také zobrazit jako hranový graf a kompletní bipartitní graf K._n,m - to znamená, že má jeden vrchol pro každou hranu K._n,ma dva vrcholy grafu věže sousedí právě tehdy, pokud odpovídající hrany úplného bipartitního grafu sdílejí společný koncový bod.^[13] V tomto pohledu je hrana v úplném bipartitním grafu z ith vrchol na jedné straně bipartice k jten vrchol na druhé straně odpovídá čtverci šachovnice se souřadnicemi (i, j).^[1]

Žádný bipartitní graf je podgraf úplného bipartitního grafu a odpovídajícím způsobem jakýkoli spojnicový graf bipartitního grafu je indukovaný podgraf grafu věže.^[14] Čárové grafy bipartitních grafů jsou perfektní: v nich a v jakémkoli z jejich indukovaných podgrafů počet barev potřebných v jakémkoli vrchol zbarvení je stejný jako počet vrcholů v největším kompletní podgraf. Čárové grafy bipartitních grafů tvoří důležitou rodinu dokonalých grafů: jsou jednou z malého počtu rodin používaných Chudnovsky a kol. (2006) charakterizovat dokonalé grafy a ukázat, že každý graf bez liché díry a liché antihole je dokonalý.^[15] Zejména grafy věže jsou samy o sobě dokonalé.

Vzhledem k tomu, že graf věže je dokonalý, počet barev potřebných pro jakékoli zbarvení grafu je jen velikost jeho největší kliky. Kliky grafu věže jsou podmnožinami jeho řádků a sloupců a největší z nich mají velikost max (m, n), takže toto je také chromatické číslo grafu. An n-barvení an n × n graf věže lze interpretovat jako a Latinský čtverec: popisuje způsob vyplňování řádků a sloupců souboru n × n mřížka s n různé hodnoty takovým způsobem, aby se stejná hodnota neobjevila dvakrát v žádném řádku nebo sloupci.^[16] Ačkoli je nalezení optimálního zbarvení grafu věže jednoduché, je NP-kompletní určit, zda lze částečné zbarvení rozšířit na zbarvení celého grafu (tento problém se nazývá rozšíření předbarvení ). Ekvivalentně je NP-úplné určit, zda lze částečný latinský čtverec doplnit na celý latinský čtverec.^[17]

Nezávislost

	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

Neútočící umístění osmi věží na šachovnici, tvořící maximální nezávislou množinu v grafu odpovídající věže

An nezávislá sada v grafu věže je sada vrcholů, z nichž žádné dva nepatří do stejného řádku nebo sloupce grafu; v šachu to odpovídá umístění věží, z nichž dva na sebe neútočí. Dokonalé grafy lze také popsat jako grafy, ve kterých se v každém indukovaném podgrafu velikost největší nezávislé množiny rovná počtu klik v rozdělení vrcholů grafu na minimální počet klik. V grafu věže tvoří sady řádků nebo sady sloupců (podle toho, které mají méně sad) takový optimální oddíl. Velikost největší nezávislé množiny v grafu je proto min (m, n).^[1] Každá barevná třída v každém optimálním zabarvení grafu věže je maximální nezávislá množina.

Rookovy grafy jsou dobře pokryté grafy: každý nezávislá sada v grafu věže lze rozšířit na maximální nezávislou množinu, a to každý maximální nezávislá množina v grafu věže má stejnou velikost, min (m, n).^[18]

Nadvláda

The dominantní číslo grafu je minimální mohutnost mezi všemi dominujícími množinami. Na grafu věže je sada vrcholů dominující množinou právě tehdy, pokud jejich odpovídající čtverce buď zabírají, nebo se pohybují ve věži od všech čtverců na m × n prkno. Pro m × n palubní číslo je min (m, n).^[19]

Na grafu věže a k-dominující sada je sada vrcholů, jejichž odpovídající čtverce útočí na všechny ostatní čtverce (prostřednictvím pohybu věže) alespoň k krát. A k-tuple dominující množina na grafu věže je sada vrcholů, jejichž odpovídající čtverce útočí na všechny ostatní čtverce alespoň k a jsou sami napadeni minimálně k − 1 krát. Minimální mohutnost mezi všemi k-dominování a k-tuple dominující sady jsou k-dominační číslo a k-tuple dominantní číslo. Na čtvercové desce a dokonce k, k-dominační číslo je nk/2 když n ≥ (k² − 2k)/4 a k < 2n. Podobným způsobem také k-tuple dominantní číslo je n(k + 1)/2 když k je liché a menší než 2n.^[20]

Viz také

3-3 duoprism

• 3-3 duoprism, 4-dimenzionální polytop mající ${ displaystyle 3 krát 3}$ věžový graf jako graf jeho vrcholů a hran
• Kingův graf a Rytířský graf, dva další grafy definované z tahů šachových figurek
• Příhradový graf, graf vodorovných a svislých sousedství čtverců na šachovnici
• Sudoku graf, supergraf grafu věže spojující čtverce logické hry Sudoku, které by měly mít nerovné hodnoty

Reference

externí odkazy

• Weisstein, Eric W. „Lattice Graph“. MathWorld.