Жалпы графиктар: Тақ циклдар мен антициклдарсыз графиктер

Кіріспе

Кемел графтарда тақ тесіктер де, тақ антитесіктер де жоқ. Графтар теориясындағы мықты кемел граф теоремасы – кемел графтардың нақты сипаттамасы, олар тақ тесіктер (кемінде 5 ұзындығы бар индукцияланған циклдар) немесе тақ антитесіктер (тақ тесіктердің толықтырулары) жоқ графтар болып табылады. Бұл гипотезаны Клод Берж 1961 жылы қойған. Мария Чудновский, Нил Робертсон, Пол Сеймур және Робин Томас 2002 жылы дәлелдеуді жариялады, ал олар 2006 жылы оны толықтырып басып шығарды. Мықты кемел граф теоремасын дәлелдеуі үшін авторлар Карнеги Меллон университетінің Жерар Корнуэхольс ұсынған 10 000 долларлық сыйлықты және 2009 жылғы Фулкерсон сыйлығын жеңіп алды.

Айтылым

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

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

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

Идеяларды дәлелдеу

Чудновский және басқалардың күшті кемелді граф теоремасының дәлелі 2001 жылы Конфорти, Корнежольс, Робертсон, Сеймур және Томас болжаған сызбаға сәйкес келеді. Оған сәйкес, әрбір Берге графы негізгі құрылыс блогының бес түрінің бірін (кемелді графтардың арнайы сыныптары) құрайды немесе ол қарапайым графтарға ыдыраудың төрт түрінің бірін иеленеді. Минималды түрде кемшілдікке ие Берге графының мұндай ыдыраулары болмайды, сондықтан теоремаға қарсы мысал болуы мүмкін емес. Бұл идея бұрынғы ұқсас құрылымдық ыдырауларға негізделген, олар күшті кемелді граф болжамын білдіретін еді, бірақ жалған болып шықты. Осы құрылымдық ыдыраудың негізгі жағдайын құрайтын кемелді графтардың бес негізгі классы: екі бөлікті графиктер, екі бөлікті графиктердің сызықтық графиктері, екі бөлікті графиктердің толықтыру графиктері, екі бөлікті графиктердің сызықтық графиктерінің толықтырулары және қос бөлікті графиктер. Екі бөлікті графиктердің кемелді екенін көру оңай: кез келген тривиалды емес индукцияланған субграфикте клика саны мен хроматикалық саны екеуі де екіге тең, демек, тең. Екі бөлікті графиктердің толықтыруларының және екі бөлікті графиктердің сызықтық графиктерінің толықтыруларының кемелділігі Кениг теоремасына тең, ол екі бөлікті графиктердегі максималды сәйкестіктердің, максималды тәуелсіз жиындардың және минималды түйін жапқыштардың өлшемдерін байланыстырады. Екі бөлікті графиктердің сызықтық графиктерінің кемелділігі екі бөлікті графиктердің хроматикалық индексі олардың максималды дәрежесіне тең деген фактімен бірдей. Осы төрт негізгі сыныптың бәрі кемелді. Қос бөлінген графиктер де кемелді екенін көрсетуге болады, олар бөлінген графиктердің туысы болып табылады. Осы дәлелде қарастырылатын ыдыраудың төрт түрі: 2-қосылыстар, 2-қосылыстардың толықтырулары, теңгерімді қисық бөліктер және біртекті жұптар. 2-қосылыс – графтың түйіндерін екі жиынға бөлу, мұнда осы екі жиын арасындағы жиектер екі түйіннен ажыратылған толық екі бөлікті графтарды құрайды. Егер графтың 2-қосылысы болса, онда оны "блоктар" деп аталатын индукцияланған субграфтарға ыдыратуға болады, сол жиынның ішіндегі екі толық екі бөлікті графтардың біреуін екіншісіне жалғастыратын ең қысқа жолмен осы жиынның ішіндегі екі жиынның бірін ауыстыру арқылы; мұндай жол болмаған жағдайда, блок екі жиынның бірін екі түйінмен ауыстыру арқылы құралады, әрқайсысы әрбір толық екі бөлікті субграф үшін. 2-қосылыс егер және тек егер оның екі блогы да кемелді болса ғана кемелді болады. Сондықтан, егер минималды түрде кемшілдікке ие графтың 2-қосылысы болса, ол оның бір блогына тең болуы керек, демек, ол Берге емес, тақ цикл болуы керек. Сол себепті, 2-қосылысы бар минималды түрде кемшілдікке ие граф Берге бола алмайды. Қисық бөлік – графтың түйіндерін екі жиынға бөлу, олардың бірі ажыратылған субграфты, ал екіншісі ажыратылған толықтыруды индукциялайды. Чудновский және басқалар. Қисық бөліктерге қатысты кейбір техникалық шектеулерді енгізді және Chvátal болжамының нәтижесінде пайда болған "салмақты қисық бөліктер" үшін дұрыс екенін көрсетті. Толық болжам күшті кемелді граф теоремасының салдары болып табылады. Біртекті жұп – графтың модульдік ыдырауымен байланысты. Бұл графты V1, V2 және V3 үш жиынға бөлу, мұнда V1 және V2 бірге кем дегенде үш түйінді қамтиды, V3 кем дегенде екі түйінді қамтиды және V3 әрбір түйін v үшін және {1,2} әрбір i үшін v Vi-дегі барлық түйіндерге немесе олардың ешқайсысына да жақын болмайды. Минималды түрде кемшілдікке ие графтың біртекті жұбы болуы мүмкін емес. Күшті кемелді граф болжамын дәлелдегеннен кейін, оны дәлелдеуде пайдаланылған ыдыраулар жиынтығынан біртекті жұптарды жоюға болатындығын көрсету арқылы оңайлатты. Әрбір Берге графының бес негізгі сыныптың біріне жататынын немесе ыдыраудың төрт түрінің бірін иеленетінін дәлелдеу, графтың ішіндегі белгілі бір конфигурациялардың болуына қарай жағдайды талдау арқылы жүзеге асырылады: "созушы" – үш индукцияланған жолға ыдыратылатын субграф, белгілі бір қосымша шектеулерге бағынады, созушының толықтыруы және "дұрыс дөңгелек" – дөңгелек графқа қатысты конфигурация, индукцияланған циклден және кем дегенде үш цикл түйініне жақын және бірнеше қосымша шектеулерге бағынатын орталық түйінден тұрады. Берге графында созушы немесе оның толықтыруы немесе дұрыс дөңгелек бар-жоғы туралы әрбір мүмкін таңдау үшін графтың негізгі сыныптардың біріне жататыны немесе ыдыратылатыны көрсетіледі. Бұл жағдайды талдау дәлелді аяқтайды.

