Галлай – Хассе – Рой – Витавер теоремасы - Gallai–Hasse–Roy–Vitaver theorem

Төрт түрлі бағдарлар әр бағыттың максималды ациклді субографиясын (қатты шеттері) және шыңдарды осы субграфтағы ең ұзақ кіретін жолдың ұзындығын көрсететін 5 циклды. Сол жақта ең қысқа жолдармен бағыт графиканың оңтайлы боялуын қамтамасыз етеді.

Жылы графтар теориясы, Галлай – Хассе – Рой – Витавер теоремасы формасы болып табылады екі жақтылық арасында бояғыштар берілген бағытталмаған графтың төбелерінің және бағдарлар оның шеттерінен. Онда кез-келген графиканы дұрыс бояу үшін қажетті минималды түстер саны көрсетілген G а-ның ұзындығына тең ең ұзақ жол ан бағдар туралы G осы жолдың ұзындығын азайту үшін таңдалған.[1] Ең ұзақ жол ең аз ұзындыққа жететін бағыттар әрқашан кем дегенде біреуін қамтиды ациклдік бағыт.[2]

Теореманың қорытындысы мынада: графиканың әрбір бағыты хроматикалық сан к құрамында қарапайым бағытталған жол бар к төбелер;[3] бұл жолды бағытталған графтың барлық басқа шыңдарына жете алатын кез-келген шыңнан бастауға шектеу қоюға болады.[4][5]

Мысалдар

A екі жақты граф екі бөлімнің бір жағынан екінші жағына бағытталуы мүмкін; осы бағыттағы ең ұзын жолдың тек екі шыңы болады. Керісінше, егер график үш шыңды жолдарсыз бағдарланған болса, онда әрбір шың не дереккөз (кіріс шеттері жоқ), не раковина (шығатын шеттері жоқ) болуы керек, ал шыңдарды көздер мен раковиналарға бөлу оны көрсетеді екі жақты.

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

Дәлел

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

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

Осы теореманың дәлелі формальдау үшін сынақ ретінде қолданылды математикалық индукция арқылы Юрий Матияевич.[6]

Санат-теориялық интерпретация

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

Гомоморфизмдерді басқа бағытта қарастыру G орнына G, бағытталған график G ациклді және ең көп дегенде к егер оның гомоморфизмі болмаса, ең ұзақ жолдағы шыңдар жол сызбасы Pк + 1 дейін G.

Сонымен, Галлай-Хассе-Рой-Витавер теоремасын баламалы түрде келесі түрде айтуға болады:[2]

Әр бағытталған граф үшін G, бастап гомоморфизм бар G дейін к-vertex транзитивті турнир, егер тек гомоморфизм болмаса (к + 1) -ке -текс нүктесі G.

Бұл жағдайда G ациклді болып табылады, оны формасы ретінде де қарастыруға болады Мирский теоремасы а-дағы ең ұзын тізбек жартылай тапсырыс берілген жиынтық жиынтықты бөлуге болатын античайндардың ең аз санына тең.[7] Бұл мәлімдемені жолдардан басқа бағытталған графиктерге жалпылауға болады: әрқайсысы үшін полиэтр P екі бағытты график бар Д. әрбір бағытталған граф үшін G, бастап гомоморфизм бар G дейін Д. егер және егер гомоморфизм болмаса ғана P дейін G.[8]

Тарих

