Графикті бояу ойыны - Graph coloring game

The графикалық бояу ойыны байланысты математикалық ойын графтар теориясы. Ойынға арналған проблемалар белгілі теоретикалық нұсқалары ретінде пайда болды графикалық бояу мәселелер. Бояу ойында екі ойыншы а-ның бояуын құру үшін берілген түстер жиынтығын пайдаланады график, біз қарастыратын ойынға байланысты нақты ережелерді сақтау. Бір ойыншы графиканың бояуын сәтті аяқтауға тырысады, ал екіншісі оған қол жеткізуге кедергі келтіреді.

Шыңдарды бояуға арналған ойын

The шыңдарды бояуға арналған ойын 1981 жылы Брамс ұсынған[1] және Бодлаендер он жылдан кейін қайта ашты.[2] Оның ережелері келесідей:

  1. Алис пен Боб графтың төбелерін бояйды G жиынтығымен к түстер.
  2. Алиса мен Боб кезектесіп, дұрыс бояу боялмаған шың (стандартты нұсқада Алиса басталады).
  3. Егер шың болса v дұрыс бояу мүмкін емес (кез-келген түс үшін, v онымен боялған көршісі бар), содан кейін Боб жеңеді.
  4. Егер график толығымен боялған болса, онда Алиса жеңеді.

The ойын хроматикалық нөмірі график , деп белгіленеді , бұл Элис үшін шыңдарды бояу ойынында жеңіске жететін минималды түстер саны . Кез-келген график үшін маңызды емес , Бізде бар , қайда болып табылады хроматикалық сан туралы және оның максимумы дәрежесі.[3]

Басқа түсініктермен байланыс

Ациклдық бояу. Әр график бірге ациклді хроматикалық сан бар .[4]

Таңбалау ойыны. Әр график үшін , , қайда болып табылады ойынның бояу нөмірі туралы . Ойынның хроматикалық санының барлық белгілі жоғарғы шегі ойын бояу нөмірінің шектерінен алынады.

Шеттердегі цикл-шектеулер. Егер графиктің әр шеті болса тиесілі циклдар, содан кейін .[5]

Графикалық сыныптар

Сынып үшін графиктерді біз белгілейміз ең кіші бүтін сан әрбір график туралы бар . Басқа сөздермен айтқанда, - бұл сыныптағы графикалық хроматикалық санның нақты жоғарғы шегі. Бұл мән графиктің бірнеше стандартты кластары үшін белгілі, ал басқалары үшін шектелген:

  • Ормандар: .[6] 3 дәрежелі шыңы жоқ орманның ойын хроматикалық санын анықтайтын қарапайым критерийлер белгілі.[7] Тіпті 3 дәрежелі шыңдары бар ормандардың ойын хроматикалық санын анықтау қиын сияқты, тіпті 3 дәрежесі бар ормандар үшін де.
  • Кактус: .[8]
  • Сыртқы жоспарлар: .[9]
  • Пландық графиктер: .[10]
  • Пландық графиктер берілген белдеу: ,[11] , , .[12]
  • Тороидты торлар: .[13]
  • Ішінара к- ағаштар: .[14]
  • Аралық графиктер: , қайда өлшемі ең үлкен графикке арналған клика.[15]

Декарттық өнімдер.Декарттық өнімнің ойын хроматикалық нөмірі функциясымен шектелмеген және . Атап айтқанда, кез-келген толық екі жақты графиктің ойын хроматикалық саны 3-ке тең, бірақ үшін жоғарғы шекара жоқ ерікті үшін .[16]

  • Бір шеті үшін бізде:[16]

Ашық мәселелер

Бұл сұрақтар осы күнге дейін ашық.

Алиса үшін көбірек түстер [18]
  • Алис графта шыңдарды бояу ойыны үшін жеңіске жететін стратегиясы бар делік G бірге к түстер. Ол үшін бар ма? k + 1 түстер?
    Жауаптар «иә» деп күтуге болады, өйткені түстердің көп болуы Алисаға артықшылық болып көрінеді. Алайда бұл тұжырымның рас екендігіне ешқандай дәлел жоқ.
  • Функция бар ма? f мысалы, егер Алис графикада шыңдарды бояу ойынында жеңетін стратегияға ие болса G бірге к түстер, содан кейін Элис жеңіске жететін стратегияға ие G бірге f (k) ?
    Алдыңғы сұрақтың босаңсыуы.