The proof of the strong perfect graph theorem by Chudnovsky et al. follows an outline conjectured in 2001 by Conforti, Cornuéjols, Robertson, Seymour, and Thomas, according to which every Berge graph either forms one of five types of basic building block (special classes of perfect graphs) or it has one of four different types of structural decomposition into simpler graphs. A minimally imperfect Berge graph cannot have any of these decompositions, from which it follows that no counterexample to the theorem can exist. This idea was based on previous conjectured structural decompositions of similar type that would have implied the strong perfect graph conjecture but turned out to be false. The five basic classes of perfect graphs that form the base case of this structural decomposition are the bipartite graphs, line graphs of bipartite graphs, complementary graphs of bipartite graphs, complements of line graphs of bipartite graphs, and double split graphs. It is easy to see that bipartite graphs are perfect: in any nontrivial induced subgraph, the clique number and chromatic number are both two and therefore both equal. The perfection of complements of bipartite graphs, and of complements of line graphs of bipartite graphs, are both equivalent to Kőnig's theorem relating the sizes of maximum matchings, maximum independent sets, and minimum vertex covers in bipartite graphs. The perfection of line graphs of bipartite graphs can be stated equivalently as the fact that bipartite graphs have chromatic index equal to their maximum degree, proven by Thus, all four of these basic classes are perfect. The double split graphs are a relative of the split graphs that can also be shown to be perfect. The four types of decompositions considered in this proof are 2 joins, complements of 2 joins, balanced skew partitions, and homogeneous pairs. A 2 join is a partition of the vertices of a graph into two subsets, with the property that the edges spanning the cut between these two subsets form two vertex disjoint complete bipartite graphs. When a graph has a 2 join, it may be decomposed into induced subgraphs called "blocks", by replacing one of the two subsets of vertices by a shortest path within that subset that connects one of the two complete bipartite graphs to the other; when no such path exists, the block is formed instead by replacing one of the two subsets of vertices by two vertices, one for each complete bipartite subgraph. A 2 join is perfect if and only if its two blocks are both perfect. Therefore, if a minimally imperfect graph has a 2 join, it must equal one of its blocks, from which it follows that it must be an odd cycle and not Berge. For the same reason, a minimally imperfect graph whose complement has a 2 join cannot be Berge. A skew partition is a partition of a graph's vertices into two subsets, one of which induces a disconnected subgraph and the other of which has a disconnected complement; had conjectured that no minimal counterexample to the strong perfect graph conjecture could have a skew partition. Chudnovsky et al. introduced some technical constraints on skew partitions, and were able to show that Chvátal's conjecture is true for the resulting "balanced skew partitions". The full conjecture is a corollary of the strong perfect graph theorem. A homogeneous pair is related to a modular decomposition of a graph. It is a partition of the graph into three subsets V1, V2, and V3 such that V1 and V2 together contain at least three vertices, V3 contains at least two vertices, and for each vertex v in V3 and each i in {1,2} either v is adjacent to all vertices in Vi or to none of them. It is not possible for a minimally imperfect graph to have a homogeneous pair. Subsequent to the proof of the strong perfect graph conjecture, simplified it by showing that homogeneous pairs could be eliminated from the set of decompositions used in the proof. The proof that every Berge graph falls into one of the five basic classes or has one of the four types of decomposition follows a case analysis, according to whether certain configurations exist within the graph: a "stretcher", a subgraph that can be decomposed into three induced paths subject to certain additional constraints, the complement of a stretcher, and a "proper wheel", a configuration related to a wheel graph, consisting of an induced cycle together with a hub vertex adjacent to at least three cycle vertices and obeying several additional constraints. For each possible choice of whether a stretcher or its complement or a proper wheel exists within the given Berge graph, the graph can be shown to be in one of the basic classes or to be decomposable. This case analysis completes the proof.