Күшті график теоремасы - Strong perfect graph theorem

Жылы графтар теориясы, күшті графикалық теорема Бұл тыйым салынған графикалық сипаттама туралы тамаша графиктер тақ сызықтары жоқ тақ сызықтар (тақ ұзындық) индукцияланған циклдар ) тақ саңылаулар (тақ саңылаулардың толықтырушылары). Ол болжам жасады Клод Берге 1961 ж Мария Чудновский, Нил Робертсон, Пол Сеймур, және Робин Томас 2002 жылы жарияланды^[1] және олар 2006 жылы жариялады.

Керемет график теоремасының дәлелі оның авторлары үшін Карнеги Меллон университетінің қызметкері Жерар Корнуэжолс ұсынған 10000 АҚШ долларын алды.^[2] және 2009 ж Фулкерсон сыйлығы.^[3]

Мәлімдеме

A тамаша график - бұл әрқайсысына арналған график индукцияланған субография, өлшемі максималды клик а-дағы минималды түстер санына тең бояу графиктің; тамаша графиктерге көптеген белгілі графикалық сыныптар, соның ішінде екі жақты графиктер, аккордтық графиктер, және салыстырмалы графиктер. Оның 1961 және 1963 жылдардағы жұмыстарында графиктердің осы класын алғаш рет анықтаған, Клод Берге тамаша сызбада тақ саңылау болуы мүмкін емес екенін байқады индукцияланған субография тақ ұзындық түрінде цикл графигі ұзындығы бес немесе одан да көп, өйткені тақ саңылауларда кликалық нөмір екінші және хроматикалық нөмір үш болады. Сол сияқты, ол керемет графикада тақ саңылаулар, индукцияланған субграфтар болмайтынын байқады толықтырушы тақ саңылауларға: 2-ге тең тақтай тесікк + 1 шыңдарда клик нөмірі бар к және хроматикалық сан к + 1, бұл қайтадан мінсіз графиктер үшін мүмкін емес. Тақ саңылаулары да, тақ саңылаулары да жоқ графиктер Берг графиктері деп аталды.

Берге әр Берге графигі кемелді деп санайды, немесе эквивалент бойынша, керемет графиктер мен Берге графиктері графтардың бірдей класын анықтайды. Бұл мықты кемелді графикалық гипотеза ретінде белгілі болды, ол 2002 жылы дәлелденгенге дейін, ол күшті графикалық теорема деп аталды.

Әлсіз кемелді график теоремасымен байланыс

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

Дәлелді идеялар

Чудновский және басқалардың мықты кемелді график теоремасының дәлелі. 2001 жылы Конфорти, Корнуеджолс, Робертсон, Сеймур және Томас болжаған контурды ұстанады, оған сәйкес әр Берге графигі негізгі құрылыс блоктарының бес түрінің бірін құрайды (арнайы графиктердің арнайы сыныптары) немесе оның төрт түрлі типінің бірі бар қарапайым графиктерге құрылымдық ыдырау. Минималды жетілмеген Берге графикасында бұл ыдыраудың ешқайсысы болуы мүмкін емес, одан теоремаға қарсы мысал бола алмайды.^[4] Бұл идея графиканың күшті гипотезасын болжайтын, бірақ жалған болып шыққан ұқсас типтегі бұрынғы құрылымдық декомпозицияларға негізделген.^[5]

Бұл құрылымдық ыдыраудың негізгі жағдайын құрайтын мінсіз графиктердің бес негізгі кластары болып табылады екі жақты графиктер, сызықтық графиктер екі жақты графиктердің, бір-бірін толықтыратын графиктер екі жақты графиктердің, екі жақты графиктердің сызықтық графиктерінің толықтыру және екіге бөлінген графиктер. Екі жақты графиктердің мінсіз екенін байқау қиын емес: кез-келген жеке емес индукцияланған субографияда клик саны мен хроматикалық сан екеуі де, сондықтан екеуі де тең. Екі жақты графиктердің комплектілерінің және екі жақты графиктердің сызықтық графикалық комплементтердің жетілдірілуі екеуіне де тең келеді Кёниг теоремасы өлшемдеріне қатысты максималды сәйкестіктер, максималды тәуелсіз жиындар, және минималды шыңдардың қақпақтары екі жақты графиктерде. Екі жақты графиктердің сызықтық графиктерінің жетілуін екі жақты графтардың бар екендігіне баламалы түрде айтуға болады. хроматикалық индекс олардың максимумына тең дәрежесі, арқылы дәлелденген Кёниг (1916). Осылайша, осы төрт негізгі сыныптың барлығы да мінсіз. Екіге бөлінген графиктер - туысы бөлінген графиктер бұл сондай-ақ мінсіз ретінде көрсетілуі мүмкін.^[6]

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