Галлай-Хассе-Рой-Витавер теоремасы бірнеше рет қайта ашылды.[2] Ол жекелеген басылымдардың атымен аталған Тибор Галлай,[9] Мария Хассе,[10] Б.Рой,[11] және Витавер Л.М.[12] Рой теореманың тұжырымдамасын 1958 жылғы график теориясының оқулығындағы болжамға негіздейді Клод Берге.[11]

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

  1. ^ а б Хсу, Лих-Хсинг; Лин, Ченг-Куан (2009), «Теорема 8.5», Графикалық теория және өзара байланыс желілері, Бока Ратон, Флорида: CRC Press, 129–130 бет, ISBN  978-1-4200-4481-2, МЫРЗА  2454502.
  2. ^ а б c Нешетиль, Ярослав; Оссона де Мендес, Патрис (2012), «Теорема 3.13», Сараңдық: Графиктер, құрылымдар және алгоритмдер, Алгоритмдер және комбинаторика, 28, Гайдельберг: Шпрингер, б. 42, дои:10.1007/978-3-642-27875-4, ISBN  978-3-642-27874-7, МЫРЗА  2920058.
  3. ^ Чартран, Гари; Чжан, Пинг (2009), «Теорема 7.17 (Галлай-Рой-Витавер теоремасы)», Хроматикалық графика теориясы, Дискретті математика және оның қосымшалары, Бока Ратон, Флорида: CRC Press, ISBN  978-1-58488-800-0, МЫРЗА  2450569.
  4. ^ Ли, Хао (2001), «Галлай-Рой теоремасын қорыту», Графиктер және комбинаторика, 17 (4): 681–685, дои:10.1007 / PL00007256, МЫРЗА  1876576.
  5. ^ Чанг, Джерард Дж .; Тонг, Ли-Да; Ян, Цзин-Хо; Ие, Хонг-Гва (2002), «Галлай-Рой-Витавер теоремасы туралы ескерту», Дискретті математика, 256 (1–2): 441–444, дои:10.1016 / S0012-365X (02) 00386-2, МЫРЗА  1927565.
  6. ^ Матиясевич, Ю. В. (1974), «Доказательств в дискретной математике схемасы» [Дискретті математикада дәлелдеудің белгілі бір схемасы], Математикалық және математикалық логике бойынша конструктивтік математика [Конструктивті математика және математикалық логика бойынша зерттеулер. VI бөлім. Марковтың 70 жасқа толуына байланысты], Zapiski Naučnyh Seminarov Leningradskogo Otdelenija Matematičeskogo Instituta im. V. A. Steklova Akademii Nauk SSSR (LOMI) (орыс тілінде), 40, 94-100 бет, МЫРЗА  0363823.
  7. ^ Мирский, Леон (1971), «Дилворттың ыдырау теоремасының дуалы», Американдық математикалық айлық, 78 (8): 876–877, дои:10.2307/2316481, JSTOR  2316481.
  8. ^ Нешетиль, Ярослав; Тардиф, Клод (2008), «Графиктің хроматикалық санын шектеуге дуалистік көзқарас», Еуропалық Комбинаторика журналы, 29 (1): 254–260, дои:10.1016 / j.ejc.2003.09.024, МЫРЗА  2368632.
  9. ^ Галлай, Тибор (1968), «Бағытталған графиктер мен схемалар туралы», Графика теориясы (Тихани 1966 ж. Коллоквиум жинағы), Будапешт: Akadémiai Kiadó, 115–118 бб.
  10. ^ Хассе, Мария (1965), «Zur algebraischen Begründung der Graphentheorie. I», Mathematische Nachrichten (неміс тілінде), 28 (5–6): 275–290, дои:10.1002 / mana.19650280503, МЫРЗА  0179105.
  11. ^ а б Рой, Б. (1967), «Nombre chromatique et plus longs chemins d'un graphe» (PDF), Аян Француз ақпараты. Recherche Opérationnelle (француз тілінде), 1 (5): 129–132, дои:10.1051 / m2an / 1967010501291, МЫРЗА  0225683.
  12. ^ Витавер, Л. М. (1962), «Нахождение минимальных раскрасок вершин графа с помощью булевых степеней матрицы смежностей [Түсу матрицасының бульдік қуаттары арқылы графиктің төбелерінің минималды боялуын анықтау]», Doklady Akademii Nauk SSSR (орыс тілінде), 147: 758–759, МЫРЗА  0145509.