Бояуды ерекшелеу - Distinguishing coloring

4- бояғышты ерекшелеугиперкубтық график

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

Бояғыштарды ажырату және сандарды ажырату арқылы енгізілді Альбертсон және Коллинз (1996), бұған дейін Фрэнк Рубин тұжырымдаған басқатырғышқа негізделген келесі уәжді мысалды келтірді: «Сізде әртүрлі есіктердің кілттері сақинасы бар делік; әр кілт тек бір есікті ашады, бірақ олардың бәрі сіз үшін ажыратылмайтын болып көрінеді. Сіз қанша түсті пернелердің тұтқаларын әр пернені ерекше анықтай алатындай етіп бояу керек пе? «[1] Бұл мысал а-ға арналған бояғышты қолдану арқылы шешіледі цикл графигі. Осындай бояумен әр перне өзінің түсімен және оны қоршаған түстердің реттілігімен ерекше түрде анықталады.[2]

Мысалдар

Сегіз асимметриялық графика, әрқайсысында бір ғана түспен (қызыл) ерекшеленетін бояу берілген

Графикте егер ол бар болса, оны ажырататын бірінші нөмір болады асимметриялық.[3] Мысалы, Фрух графигі тек бір түспен ерекшеленетін бояғышқа ие.

Ішінде толық граф, тек әр түрлі бояғыштар әр шыңға әр түрлі түсті береді. Егер екі төбеге бірдей түс берілсе, онда сол екі төбені ауыстырып, қалғандарын орнында қалдыратын симметрия болады. Демек, толық графиканың айырым нөмірі Қn болып табылады n. Алайда алынған график Қn әр шыңына градус-бір шыңды бекіту арқылы Қn бірдей симметрия тобына ие болғанымен, едәуір кіші айырым нөмірі бар: оның бар ерекше бояуы бар түстер, әр шыңның әр жұбы үшін әртүрлі реттелген түстер жұбын қолдану арқылы алынған Қn және оның көршісі.[2]

Екі түстің (қызыл және боялмаған) көмегімен алты пернеден тұратын сақинаның айрықша бояуы

Үшін цикл графигі үш, төрт немесе бес шыңдардан, үш түрлі түсті бояу салу үшін қажет. Мысалы, бес циклдің әрбір екі бояуы шағылысу симметриясына ие. Осы циклдердің әрқайсысында көршілес екі төбенің әрқайсысына ерекше түсті тағайындау және қалған барлық шыңдар үшін үшінші түсті қолдану үш түсті ерекшеленетін бояуға әкеледі. Алайда, алты немесе одан да көп шыңдар циклдарында тек екі түспен ерекшеленетін бояғыштар бар. Яғни, Фрэнк Рубиннің кілттер сөзжұмбағында үш, төрт немесе бес кілттердің сақиналары үшін үш түсті қажет, бірақ алты немесе одан да көп кілттерге немесе екі кілтке екі түсті қажет.[2] Мысалы, көрсетілген алты перненің сақинасында әр пернені өзінің түсімен және қарама-қарсы түсті пернелердің іргелес блоктарының ұзындығымен немесе ұзындықтарымен ажыратуға болады: әр түсті және көршілес блок ұзындықтарының әр тіркесімі үшін бір ғана перне бар .

Гиперкуб графиктері циклдік графиктерге ұқсас құбылысты көрсетіңіз. Екі және үш өлшемді гиперкубалық графиктерде (сәйкесінше, 4 цикл және кубтың графигі) ажыратылатын үш саны бар. Алайда, жоғары өлшемді әрбір гиперкубтық графикада айрықша сан тек екіге ие.[4]

The Питерсен графигі 3-тен ерекшеленетін нөмірі бар. Алайда бұл графиктен және толық графиктерден басқа, барлығы Kneser графиктері айырым нөмірі 2 бар.[5] Сол сияқты, арасында жалпыланған Петерсен графиктері, тек Петерсен графигінің өзі және текше графигінің айырымдық саны 3 болады; қалғандарының айырым нөмірі 2 бар.[6]

Есептеудің күрделілігі

-Ның айырым сандары ағаштар, жазықтық графиктер, және аралық графиктер есептелуі мүмкін көпмүшелік уақыт.[7][8][9]

Айырмашылық сандарды есептеудің нақты күрделілігі түсініксіз, өйткені ол әлі белгісіз күрделілікпен тығыз байланысты графикалық изоморфизм. Алайда оның күрделілік класына жататындығы дәлелденді AM.[10] Сонымен қатар, айырмашылық санының ең көп дегенде үш екенін тексеру NP-hard,[9] және оның максимум екі болатындығын тексеру «кем дегенде графоморфизм сияқты қиын, бірақ граф изоморфизмінен қиын емес».[11]

Қосымша қасиеттер

Берілген графиктің бояуы, егер ол үшін ерекшеленетін болса ғана, сол график үшін ерекшеленеді толықтыру сызбасы. Сондықтан әр графта оның толықтырғышымен бірдей айырым саны болады.[2]

