Bástyaszám

bástyaszám

Bástyaszám 8x8
Csúcsok nm
borda nm ( n + m )/2- nm
Átmérő 2
Heveder 3 (ha max( n , m ) ≥ 3)
Kromatikus szám max( n , m )
Tulajdonságok szabályos
vertex-tranzitív
tökéletes
jól fedett
 Médiafájlok a Wikimedia Commons oldalon

A gráfelméletben a bástya gráf egy olyan gráf , amely a sakktáblán lévő bástya összes megengedett lépését ábrázolja  – minden csúcs egy cellát jelöl a táblán , az élek pedig a lehetséges mozgásokat. A bástyagráfok nagyon szimmetrikus tökéletes gráfok  – leírhatók a háromszögek számával, amelyekhez egy él tartozik, és egy 4 hosszúságú ciklus létezésével, amely bármely két nem szomszédos csúcsot tartalmaz.

Definíció

Az n  ×  m -es bástya grafikon egy n  ×  m -es táblán megengedett bástyamozgásokat ábrázolja . A gráf csúcsai megadhatók ( x , y ), ahol 1 ≤  x  ≤  n és 1 ≤  y  ≤  m . Két csúcs ( x 1 , y 1 ) és ( x 2 , y 2 ) akkor és csak akkor szomszédos , ha x 1  =  x 2 vagy y 1  =  y 2 . Vagyis ha ugyanazon a sejtvonalon fekszenek (vízszintesen vagy függőlegesen).

Egy n  ×  m -es rook gráf esetén a csúcsok teljes száma nm . Egy n  ×  n négyzettábla esetén a bástya gráf csúcsainak száma egyenlő , az élek száma pedig egyenlő . Az utóbbi esetben a gráf kétdimenziós Hamming-gráfként ismert .

Egy n  ×  m -es táblán lévő bástya gráf két teljes gráf K n K m közvetlen szorzataként definiálható . A 2× n -es bástya gráfjának  komplementere egy korona .

Szimmetria

A Rook gráfok csúcstranzitívak és ( n  +  m  − 2) -regulárisak . Ez a szabályos gráfok egyetlen osztálya, amely szabványos sakkfigurák mozdulatai alapján összeállítható [1] . Ha m  ≠  n , akkor a bástya gráf szimmetriáit a gráf sorainak és oszlopainak független permutációi alkotják. Ha n  =  m , akkor a gráfnak további szimmetriái vannak, amelyek felcserélik a sorokat és az oszlopokat. A négyzet alakú sakktábla bástya grafikonja szimmetrikus .

A bástya gráf bármely két csúcsa egy vagy kettő távolságra van egymástól, attól függően, hogy szomszédosak-e vagy sem. Bármely két nem szomszédos csúcs leképezhető bármely két másik nem szomszédos csúcsra gráfszimmetria segítségével. Ha a bástya gráf nem négyzet alakú, akkor a szomszédos csúcspárok szomszédságuk szerint a szimmetriacsoport két pályájára hasadnak - vízszintesen vagy függőlegesen, de négyzetes gráf esetén bármelyik két szomszédos csúcs átvihető egyikből a másikba. szimmetria, és így a gráf távolságtranzitív .

Ha m és n relatív prím , akkor a bástya gráfjának S m × S n szimmetriacsoportja alcsoportként tartalmazza a C mn  =  C m × C n ciklikus csoportot , amely mn csúcs ciklikus permutálásával működik . Így ebben az esetben a bástya gráfja körkörös .

Tökéletesség

A bástya gráfot a teljes kétrészes gráf K n , m vonalgráfjának tekinthetjük . Ez azt jelenti, hogy minden K n élhez van egy csúcsa , m és a bástya gráf két csúcsa akkor és csak akkor szomszédos, ha a teljes kétrészes gráf megfelelő éleinek közös csúcsa van. Ebből a szempontból az egyik oldal i csúcsát a másik oldal j csúcsával összekötő bipartit gráf éle egy ( i , j ) koordinátákkal rendelkező sakktábla cellának felel meg .

Bármely kétrészes gráf egy teljes kétrészes gráf részgráfja , ami azt jelenti, hogy egy kétrészes gráf bármely vonalgráfja egy bástya gráfjának generált részgráfja. A kétrészes gráfok vonalgráfjai tökéletesek  - benne és bármelyik generált részgráfjában a csúcsok tetszőleges színezéséhez szükséges színek száma megegyezik a legnagyobb klikk csúcsainak számával . A kétrészes gráfok vonalgráfjai a tökéletes gráfok fontos családját alkotják, egyike azoknak a kevés családnak, amelyeket Chudnovskaya és munkatársai [2] használtak a tökéletes gráfok leírására és annak bemutatására, hogy minden páratlan lyukak és antilyukak nélküli gráf tökéletes. Különösen a bástya grafikonjai tökéletesek.