2-қосылыс дегеніміз - бұл графиктің шыңдарының екі ішкі жиынға бөлінуі, бұл екі ішкі жиынның арасындағы кесіндіге созылатын шеттері екі шыңнан бөлінетін қасиетке ие. толық екі жақты графиктер. Графиктің 2-қосылысы болған кезде, оны екі блоктық шыңның бірін екі толық екі графиттің біреуін екіншісіне қосатын сол ішкі жиектегі ең қысқа жолмен ауыстыру арқылы «блоктар» деп аталатын субграфтарға бөлуге болады; мұндай жол болмаған кезде, оның орнына шыңдар екі жиынтықтың бірін екі толық төбеге ауыстыру арқылы пайда болады, әр толық екі жақты субография үшін біреуі. 2-қосылыс өте жақсы, егер оның екі блогы да мінсіз болса ғана. Сондықтан, егер минималды жетілмеген графта 2-қосылғыш болса, онда ол оның блоктарының біріне тең болуы керек, одан Берге емес, тақ цикл болуы керек. Сол себепті комплементі 2 қосылғышқа ие минималды жетілмеген графика Берге бола алмайды.^[7]

A қисаю бөлімі біреуі ажыратылған субографияны, ал екіншісінде ажыратылған толықтауыш болатын индикаторларды екі ішкі жиынға бөлу; Чваталь (1985) күшті графикалық болжамға ешқандай минималды қарсы мысал қисық бөлімді бола алмайды деп ойлады. Чудновский және басқалар. қисық бөлімдерге кейбір техникалық шектеулер енгізді және Чваталдың болжамының нәтижесінде пайда болған «теңдестірілген қисаю бөлімдеріне» сәйкес келетіндігін көрсете алды. Толық болжам - бұл керемет график теоремасының қорытындысы.^[8]

Біртекті жұп а модульдік ыдырау график. Бұл графиктің үш ішкі жиынға бөлінуі V₁, V₂, және V₃ осындай V₁ және V₂ бірге кем дегенде үш шың бар, V₃ кем дегенде екі шыңнан тұрады және әр шың үшін v жылы V₃ және әрқайсысы мен {1,2} -де де v барлық шыңдарға іргелес V_мен немесе олардың ешқайсысына. Минималды жетілмеген графикада біртекті жұп болуы мүмкін емес.^[9] Кейінгі керемет графикалық болжамның дәлелденуінен кейін, Чудновский (2006) дәлелдеу кезінде қолданылатын ыдырау жиынтығынан біртекті жұптарды жоюға болатындығын көрсетіп, оны оңайлатты.

Әрбір Berge графигінің негізгі бес кластың біріне жататындығының немесе ыдыраудың төрт түрінің біреуінің бар екендігінің дәлелі графиктің ішіндегі белгілі бір конфигурациялардың бар-жоғына сәйкес жағдайды талдаудан кейін жүреді: «зембіл», ішіне ыдырауға болатын подограф. белгілі бір қосымша шектеулерге ұшыраған үш индукцияланған жол, зембілдің комплементі және «тиісті дөңгелек», байланысты конфигурация доңғалақ графигі, индукцияланған циклдан және циклдің кем дегенде үш төбесіне жақын орналасқан хаб төбесінен тұрады және бірнеше қосымша шектеулерге бағынады. Берге графикасында зембіл немесе оның комплементі немесе тиісті дөңгелегі бар-жоқтығын таңдау үшін график негізгі кластардың бірінде немесе ыдырайтын болып көрсетілуі мүмкін.^[10] Бұл жағдайды талдау дәлелдеуді аяқтайды.

Ескертулер

^ Маккензи (2002); Cornuéjols (2002).
^ Маккензи (2002).
^ «2009 жылғы Фулкерсон сыйлығы» (PDF), Американдық математикалық қоғамның хабарламалары: 1475–1476, желтоқсан 2011.
^ Cornuéjols (2002), Болжам 5.1.
^ Рид (1986); Хугардия (1991); Русу (1997); Руссель, Русу және Туллер (2009), 4.6 бөлім «Алғашқы болжамдар».
^ Руссель, Русу және Туллер (2009), Анықтама 4.39.
^ Cornuéjols & Cunningham (1985); Cornuéjols (2002), 3.2 теоремасы және 3.3 қорытынды.
^ Сеймур (2006); Руссель, Русу және Туллер (2009), 4.7 бөлім «Қиғаш бөлім»; Cornuéjols (2002), 4.1 және 4.2 теоремалары.
^ Чваталь және Сбихи (1987); Cornuéjols (2002), Теорема 4.10.
^ Cornuéjols (2002), 5.4, 5.5 және 5.6 теоремалары; Руссель, Русу және Туллер (2009), Теорема 4.42.

Пайдаланылған әдебиеттер

