У теорії графів туровий граф — граф, що представляє всі допустимі ходи тури на шахівниці: кожна вершина представляє клітинку на дошці, а ребра — можливі ходи. Турові графи є вкрай симетричними досконалими графами — їх можна описати в термінах числа трикутників, яким належить ребро, та існування циклу довжини 4, що включає будь-які дві несуміжні вершини.
Туровий граф | |
---|---|
Туровий граф 8x8 | |
(Вершин) | |
(Ребер) | |
(Діаметр) | 2 |
(Обхват) | 3 (якщо ) |
Хроматичне число | |
Властивості | регулярний вершинно-транзитивний досконалий |
Визначення
Туровий граф представляє допустимі ходи тури на дошці . Вершинам графа можна задати координати , де та . Дві вершини та суміжні тоді і лише тоді, коли або або . Тобто якщо вони лежать в одному рядку клітин (горизонтальному або вертикальному).
Для турового графа загальна кількість вершин дорівнює . Для квадратної дошки число вершин турового графа дорівнює і число ребер дорівнює . В останньому разі граф відомий як двовимірний граф Геммінга.
Туровий граф на дошці можна визначити як прямий добуток двох повних графів . Доповнення турового графа є короною.
Симетрія
Турові графи вершинно-транзитивні та -регулярні. Це єдиний клас регулярних графів, який можна побудувати на основі ходів стандартних шахових фігур. Якщо , симетрії турових графів утворено незалежними перестановками рядків та стовпців графа. Якщо , у графа з'являються додаткові симетрії, які обмінюють рядки та стовпці. Туровий граф для квадратної шахівниці є симетричним.
Відстань між будь-якими двома вершинами турового графа дорівнює одиниці або двом, залежно від того, суміжні вони чи ні. Будь-які дві несуміжні вершини можна перевести в будь-які інші несуміжні вершини за допомогою симетрії графа. Якщо туровий граф не квадратний, пари суміжних вершин розпадаються на дві орбіти групи симетрій відповідно до їх суміжності — по горизонталі або по вертикалі, але в разі квадратного графа будь-які дві суміжні вершини можна перевести з однієї в іншу за допомогою симетрії і, таким чином, граф дистанційно-транзитивний.
Якщо і взаємно прості, група симетрій турового графа містить як підгрупу циклічну групу , яка діє шляхом перестановки вершин циклічно. Отже, в цьому випадку туровий граф є циркулянтним.
Досконалість
Туровий граф можна розглядати як реберний граф повного двочасткового графа . Тобто, він має по вершині для кожного ребра і дві вершини турового графа суміжні тоді й лише тоді, коли відповідні ребра повного двочасткового графа мають спільну вершину. З цього погляду ребро двочасткового графа, що з'єднує вершину однієї сторони з вершиною іншої сторони, відповідає клітинці шахівниці з координатами .
Будь-який двочастковий граф є підграфом повного двочасткового графа, отже будь-який реберний граф двочасткового графа є породженим підграфом турового графа. Реберний граф двочасткового графа досконалий — в ньому і в будь-якому його породженому підграфі число кольорів, необхідних для будь-якого розфарбування вершин, дорівнює кількості вершин у найбільшій кліці. Реберні графи двочасткових графів утворюють важливе сімейство досконалих графів, одне з небагатьох сімейств, використаних Чудновською зі співавторами для опису досконалих графів і для того, щоб показати, що будь-який граф без непарних дір і антидір досконалий. Зокрема, досконалими є турові графи.
Оскільки турові графи досконалі, кількість кольорів, які потрібні для розфарбвання графа, дорівнює розміру найбільшої кліки. Кліки турового графа є підмножинами його рядків і стовпців і найбільша має розмір , отже, це число є хроматичним числом графа. -колірне розфарбування турового графа можна розглядати як латинський квадрат — він описує спосіб заповнення рядків і стовпців -ґратки різними значеннями, за якого жодне значення не з'являється двічі в рядках і стовпцях.
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 |
Незалежна множина в туровому графі — це множина вершин, жодні дві з яких не належать одному рядку або стовпцю графа. У термінах шахів це відповідає розташуванню тур, жодні дві з яких не атакують одна одну. Досконалі графи можна також описати як графи, в яких для будь-якого породженого підграфа розмір найбільшої незалежної множини дорівнює числу клік у розкладі вершин графа на найменше число клік. У туровому графі множина рядків або стовпців (менша з них) утворює такий оптимальний розклад. Отже, розмір найбільшої незалежної множини дорівнює . Будь-яке оптимальне розфарбування в туровому графі є найбільшою незалежною множиною.
Опис
Мун описує туровий граф як єдиний граф, що має такі властивості:
- він має вершин, кожна з яких інцидентна ребрам;
- ребер належать трикутникам, а решта ребер належать трикутникам;
- будь-які дві несуміжні вершини належать єдиному циклу із 4 вершин.
Якщо , ці умови можна спростити до твердження, що граф є сильно регулярним графом з параметрами , і що будь-який сильно регулярний граф з такими параметрами має бути туровим графом якщо . Якщо , існує ще один регулярний граф, а саме, граф Шрікханде, який має такі ж параметри, що й туровий граф . Граф Шрікханде відрізняється від турового графа тим, що окіл будь-якої вершини графа Шрікханде пов'язаний у цикл довжини 6, тоді як у туровому графі він належить двом трикутникам.
Домінування
Число домінування графа — це найменший розмір множини серед усіх домінівних множин. У туровому графі множина вершин є домінівною множиною тоді й лише тоді, коли будь-яка клітинка дошки або належать до множини, або за один хід від елемента множини. Для дошки число домінування дорівнює .
Для турового графа -домінівна множина — це множина вершин, відповідні клітинки яких атакують усі інші клітинки (ходом тури) принаймні разів. -кратна домінівна множина для турового графа — це множина вершин, відповідні клітинки яких атакують усі інші клітинки (ходом тури) принаймні разів і атакують свої клітинки не менше разів. Найменший розмір серед усіх -домінівних множин і -кратних домінівних множин — це -домінівне число і -кратне домінівне число відповідно. На квадратній дошці для парних -домінівне число дорівнює при та . Аналогічно -кратне домінівне число дорівнює коли непарне і менше ніж .
Див. також
Примітки
Література
- Ján Beka. Kn-decomposition of the line graphs of complete bipartite graphs // Octogon Mathematical Magazine. — 2001. — Т. 9, вип. 1A. — С. 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-domination and k-tuple domination on the rook's graph and other results // . — 2009. — Т. 199. — С. 187—204.
- Maria Chudnovsky, Neil Robertson, Paul Seymour, Robin Thomas. The strong perfect graph theorem // Annals of Mathematics. — 2006. — Т. 164, вип. 1. — С. 51—229. — DOI: .
- [en]. Graph theory glossary. — 2004.
- A. J. Hoffman. On the line graph of the complete bipartite graph // . — 1964. — Т. 35, вип. 2. — С. 883—885. — DOI: .
- 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. Chessboard graphs, related designs, and domination parameters // Journal of Statistical Planning and Inference. — 1999. — Т. 76, вип. 1—2. — С. 285—294. — DOI: .
- van der Hofstad, Remco; Luczak, Malwina J. & Spencer, Joel (2008), The second largest component in the supercritical 2D Hamming graph, arΧiv:0801.1608 [math.PR].
- G. MacGillivray, K. Seyffarth. Classes of line graphs with small cycle double covers // Australasian Journal of Combinatorics. — 2001. — Т. 24. — С. 91—114.
- J. W. Moon. On the line-graph of the complete bigraph // . — 1963. — Т. 34, вип. 2. — С. 664—667. — DOI: .
- D. de Werra, A. Hertz. On perfectness of sums of graphs // . — 1999. — Т. 195, вип. 1—3. — С. 93—101. — DOI: .
- Яглом А. М., Яглом И. М. Неэлементарные задачи в элементарном изложении. — Dover, 1987.
Посилання
- Weisstein, Eric W. Граф решітки(англ.) на сайті Wolfram MathWorld.
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
U teoriyi grafiv turovij graf graf sho predstavlyaye vsi dopustimi hodi turi na shahivnici kozhna vershina predstavlyaye klitinku na doshci a rebra mozhlivi hodi Turovi grafi ye vkraj simetrichnimi doskonalimi grafami yih mozhna opisati v terminah chisla trikutnikiv yakim nalezhit rebro ta isnuvannya ciklu dovzhini 4 sho vklyuchaye bud yaki dvi nesumizhni vershini Turovij grafTurovij graf 8x8Vershinn m displaystyle nm Rebern m n m 2 n m displaystyle nm n m 2 nm Diametr2Obhvat3 yaksho m a x n m 3 displaystyle max n m geq 3 Hromatichne chislom a x n m displaystyle max n m Vlastivostiregulyarnij vershinno tranzitivnij doskonalijViznachennyaTurovij graf n m displaystyle n times m predstavlyaye dopustimi hodi turi na doshci n m displaystyle n times m Vershinam grafa mozhna zadati koordinati x y displaystyle x y de 1 x n displaystyle 1 leq x leq n ta 1 y m displaystyle 1 leq y leq m Dvi vershini x 1 y 1 displaystyle x 1 y 1 ta x 2 y 2 displaystyle x 2 y 2 sumizhni todi i lishe todi koli abo x 1 x 2 displaystyle x 1 x 2 abo y 1 y 2 displaystyle y 1 y 2 Tobto yaksho voni lezhat v odnomu ryadku klitin gorizontalnomu abo vertikalnomu Dlya turovogo grafa n m displaystyle n times m zagalna kilkist vershin dorivnyuye n m displaystyle nm Dlya kvadratnoyi doshki n n displaystyle n times n chislo vershin turovogo grafa dorivnyuye n 2 displaystyle n 2 i chislo reber dorivnyuye n 3 n 2 displaystyle n 3 n 2 V ostannomu razi graf vidomij yak dvovimirnij graf Gemminga Turovij graf na doshci n m displaystyle n times m mozhna viznachiti yak pryamij dobutok dvoh povnih grafiv K n K m displaystyle K n square K m Dopovnennya turovogo grafa 2 n displaystyle 2 times n ye koronoyu SimetriyaTurovi grafi vershinno tranzitivni ta n m 2 displaystyle n m 2 regulyarni Ce yedinij klas regulyarnih grafiv yakij mozhna pobuduvati na osnovi hodiv standartnih shahovih figur Yaksho m n displaystyle m neq n simetriyi turovih grafiv utvoreno nezalezhnimi perestanovkami ryadkiv ta stovpciv grafa Yaksho n m displaystyle n m u grafa z yavlyayutsya dodatkovi simetriyi yaki obminyuyut ryadki ta stovpci Turovij graf dlya kvadratnoyi shahivnici ye simetrichnim Vidstan mizh bud yakimi dvoma vershinami turovogo grafa dorivnyuye odinici abo dvom zalezhno vid togo sumizhni voni chi ni Bud yaki dvi nesumizhni vershini mozhna perevesti v bud yaki inshi nesumizhni vershini za dopomogoyu simetriyi grafa Yaksho turovij graf ne kvadratnij pari sumizhnih vershin rozpadayutsya na dvi orbiti grupi simetrij vidpovidno do yih sumizhnosti po gorizontali abo po vertikali ale v razi kvadratnogo grafa bud yaki dvi sumizhni vershini mozhna perevesti z odniyeyi v inshu za dopomogoyu simetriyi i takim chinom graf distancijno tranzitivnij Yaksho m displaystyle m i n displaystyle n vzayemno prosti grupa simetrij S m S n displaystyle S m times S n turovogo grafa mistit yak pidgrupu ciklichnu grupu C m n C m C n displaystyle C mn C m times C n yaka diye shlyahom perestanovki m n displaystyle mn vershin ciklichno Otzhe v comu vipadku turovij graf ye cirkulyantnim Doskonalist3 3 turovij graf rozfarbovanij troma kolorami v yakomu pokazano kliku yaka maye tri vershini U comu grafi i v usih jogo porodzhenih pidgrafah hromatichne chislo dorivnyuye klikovomu chislu tomu vin ye doskonalim Turovij graf mozhna rozglyadati yak rebernij graf povnogo dvochastkovogo grafa K n m displaystyle K n m Tobto vin maye po vershini dlya kozhnogo rebra K n m displaystyle K n m i dvi vershini turovogo grafa sumizhni todi j lishe todi koli vidpovidni rebra povnogo dvochastkovogo grafa mayut spilnu vershinu Z cogo poglyadu rebro dvochastkovogo grafa sho z yednuye vershinu i displaystyle i odniyeyi storoni z vershinoyu j displaystyle j inshoyi storoni vidpovidaye klitinci shahivnici z koordinatami i j displaystyle i j Bud yakij dvochastkovij graf ye pidgrafom povnogo dvochastkovogo grafa otzhe bud yakij rebernij graf dvochastkovogo grafa ye porodzhenim pidgrafom turovogo grafa Rebernij graf dvochastkovogo grafa doskonalij v nomu i v bud yakomu jogo porodzhenomu pidgrafi chislo koloriv neobhidnih dlya bud yakogo rozfarbuvannya vershin dorivnyuye kilkosti vershin u najbilshij klici Reberni grafi dvochastkovih grafiv utvoryuyut vazhlive simejstvo doskonalih grafiv odne z nebagatoh simejstv vikoristanih Chudnovskoyu zi spivavtorami dlya opisu doskonalih grafiv i dlya togo shob pokazati sho bud yakij graf bez neparnih dir i antidir doskonalij Zokrema doskonalimi ye turovi grafi Oskilki turovi grafi doskonali kilkist koloriv yaki potribni dlya rozfarbvannya grafa dorivnyuye rozmiru najbilshoyi kliki Kliki turovogo grafa ye pidmnozhinami jogo ryadkiv i stovpciv i najbilsha maye rozmir m a x m n displaystyle max m n otzhe ce chislo ye hromatichnim chislom grafa n displaystyle n kolirne rozfarbuvannya n n displaystyle n times n turovogo grafa mozhna rozglyadati yak latinskij kvadrat vin opisuye sposib zapovnennya ryadkiv i stovpciv n n displaystyle n times n gratki n displaystyle n riznimi znachennyami za yakogo zhodne znachennya ne z yavlyayetsya dvichi v ryadkah i stovpcyah abcdefgh 8877 66 55 44 33 22 11 abcdefgh Roztashuvannya vosmi tur na shahivnici tak sho voni ne b yut odna odnu Ci turi utvoryuyut najbilshu nezalezhnu mnozhinu u vidpovidnomu turovomu grafi Nezalezhna mnozhina v turovomu grafi ce mnozhina vershin zhodni dvi z yakih ne nalezhat odnomu ryadku abo stovpcyu grafa U terminah shahiv ce vidpovidaye roztashuvannyu tur zhodni dvi z yakih ne atakuyut odna odnu Doskonali grafi mozhna takozh opisati yak grafi v yakih dlya bud yakogo porodzhenogo pidgrafa rozmir najbilshoyi nezalezhnoyi mnozhini dorivnyuye chislu klik u rozkladi vershin grafa na najmenshe chislo klik U turovomu grafi mnozhina ryadkiv abo stovpciv mensha z nih utvoryuye takij optimalnij rozklad Otzhe rozmir najbilshoyi nezalezhnoyi mnozhini dorivnyuye m i n m n displaystyle min m n Bud yake optimalne rozfarbuvannya v turovomu grafi ye najbilshoyu nezalezhnoyu mnozhinoyu OpisMun opisuye turovij graf m n displaystyle m times n yak yedinij graf sho maye taki vlastivosti vin maye m n displaystyle mn vershin kozhna z yakih incidentna n m 2 displaystyle n m 2 rebram m n m 1 2 displaystyle mn m 1 2 reber nalezhat m 2 displaystyle m 2 trikutnikam a reshta m n n 1 2 displaystyle mn n 1 2 reber nalezhat n 2 displaystyle n 2 trikutnikam bud yaki dvi nesumizhni vershini nalezhat yedinomu ciklu iz 4 vershin Yaksho n m displaystyle n m ci umovi mozhna sprostiti do tverdzhennya sho graf n n displaystyle n times n ye silno regulyarnim grafom z parametrami s r g n 2 2 n 2 n 2 2 displaystyle srg n 2 2n 2 n 2 2 i sho bud yakij silno regulyarnij graf z takimi parametrami maye buti turovim grafom n n displaystyle n times n yaksho n 4 displaystyle n neq 4 Yaksho n 4 displaystyle n 4 isnuye she odin regulyarnij graf a same graf Shrikhande yakij maye taki zh parametri sho j turovij graf 4 4 displaystyle 4 times 4 Graf Shrikhande vidriznyayetsya vid turovogo grafa 4 4 displaystyle 4 times 4 tim sho okil bud yakoyi vershini grafa Shrikhande pov yazanij u cikl dovzhini 6 todi yak u turovomu grafi vin nalezhit dvom trikutnikam DominuvannyaChislo dominuvannya grafa ce najmenshij rozmir mnozhini sered usih dominivnih mnozhin U turovomu grafi mnozhina vershin ye dominivnoyu mnozhinoyu todi j lishe todi koli bud yaka klitinka doshki abo nalezhat do mnozhini abo za odin hid vid elementa mnozhini Dlya doshki m n displaystyle m times n chislo dominuvannya dorivnyuye m i n m n displaystyle min m n Dlya turovogo grafa k displaystyle k dominivna mnozhina ce mnozhina vershin vidpovidni klitinki yakih atakuyut usi inshi klitinki hodom turi prinajmni k displaystyle k raziv k displaystyle k kratna dominivna mnozhina dlya turovogo grafa ce mnozhina vershin vidpovidni klitinki yakih atakuyut usi inshi klitinki hodom turi prinajmni k displaystyle k raziv i atakuyut svoyi klitinki ne menshe k 1 displaystyle k 1 raziv Najmenshij rozmir sered usih k displaystyle k dominivnih mnozhin i k displaystyle k kratnih dominivnih mnozhin ce k displaystyle k dominivne chislo i k displaystyle k kratne dominivne chislo vidpovidno Na kvadratnij doshci dlya parnih k displaystyle k k displaystyle k dominivne chislo dorivnyuye n k 2 displaystyle nk 2 pri n k 2 2 k 4 displaystyle n geq k 2 2k 4 ta k lt 2 n displaystyle k lt 2n Analogichno k displaystyle k kratne dominivne chislo dorivnyuye n k 1 2 displaystyle n k 1 2 koli k displaystyle k neparne i menshe nizh 2 n displaystyle 2n Div takozhGraf hodiv korolya Graf hodiv konya Reshitka Graf GejmsaPrimitkiElkies 2004 Chudnovsky Robertson Seymour Thomas 2006 Moon 1963 Yaglom i Yaglom 1987 Burchett Lane Lachniet 2009 LiteraturaJan Beka Kn decomposition of the line graphs of complete bipartite graphs Octogon Mathematical Magazine 2001 T 9 vip 1A S 135 139 Bekmetjev Airat amp Hurlbert Glenn 2004 The pebbling threshold of the square of cliques arXiv math CO 0406157 math CO Berger Wolf Tanya Y amp Harris Mitchell A 2003 Sharp bounds for bandwidth of clique products arXiv cs DM 0305051 cs DM Paul Burchett David Lane Jason Lachniet K domination and k tuple domination on the rook s graph and other results 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 vip 1 S 51 229 DOI 10 4007 annals 2006 164 51 en Graph theory glossary 2004 A J Hoffman On the line graph of the complete bipartite graph 1964 T 35 vip 2 S 883 885 DOI 10 1214 aoms 1177703593 van der Hofstad Remco amp Luczak Malwina J 2008 Random subgraphs of the 2D Hamming graph the supercritical phase arXiv 0801 1607 math PR Renu Laskar Charles Wallis Chessboard graphs related designs and domination parameters Journal of Statistical Planning and Inference 1999 T 76 vip 1 2 S 285 294 DOI 10 1016 S0378 3758 98 00132 3 van der Hofstad Remco Luczak Malwina J amp Spencer Joel 2008 The second largest component in the supercritical 2D Hamming graph arXiv 0801 1608 math PR G MacGillivray K Seyffarth Classes of line graphs with small cycle double covers Australasian Journal of Combinatorics 2001 T 24 S 91 114 J W Moon On the line graph of the complete bigraph 1963 T 34 vip 2 S 664 667 DOI 10 1214 aoms 1177704179 D de Werra A Hertz On perfectness of sums of graphs 1999 T 195 vip 1 3 S 93 101 DOI 10 1016 S0012 365X 98 00168 X Yaglom A M Yaglom I M Neelementarnye zadachi v elementarnom izlozhenii Dover 1987 PosilannyaWeisstein Eric W Graf reshitki angl na sajti Wolfram MathWorld