Басқа түсініктермен қатынастар [18]
  • Графиктердің монотонды класы (мысалы, ішкі графиктермен жабылған графтар класы) шектелген делік ойын хроматикалық нөмірі. Бұл график класы шектелгені рас па? ойынның бояу нөмірі  ?
  • Графиктердің монотонды класы (мысалы, ішкі графиктермен жабылған графтар класы) шектелген делік ойын хроматикалық нөмірі. Бұл график класы шектелгені рас па? ағаш өсіру  ?
  • Шектелген графиктердің монотонды класы деген рас па? ойын хроматикалық нөмірі шектелген ациклді хроматикалық сан  ?
Максималды дәрежені төмендету [7]
  • Болжам: Болып табылады бұл орман, бар осындай және .
  • Келіңіздер кез келген үшін графиктер класы болыңыз , бар осындай және . Графтардың қандай отбасылары бар?  ?
Гиперкубалар[16]
  • Бұл рас па? кез келген гиперкуб үшін  ?
    Ол үшін шындық екені белгілі .[16]

Жиектерді бояу ойыны

The шетін бояу ойыны, Лам, Шиу және Цзу енгізген,[19] шыңдарды бояу ойынына ұқсайды, тек Элис пен Боб дұрыс құрастырмайды жиектерді бояу дұрыс шыңды бояудың орнына. Оның ережелері келесідей:

  1. Алис пен Боб графтың шеттерін бояуда G жиынтығымен к түстер.
  2. Алиса мен Боб кезек-кезек, дұрыс бояу боялмаған жиек (стандартты нұсқада Алиса басталады).
  3. Егер шеті болса e дұрыс бояу мүмкін емес (кез-келген түс үшін, e онымен боялған жиекке іргелес), содан кейін Боб жеңеді.
  4. Егер график толығымен шеткі түсті болса, онда Алиса жеңеді.

Бұл ойынды нақты жағдай ретінде қарастыруға болады шыңдарды бояуға арналған ойын қосулы сызықтық графиктер, бұл негізінен ғылыми әдебиеттерде ерекше ойын ретінде қарастырылады. The ойын хроматикалық индексі график , деп белгіленеді , бұл ойынға жеңіске жету үшін Элиске қажет түстердің минималды саны .

Жалпы жағдай

Әр график үшін G, . Бұл шекараларға жететін графиктер бар, бірақ біз осы шекараға жеткен графиктердің барлығының максималды дәрежесі шамалы.[19] Графиктері бар -ның ерікті үлкен мәндері үшін .[20]

Болжам. Бар кез келген ерікті график үшін , Бізде бар .
Бұл болжам қашан болады шыңдарымен салыстырғанда жеткілікті үлкен .[20]

  • Ағаш өсімдігі. Келіңіздер болуы ағаш өсіру график . Әр график максимуммен дәрежесі бар .[21]

Графикалық сыныптар

Сынып үшін графиктерді біз белгілейміз ең кіші бүтін сан әрбір график туралы бар . Басқа сөздермен айтқанда, - бұл сыныптағы графикалық графикалық ойын индексінің жоғарғы шегі. Бұл мән графиктің бірнеше стандартты кластары үшін белгілі, ал басқалары үшін шектелген:

  • Дөңгелектер: және қашан .[19]
  • Ормандар  : қашан , және .[22]
    Сонымен қатар, егер орманның әр ағашы болса туралы бөлу арқылы алынады шынжыр ағаш немесе 4 дәрежелі екі шектес шыңдардан тұрмайды, содан кейін .[23]

Мәселелерді ашыңыз

Жоғарғы шекара. Тұрақты ма? осындай әр граф үшін ? Егер бұл шын болса, жеткілікті ?[19]

Үлкен минималды градусқа болжам. Бар және бүтін сан кез келген граф бірге қанағаттандырады . [20]

Инцидентті бояу ойыны

The сырқаттанушылықты бояу ойыны - Андрес енгізген графикалық бояу ойыны,[24] және шыңдарды бояуға арналған ойынға ұқсас, Элис пен Бобтан басқасы дұрыс жасалмайды аурудың түсі дұрыс шыңды бояудың орнына. Оның ережелері келесідей:

  1. Алис пен Боб бояуды бояйды оқиғалар график G жиынтығымен к түстер.
  2. Элис пен Боб кезектесіп, түссіз инциденттерді дұрыс бояйды (стандартты нұсқада Алиса басталады).
  3. Егер сырқаттану мен дұрыс бояу мүмкін емес (кез-келген түс үшін, мен онымен боялған оқиғаға іргелес), содан кейін Боб жеңеді.
  4. Егер барлық инциденттер дұрыс боялған болса, онда Алиса жеңеді.