Әр график үшін G, -ның айырым саны G көбіне пропорционалды логарифм санының автоморфизмдер туралы G. Егер автоморфизмдер нотивиальды түзсе абель тобы, айырым саны екіге тең, ал егер ол а құрайды екіжақты топ онда айырым саны ең көп дегенде үш болады.[2]

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

Вариациялар

A дұрыс ажыратылатын бояу бұл әр түрлі бояғыш, ол сонымен қатар тиісті бояғыш болып табылады: әр екі іргелес шыңдардың түстері әртүрлі. Графиктің дұрыс ажыратылған бояуларындағы минималды түстер саны деп аталады хроматикалық санды ажырату график.[12]

Әдебиеттер тізімі

  1. ^ Рубин, Фрэнк (1979), «729-мәселе: соқырдың кілттері», Рекреациялық математика журналы, 11: 128. Шешім том. 12, 1980. келтірген Альбертсон және Коллинз (1996). Түстерді пайдаланудың орнына, Рубин бұл мәселені бір-бірінен жанасу арқылы ажыратуға болатын түйінді тұтқалар тұрғысынан тұжырымдады. Дәлірек айтсақ, бұл мәселе әр перне симметриялы болады, сондықтан пернелерді кілттер бойынша бағдарлары бойынша бір-бірінен ажыратуға болмайды.
  2. ^ а б c г. e f Альбертсон, Майкл О .; Коллинз, Карен Л. (1996), «Графиктердегі симметрияның бұзылуы», Комбинаториканың электронды журналы, 3 (1): R18, МЫРЗА  1394549.
  3. ^ Қараңыз, мысалы, Имрих, Уилфрид; Клавжар, Санди (2006), «Графиктердің декарттық күштерін ажырату», Графикалық теория журналы, 53 (3): 250–260, CiteSeerX  10.1.1.59.9242, дои:10.1002 / jgt.20190 ж, МЫРЗА  2262268, Егер графиктің нейтривиалды автоморфизмі болмаса, оның айырым саны 1 болады. Басқаша айтқанда, Д.(G) = 1 асимметриялық графиктер үшін.
  4. ^ Богстад, Билл; Коуэн, Ленор Дж. (2004), «Гиперкубтың айырықша саны», Дискретті математика, 283 (1–3): 29–35, дои:10.1016 / j.disc.2003.11.018, МЫРЗА  2061481.
  5. ^ Альбертсон, Майкл О .; Ботин, Дебра Л. (2007), «Kneser графиктерін ажырату үшін анықтайтын жиынтықтарды қолдану», Комбинаториканың электронды журналы, 14 (1): R20, МЫРЗА  2285824.
  6. ^ Лал, А.К .; Bhattacharjya, B. (2009), «Кітап графигі мен жалпыланған Питерсен графигінің симметрияларын бұзу», Дискретті математика бойынша SIAM журналы, 23 (3): 1200–1216, дои:10.1137/080728640, МЫРЗА  2538646. Лал мен Бхаттачарджя (Теорема 4.3) бұл нәтижені К.С.Потанканың жарияланбаған магистрлік диссертациясы деп санайды (Вирджиния политехникалық университеті, 1998).
  7. ^ Ченг, Кристин Т. (2006), «Ағаштар мен ормандардың айырым сандарын есептеу туралы», Комбинаториканың электронды журналы, 13 (1): R11, МЫРЗА  2200539.
  8. ^ Арвинд, V .; Ченг, Кристин Т .; Деванур, Никхил Р. (2008), «Пландық графиктің және одан тыс графиканың айырым сандарын есептеу туралы: санау тәсілі», Дискретті математика бойынша SIAM журналы, 22 (4): 1297–1324, arXiv:математика / 0703927, дои:10.1137 / 07068686X, МЫРЗА  2443115.
  9. ^ а б Ченг, Кристин Т. (2009), «Хроматикалық сандарды ажырату және ажырату графиктерін және басқа нәтижелерді есептеу туралы», Дискретті математика, 309 (16): 5169–5182, дои:10.1016 / j.disc.2009.04.004, МЫРЗА  2548918.
  10. ^ Рассел, Александр; Сундарам, Рави (1998), «Асимптотика және графиктің ажыратымдылығының есептеу күрделілігі туралы жазба», Комбинаториканың электронды журналы, 5: R23, МЫРЗА  1617449.
  11. ^ Эшен, Элейн М .; Хоан, Чин Т .; Сритаран, Р .; Стюарт, Лорна (2011 ж.), «Графиктің ажырайтын хроматикалық саны ең көп дегенде екі болатындығын шешудің күрделілігі туралы», Дискретті математика, 311 (6): 431–434, arXiv:0907.0691, дои:10.1016 / j.disc.2010.12.013, МЫРЗА  2799894.
  12. ^ Коллинз, Карен Л.; Тренк, Анн Н. (2006), «Айырмашылығы бар хроматикалық сан», Комбинаториканың электронды журналы, 13 (1): R16, МЫРЗА  2200544.