Берг, Клод (1961), «Färbung von Graphen, deren sämtliche bzw. deren ungerade Kreise starr sind», Уис. Мартин-Лютер-Унив. Галле-Виттенберг математикасы. Рейх, 10: 114.
Берг, Клод (1963), «Керемет графиктер», Графика теориясы бойынша алты мақала, Калькутта: Үндістан статистикалық институты, 1–21 бб.
Чудновский, Мария (2006), «Берге триграфтары», Графикалық теория журналы, 53 (1): 1–55, дои:10.1002 / jgt.20165, МЫРЗА 2245543.
Чудновский, Мария; Робертсон, Нил; Сеймур, Пол; Томас, Робин (2006), «Мықты график теоремасы», Математика жылнамалары, 164 (1): 51–229, arXiv:математика / 0212070, дои:10.4007 / жылнамалар.2006.164.51, МЫРЗА 2233847.
Чудновский, Мария; Робертсон, Нил; Сеймур, Пол; Томас, Робин (2003), «Мінсіз графиктер бойынша прогресс», Математикалық бағдарламалау, B. сериясы, 97 (1–2): 405–422, CiteSeerX 10.1.1.137.3013, дои:10.1007 / s10107-003-0449-8, МЫРЗА 2004404.
Чваталь, Вацлав (1985), «Жұлдыздар мен керемет графиктер», Комбинаторлық теория журналы, B сериясы, 39 (3): 189–199, дои:10.1016/0095-8956(85)90049-8, МЫРЗА 0815391.
Чваталь, Вацлав; Сбихи, Наджиба (1987), «Бергесіз графика өте жақсы», Графиктер және комбинаторика, 3 (2): 127–139, дои:10.1007 / BF01788536, МЫРЗА 0932129.
Корнуэхолс, Жерар (2002), «Күшті тамаша графикалық болжам», Халықаралық математиктер конгресінің материалдары, т. III (Пекин, 2002) (PDF), Пекин: Жоғары ред. Баспасөз, 547–559 б., МЫРЗА 1957560.
Корнуэжолс, Г.; Каннингэм, У.Х. (1985), «Мінсіз графиктерге арналған композициялар», Дискретті математика, 55 (3): 245–254, дои:10.1016 / S0012-365X (85) 80001-7, МЫРЗА 0802663.
Хугарди, С. (1991), Керемет графиктерге қатысты үш болжамға қарсы мысалдар, Техникалық есеп RR870-M, Гренобль, Франция: Laboratoire Artemis-IMAG, Университет Джозеф Фурье. Келтірілгендей Руссель, Русу және Туллер (2009).
Кёниг, Денес (1916), «Gráfok és alkalmazásuk a determinánsok és a halmazok elméletére», Matematikai és Természettudományi Értesítő, 34: 104–119.
Ловас, Ласло (1972a), «Қалыпты гиперграфиялар және керемет графикалық болжам», Дискретті математика, 2 (3): 253–267, дои:10.1016 / 0012-365X (72) 90006-4.
Ловас, Ласло (1972б), «Мінсіз графиктердің сипаттамасы», Комбинаторлық теория журналы, B сериясы, 13 (2): 95–98, дои:10.1016/0095-8956(72)90045-7.
Маккензи, Дана (2002 ж. 5 шілде), «Математика: Графикалық теория кемелдік тамырларын ашады», Ғылым, 297 (5578): 38, дои:10.1126 / ғылым.297.5578.38, PMID 12098683.
Рид, Б.А. (1986), Жартылай күшті график теоремасы, Ph.D. диссертация, Монреаль, Квебек, Канада: МакГилл университетінің Информатика кафедрасы. Келтірілгендей Руссель, Русу және Туллер (2009).
Руссель, Ф .; Русу, мен .; Туллиер, Х. (2009), «Күшті керемет графикалық болжам: 40 жылдық талпыныс және оның шешімі», Дискретті математика, 309 (20): 6092–6113, дои:10.1016 / j.disc.2009.05.024, МЫРЗА 2552645.
Rusu, Irena (1997), «Қарама-қарсы мысалдар құру», Дискретті математика, 171 (1–3): 213–227, дои:10.1016 / S0012-365X (96) 00081-7, МЫРЗА 1454452.
Сеймур, Пол (2006), «Мықты графикалық болжамның дәлелі қалай табылды» (PDF), Gazette des Mathématiciens (109): 69–83, МЫРЗА 2245898.

Сыртқы сілтемелер

[1] Маккензи (2002); Cornuéjols (2002).

[2] Маккензи (2002).

[3] «2009 жылғы Фулкерсон сыйлығы» (PDF), Американдық математикалық қоғамның хабарламалары: 1475–1476, желтоқсан 2011.

[4] Cornuéjols (2002), Болжам 5.1.

[5] Рид (1986); Хугардия (1991); Русу (1997); Руссель, Русу және Туллер (2009), 4.6 бөлім «Алғашқы болжамдар».

[6] Руссель, Русу және Туллер (2009), Анықтама 4.39.

[7] Cornuéjols & Cunningham (1985); Cornuéjols (2002), 3.2 теоремасы және 3.3 қорытынды.

[8] Сеймур (2006); Руссель, Русу және Туллер (2009), 4.7 бөлім «Қиғаш бөлім»; Cornuéjols (2002), 4.1 және 4.2 теоремалары.

[9] Чваталь және Сбихи (1987); Cornuéjols (2002), Теорема 4.10.

[10] Cornuéjols (2002), 5.4, 5.5 және 5.6 теоремалары; Руссель, Русу және Туллер (2009), Теорема 4.42.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]