Радуга бояуы - Rainbow coloring

А-ның радуга түсі доңғалақ графигі, үш түсті. Көршілес емес екі төбені кемпірқосақ жолымен тікелей орталық шың арқылы (төменгі сол жақта) немесе қайталанатын жиек түсін болдырмау үшін бір үшбұрышты айналып өту арқылы қосуға болады (төменгі оң жақ).

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

Анықтамалар мен шектер

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

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

Төмендегі экстремалды жағдайлар:[1]

  • егер және егер болса Бұл толық граф.
  • егер және егер болса Бұл ағаш.

Жоғарыда көрсетілгендей, шыңдар саны бойынша жоғарғы шекара жалпы алғанда ең жақсы болып табылады. Шын мәнінде, пайдаланып кемпірқосақ бояу түстерді ағаштың шеттерін бояу арқылы жасауға болады нақты түстерде. Қалған боялмаған шеттер ерікті түрде боялған, жаңа түстер енгізілмеген. Қашан 2-байланысты, бізде бар .[2] Сонымен қатар, бұл, мысалы, қатты куә. тақ циклдар.

Дәл кемпірқосақ немесе күшті радуга байланыс нөмірлері

Кейбір құрылымдалған графикалық сыныптар үшін кемпірқосақ немесе күшті радуга байланыс нөмірі анықталды:

  • , әрбір бүтін сан үшін , қайда болып табылады цикл графигі.[1]
  • , әрбір бүтін сан үшін , және , үшін , қайда болып табылады доңғалақ графигі.[1]

Күрделілік

Шешім мәселесі берілген график үшін болып табылады NP аяқталды.[3] Себебі егер және егер болса ,[1] егер болса, соны шешеді берілген график үшін NP-аяқталған .

Нұсқалар және жалпылау

Шартран, Окамото және Чжан[4] кемпірқосақтың байланыс нөмірін төмендегідей жалпылаған. Келіңіздер тапсырыс бойынша жиек түсті нейтривиальды байланысты график болу . Ағаш Бұл кемпірқосақ ағашы егер екі шеті болмаса бірдей түс беріледі. Келіңіздер -мен бекітілген бүтін сан болу керек . Беттің түсі а деп аталады - ми садақтарын бояу егер әр жиынтық үшін болса туралы шыңдары , ішінде радуга ағашы бар шыңдары бар . The - ми садақының индексі туралы а-ға қажет түстердің минималды саны - ми садақтарын бояу . A - ми садақтарын бояу түстер а деп аталады минимум - ми садақтарын бояу. Осылайша - кемпірқосақтың байланыс нөмірі .

Радуга байланысы сонымен қатар шыңдардағы түрлі-түсті графикаларда зерттелген. Бұл тұжырымдаманы Кривелевич пен Юстер енгізген.[5]Мұнда радуга шыңы-байланыс нөмірі график , деп белгіленеді , бұл бояу үшін қажет түстердің минималды саны әрбір төбенің жұбы үшін оларды біріктіретін жол бар, олардың ішкі шыңдарына ерекше түстер тағайындалады.

Сондай-ақ қараңыз

Ескертулер

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

  • Чартран, Гари; Джонс, Гарри Л .; МакКион, Кэтлин А .; Чжан, Пинг (2008), «Радугадағы байланыс», Mathematica Bohemica, 133 (1).
  • Чартран, Гари; Окамото, Футаба; Чжан, Пинг (2010), «Радуга ағаштары графикада және жалпыланған байланыста», Желілер, 55 (4), дои:10.1002 / net.20339.
  • Чакраборти, Сурав; Фишер, Эльдар; Мацлия, Ари; Юстер, Рафаэль (2011), «Радугаға қосылудың қаттылығы және алгоритмдері», Комбинаторлық оңтайландыру журналы, 21 (3): 330–347, arXiv:0809.2493, дои:10.1007 / s10878-009-9250-9.
  • Кривелевич, Майкл; Юстер, Рафаэль (2010), «Графиктің кемпірқосақтың қосылуы (ең көп дегенде) оның минималды дәрежесіне сәйкес келеді», Графикалық теория журналы, 63 (3): 185–191, дои:10.1002 / jgt.20418.
  • Ли, Сюэлян; Ши, Йонгтанг; Sun, Yuefang (2013), «Радуга графикасының байланыстары: сауалнама», Графиктер және комбинаторика, 29 (1): 1–38, arXiv:1101.5747, дои:10.1007 / s00373-012-1243-2.
  • Ли, Сюэлян; Sun, Yuefang (2012), Графиктердің радуга байланыстары, Springer, б. 103, ISBN  978-1-4614-3119-0.
  • Экштейн, Ян; Холуб, Пемисл; Кайзер, Томаш; Кох, Мария; Камачо, Стефан Матос; Рыячек, Зденек; Schiermeyer, Ingo (2013), «2 байланысқан графиктің кемпірқосақтың байланыс нөмірі», Дискретті математика, 313 (19): 1884–1892, arXiv:1110.5736, дои:10.1016 / j.disc.2012.04.022.