A matematika, azon belül a gráfelmélet területén egy bástyagráf (rook's graph) olyan gráf, ami a sakkjátékban szereplő bástya nevű figura lehetséges lépéseit jeleníti meg egy sakktáblán: a csúcsok a sakktábla egy-egy mezőjét jelképezik, az élek pedig a legális lépéseket köztük. A bástyagráfok erősen szimmetrikus, perfekt gráfok; jellemző rájuk, hogy éleik hány háromszöghöz tartoznak, valamint a nem szomszédos csúcspárokat összekötő -körök létezése. A bástyagráf a sakkfigurák gráfjai között (futógráf, huszárgráf, királygráf, vezérgráf) egyedülálló szimmetriákat és regularitást mutat.

Definíció és jellemzés Egy -es bástyagráf a bástya lépési lehetőségeit mutatja meg egy -es sakktáblán. Csúcsaihoz koordináták rendelhetők, ahol és egész számok. Az , illetve csúcsok pontosan akkor szomszédosak, ha az és az állítások valamelyike igaz; tehát ha a sakktábla azonos oszlopában vagy sorában találhatóak.

Egy -es bástyagráfnál a csúcsok száma , az -es bástyagráfnál (amilyen a normál sakktábla is, n=8), a csúcsok száma , az élek száma pedig ; ebben az esetben a gráf egy kétdimenziós Hamming-gráf vagy latin négyzet-gráf.

Minden bástyagráf 2-összefüggő és rendelkezik Hamilton-körrel az elfajult n=1 vagy m=1 eset kivételével. A bástyagráf speciális esete az 1×n-es sakktáblán a teljes gráf.

Egy -es bástyagráf meghatározható úgy is, mint a és teljes gráfok Descartes-szorzata, képlettel kifejezve . A -es bástyagráf komplementere egy koronagráf.

és jellemzése alapján az -es bástyagráfok a következő egyedi, rájuk jellemző tulajdonságokkal bírnak:.. csúccsal rendelkezik, melyek mindegyikéhez él tartozik. Az élek közül pontosan tartozik háromszöghöz, a maradék él pedig háromszöghöz (a háromszögelés során a bástya megtartja vagy saját sorát, vagy saját oszlopát). Bármely két, nem szomszédos csúcs pontosan egy, rájuk jellemző -körhöz tartozik. Ha , a feltételek rövidebben úgy is megfogalmazhatók, hogy az -es bástyagráf erősen reguláris gráf paraméterekkel, és minden ezekkel a paraméterekkel rendelkező, erősen reguláris gráf egy -es bástyagráf, kivéve, ha . Az esetben létezik még egy, az bástyagráf paramétereivel megegyező erősen reguláris gráf, méghozzá a Shrikhande-gráf. A Shrikhande-gráf és a -bástyagráf könnyen megkülönböztethetők egymástól, mivel a bástyagráf bármely csúcsának szomszédságában két háromszög, a Shrikhande-gráf bármely csúcsának szomszédságában pedig egy -kör található.

Szimmetria A bástyagráfok csúcstranzitív és -reguláris gráfok; ők az egyetlen, standard sakkfigurák mozgását leíró reguláris gráfok.. Ha , a bástyagráf szimmetriái a gráf sorainak, illetve oszlopainak külön-külön permutálásából adódnak. Ha , a gráf további, a sorok és oszlopok felcseréléséből adódó szimmetriákkal is rendelkezik.

A bástyagráf bármely két csúcsa vagy 1 vagy 2 távolságra van egymástól. Bármely két, nem szomszédos csúcs transzformálható másik két nem szomszédos csúccsá a gráf egy szimmetriája segítségével. Ha a bástyagráf nem négyzetes, a szomszédos csúcspárok a szimmetriacsoport két pályájába esnek, attól függően, hogy vízszintesen vagy függőlegesen szomszédosak; ha viszont a gráf négyzetes, bármely két szomszédos csúcs átvihető egymásba egy szimmetria segítségével, ezáltal a gráf távolságtranzitív.

Ha és relatív prímek, a bástyagráf szimmetriacsoportja alcsoportként magában foglalja a ciklikus csoportot, ami az csúcs ciklikus permutációjával hat; ebben az esetben tehát a bástyagráf egy cirkuláns gráf.

Perfektség

A bástyagráf úgy is tekinthető, mint a teljes páros gráf élgráfja – tehát olyan gráf, ami a minden éléhez egy csúcsot tartalmaz, és két csúcsa akkor szomszédosak, ha a teljes páros gráfban a megfelelő élek közös végpontból indulnak.A teljes gráfok Descartes-szorzata és a teljes páros gráfok élgráfja közötti ekvivalenciához lásd: . Így tekintve, a teljes páros gráf egy éle, ami a bipartíció egyik oldalának -edik csúcsa és a bipartíció másik oldalának -edik csúcsa között húzódik, egy sakktábla koordinátájú mezőjének felel meg.

Bármely páros gráf egy teljes páros gráf részgráfja, ennek megfelelően bármely páros gráf élgráfja egy bástyagráf feszített részgráfja. A páros gráfok élgráfjai perfektek: bennük, és bármely feszített részgráfjukban a színezésükhöz szükséges színek száma megegyezik legnagyobb teljes részgráfjuk (klikkjük) csúcsainak számával. A páros gráfok élgráfjai a perfekt gráfok fontos családját alkotják: egyikét alkotják a által a perfekt gráfok karakterizációjához felhasznált kevés számú családnak, melyekkel megmutatták, hogy a páratlan lyukak és páratlan antilyukak nélküli gráfok perfektek.. Továbbá a bástyagráfok maguk is perfektek.

Mivel a bástyagráfok perfektek, a gráf színezéséhez annyi színre van szükség, mint a legnagyobb klikkjének a mérete. A bástyagráfok klikkjei sorainak és oszlopainak részhalmazai, ezek közül a legnagyobbaknak a mérete , tehát ennyi a gráf kromatikus száma is. Egy -es bástyagráf -színezése latin négyzetként is értelmezhető: leírja, hogy lehet az -es rács sorait és oszlopait úgy feltölteni különböző értékkel, hogy ugyanaz az érték ne jelenjen meg egynél többször ugyanabban a sorban vagy oszlopban.A teljes páros gráfok élszínezése és a latin négyzetek ekvivalenciája tárgyában lásd pl. .

Egy bástyagráf független csúcshalmaza olyan csúcsok halmaza, melyek közül semelyik sincs a gráf azonos oszlopában vagy sorában, azaz, sakk-terminológiával élve olyan, a sakktáblán elhelyezett bástyákról van szó, melyek közül semelyik sem áll ütésben a többiek által. A perfekt gráfok úgy is leírhatók, mint olyan gráfok, melyek minden feszített részgráfjában a legnagyobb független csúcshalmaz mérete megegyezik a lehető legkevesebb klikkbe particionálásban a klikkek számával. Egy bástyagráfban a sorok halmaza vagy az oszlopok halmaza (amelyik kisebb) ilyen optimális partíciót alkot. A gráf legnagyobb független csúcshalmazának mérete ezért . A bástyagráf bármely optimális színezésének összes színosztálya maximális elemszámú független csúcshalmazt alkot.

Dominálás Egy gráf dominálási száma a legkisebb domináló halmazának elemszámával egyezik meg. A bástyagráfban egy csúcshalmaz pontosan akkor domináló halmaz, ha az -es sakktáblán nekik megfelelő mezők vagy megegyeznek, vagy egy bástyalépés távolságra vannak a többi mezőtől. Az -es táblán a dominálási szám ..

A bástyagráf egy -domináló halmaza olyan csúcshalmaz, melyhez tartozó mezőkön álló bástyák minden más mezőt legalább -szor támadnak. A bástyagráf -tuple domináló halmaza olyan csúcshalmaz, melyhez tartozó mezőkön álló bástyák minden más mezőt legalább -szor támadnak, és ők maguk is legalább -szer ütésben állnak. A-domináló és -tuple domináló halmazok közül a legkisebb számosságúnak az elemszámát -dominációs számnak, illetve -tuple dominációs számnak nevezik. Négyzetes táblán, páros -ra a -dominációs szám , ha és . Hasonlóan, a -tuple dominációs szám , ha páratlan és kisebb, mint ..

Kapcsolódó szócikkek Futógráf Huszárgráf Királygráf Vezérgráf Rácsgráf

Jegyzetek

További információk

Kategória:Sakk Kategória:Perfekt gráfok Kategória:Parametrikus gráfcsaládok Kategória:Reguláris gráfok Kategória:Erősen reguláris gráfok