The ойынның хроматикалық саны график , деп белгіленеді , бұл ойынға жеңіске жету үшін Элиске қажет түстердің минималды саны .

Әр график үшін максималды дәрежемен , Бізде бар .[24]

Басқа түсініктермен қатынастар

  • (а, г)-Композиция. Бұл жалпы жағдай үшін біз білетін ең жақсы шекара. Егер графиктің шеттері болса екі жиынтыққа бөлуге болады, олардың бірі графиканы индукциялайды ағаш өсіру , екіншісі максималды дәрежесі бар графикті индукциялайды , содан кейін .[25]
    Сонымен қатар , содан кейін .[25]
  • Азғындау. Егер Бұл к- дегенеративті график максимуммен дәрежесі , содан кейін . Оның үстіне, қашан және қашан .[24]

Графикалық сыныптар

Сынып үшін графиктерді біз белгілейміз ең кіші бүтін сан әрбір график туралы бар .

  • Жолдар : Үшін , .
  • Циклдар : Үшін , .[26]
  • Жұлдыздар : Үшін , .[24]
  • Дөңгелектер : Үшін , . Үшін , .[24]
  • Түсіндірмелері Дөңгелектер : Үшін , егер болып табылады бар подграф ретінде, содан кейін .[27]

Мәселелерді ашыңыз

  • Жоғарғы шекара әрбір мәні үшін қатаң  ?[24]
  • Ойынның хроматикалық саны монотонды параметр ме (яғни график үшін ол соншалықты үлкен емес пе) G кез келген подграфына келетін болсақ G) ?[24]

Ескертулер

  1. ^ Гарднер (1981)
  2. ^ Bodlaender (1991)
  3. ^ Хроматикалық саннан гөрі аз түстер болса, тиісті бояу болмайды G сондықтан Алиса жеңе алмайды. Максималды дәрежеден көп түстермен, шыңды бояуға арналған әрдайым қол жетімді түс бар, сондықтан Элис жоғалтпайды.
  4. ^ Дински және Чжу (1999)
  5. ^ Junosza-Szaniawski & Rożej (2010)
  6. ^ Файгл және басқалар. (1993), және көздейді Junosza-Szaniawski & Rożej (2010)
  7. ^ а б Данн және басқалар. (2014)
  8. ^ Сидорович (2007), және көздейді Junosza-Szaniawski & Rożej (2010)
  9. ^ Гуан және Чжу (1999)
  10. ^ Жоғарғы жағынан байланысты Чжу (2008), алдыңғы шектерін жақсарту 33 дюйм Kierstead & Trotter (1994), 30 білдіреді Дински және Чжу (1999), 19 дюйм Чжу (1999) және 18 дюйм Kierstead (2000). Төменгі шекара мәлімдеді Kierstead & Trotter (1994). Планарлық графиктің ойын хроматикалық санына арналған сауалнаманы қараңыз Бартнички және басқалар. (2007).
  11. ^ Секигуши (2014)
  12. ^ Ол және т.б. (2002)
  13. ^ Raspaud & Wu (2009)
  14. ^ Чжу (2000)
  15. ^ Файгл және басқалар. (1993)
  16. ^ а б c г. Питерин (2007)
  17. ^ а б c Sia (2009)
  18. ^ а б Чжу (1999)
  19. ^ а б c г. Лам, Шиу және Сю (1999)
  20. ^ а б c Беверидж және басқалар. (2008)
  21. ^ Бартнички және Гриччук (2008) нәтижелерін жақсарту к- графиктердің бұзылуы Cai & Zhu (2001)
  22. ^ Bound + 2 жоғарғы шекарасы бойынша Лам, Шиу және Сю (1999), содан кейін Δ + 1 арқылы шектеледі Ердос және басқалар. (2004) cases = 3 және Δ≥6 жағдайлары үшін, және Андрес (2006) case = 5 жағдай үшін.
  23. ^ Δ = 4 болатын ормандардың шарттары Чан & Нонг (2014)
  24. ^ а б c г. e f ж Андрес (2009a), сондай-ақ тұрақсыздықты қараңыз Андрес (2009b)
  25. ^ а б Шарпентье және Сопена (2014), нәтижелерін кеңейту Шарпентье және Сопена (2013).
  26. ^ Ким (2011), үшін ұқсас нәтижені жақсарту k ≥ 7 жылы Андрес (2009a) (сонымен қатар тұрақсыздықты қараңыз Андрес (2009b) )
  27. ^ Ким (2011)

Әдебиеттер тізімі (хронологиялық тәртіп)