Mivel a bástya grafikonok tökéletesek, a grafikon színezéséhez szükséges színek száma megegyezik a legnagyobb klikk méretével. Egy bástya gráfjának klikkjei a sorok és oszlopok részhalmazai, amelyek közül a legnagyobb max( m , n ) méretű, tehát ez a szám a gráf kromatikus száma. Egy n × n -es bábu gráf n színezése latin négyzetként fogható fel – egy n × n -es rács sorainak és oszlopainak n különböző értékkel  való kitöltésének módját írja le úgy , hogy egyetlen érték se jelenjen meg kétszer a sorokban. és oszlopok.

Független halmaz a bástya gráfban olyan csúcsok halmaza, amelyek közül kettő nem tartozik a gráf ugyanahhoz a sorához vagy oszlopához. A sakk szempontjából ez a bástya elrendezésének felel meg, amelyek közül kettő nem támadja meg egymást. A tökéletes gráfok olyan gráfokként is leírhatók, amelyekben bármely generált részgráf esetén a legnagyobb független halmaz mérete megegyezik a gráf csúcsainak a minimális számú klikkre való felbontása során előforduló klikkek számával. Egy bástyás gráfban a sorok vagy oszlopok halmaza (amelyik kisebb) ilyen optimális dekompozíciót alkot. A legnagyobb független halmaz mérete tehát min( m , n ). Bármilyen optimális színezés egy bástya gráfban egy maximális független halmaz.

Leírás

A Hold [3] az m × n bábugráfot írja le , mint az egyetlen gráfot, amely a következő tulajdonságokkal rendelkezik:

Ha n  =  m , akkor ezek a feltételek leegyszerűsíthetők, és azt mondják, hogy az n × n rook gráf egy erősen szabályos gráf srg( n 2 , 2 n  − 2,  n  − 2, 2) paraméterekkel, és hogy minden erősen szabályos gráf ezeknek a paramétereknek egy n × n oszlopgráfnak kell lenniük, ha n ≠ 4. Ha n = 4, akkor van egy másik erősen szabályos gráf, mégpedig a Shrikhande gráf , amely ugyanazokkal a paraméterekkel rendelkezik, mint a 4 × 4-es bástya gráf. A Shrikhande gráf abban különbözik a 4×4-es bástya gráftól, hogy a Shrikhande gráf bármely csúcsának szomszédsága egy 6 hosszúságú ciklusban kapcsolódik, míg a bástya gráfban két háromszöghez tartoznak.

Uralkodás

A gráf dominancia száma a minimális halmazméret az összes domináns halmaz között. A bástya gráfban a csúcsok halmaza akkor és csak akkor domináns halmaz, ha a tábla bármely cellája a halmazhoz tartozik, vagy egy lépésnyire van a halmaz elemétől. Egy m × n tábla esetén a dominanciaszám min( m , n ) [4] .

Rook gráf esetén a k -domináns halmaz azoknak a csúcsoknak a halmaza, amelyeknek a megfelelő cellái legalább k - szer megtámadják az összes többi cellát (rook mozgással). Egy bástya gráf k -szeres domináns halmaza azoknak a csúcsoknak a halmaza, amelyeknek a megfelelő cellái legalább k-szer megtámadják az összes többi sejtet (a bástya mozdulatával), és legalább k −  1-szer megtámadják a saját sejtjeit . Az összes k -szeres domináns halmaz és k -szeres domináns halmaz között a minimális méret k -szeres domináns szám, illetve k -szeres domináns szám. Négyzettáblán páros k esetén a k -domináns szám nk /2 n  ≥ ( k 2  − 2 k )/4 és k  < 2 n esetén . Hasonlóképpen , a k - szeres domináns szám n ( k  + 1)/2, ha k páratlan és kisebb, mint 2n [5] .

Lásd még

Jegyzetek

  1. ↑ Elkies, 2004 .
  2. ↑ Chudnovsky, Robertson, Seymour, Thomas, 2006 .
  3. ↑ Hold, 1963 .
  4. ↑ Yaglom és Yaglom, 1987 .
  5. ↑ Burchett, Lane, Lachniet, 2009 .

Irodalom

Linkek