Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
Бағытталмаған график оның комплемент графы да кемелді болса және тек сонда ғана кемелді болады.
An undirected graph is perfect if and only if its complement graph is also perfect
Графтар теориясында, кемелді граф теоремасы бойынша бағытталмаған график оның комплемент графы да кемелді болса және тек сонда ғана кемелді болады. Бұл нәтиже болжамдалған және кейде оны күшті кемелді граф теоремасынан ажырату үшін әлсіз кемелді граф теоремасы деп атайды.
In graph theory, the perfect graph theorem of states that an undirected graph is perfect if and only if its complement graph is also perfect. This result had been conjectured by , and it is sometimes called the weak perfect graph theorem to distinguish it from the strong perfect graph theorem characterizing perfect graphs by their forbidden induced subgraphs.
Мысал
G – үштен үлкен тақ ұзындығы бар циклдік граф болсын ("тақ тесік" деп аталады). Онда G кез келген бояуда кем дегенде үш түс қажет етеді, бірақ үшбұрышы жоқ, сондықтан ол толық емес. Толық граф теоремасы бойынша, G-нің толықтырылысы ("тақ антитесік") да толық емес болуы керек. Егер G бес төбесі бар цикл болса, ол өзінің толықтырылысына изоморфты, бірақ бұл қасиет ұзын тақ циклдар үшін осылай емес, және тақ тесіктегідей тақ антитесікте клика саны мен хроматикалық санды есептеу оңай емес. Күшті толық граф теоремасы бойынша, тақ тесіктер мен тақ антитесіктер толық графтар үшін ең кішкентай тыйым салынған индукцияланған кішграфтар болып табылады.
Let G be a cycle graph of odd length greater than three (a so called "odd hole"). Then G requires at least three colors in any coloring, but has no triangle, so it is not perfect. By the perfect graph theorem, the complement of G (an "odd antihole") must therefore also not be perfect. If G is a cycle of five vertices, it is isomorphic to its complement, but this property is not true for longer odd cycles, and it is not as trivial to compute the clique number and chromatic number in an odd antihole as it is in an odd hole. As the strong perfect graph theorem states, the odd holes and odd antiholes turn out to be the minimal forbidden induced subgraphs for the perfect graphs.
Қолданбалар
Баяғы емес екіжақты графтарда түстердің оңтайлы саны (анықтама бойынша) екі, ал (екіжақты графтар үшбұрышсыз болғандықтан) максималды кликаның мөлшері де екі. Сондай-ақ, екіжақты графтың кез келген индуцирленген кіші графы екіжақты болып қалады. Сондықтан, екіжақты графтар кемелді. n төбесі бар екіжақты графтарда, ең кішкентай кликалық жабын максималды сәйкестік түрінде болады, сонымен қатар әрбір сәйкес келмейтін төбе үшін n - M мөлшерінде қосымша кликамен бірге, мұнда M – сәйкестіктің кардиналдығы. Осылайша, осы жағдайда кемелді граф теоремасы Кёниг теоремасын білдіреді, екіжақты графтағы ең үлкен тәуелсіз жиынның мөлшері де n - M, бұл Бергенің кемелді графтар теориясын қалыптастыруына үлкен ықпал етті. Мырский теоремасы, ішінара реттелген жиынның биіктігін антитізбектерге бөлу арқылы сипаттайды және оны ішінара реттелген жиынның салыстырылатындығы графигінің кемелділігі ретінде тұжырымдауға болады, ал Дилворт теоремасы ішінара реттелген жиынның енін тізбектерге бөлу арқылы сипаттайды және оны осы графтардың толықтыруларының кемелділігі ретінде тұжырымдауға болады. Осылайша, кемелді граф теоремасын Мирский теоремасының (әлдеқайда оңай) дәлелінен Дилворт теоремасын немесе керісінше дәлелдеу үшін пайдалануға болады.
In a nontrivial bipartite graph, the optimal number of colors is (by definition) two, and (since bipartite graphs are triangle free) the maximum clique size is also two. Also, any induced subgraph of a bipartite graph remains bipartite. Therefore, bipartite graphs are perfect. In n vertex bipartite graphs, a minimum clique cover takes the form of a maximum matching together with an additional clique for every unmatched vertex, with size n − M, where M is the cardinality of the matching. Thus, in this case, the perfect graph theorem implies Kőnig's theorem that the size of a maximum independent set in a bipartite graph is also n − M, a result that was a major inspiration for Berge's formulation of the theory of perfect graphs. Mirsky's theorem characterizing the height of a partially ordered set in terms of partitions into antichains can be formulated as the perfection of the comparability graph of the partially ordered set, and Dilworth's theorem characterizing the width of a partially ordered set in terms of partitions into chains can be formulated as the perfection of the complements of these graphs. Thus, the perfect graph theorem can be used to prove Dilworth's theorem from the (much easier) proof of Mirsky's theorem, or vice versa.
Ловастың дәлелі
Кемел граф теоремасын дәлелдеу үшін Ловас графтың төбелерін кликалармен алмастыру амалын қолданды; Бергеге бұрыннан графтың кемелді болса, осы алмастыру процесінен пайда болған графтың да кемелді болатыны белгілі еді. Мұндай алмастыру процесін төбелікті екі еселеудің қайталама қадамдарына бөлуге болады. Егер екі еселенген төбе графтың максималды кликасына жатса, ол клика саны мен хроматикалық санды бірге арттырады. Ал егер екі еселенген төбе максималды кликаға жатпаса, берілген графтың оптималды түстеуінен екі еселенген төбемен бірдей түсті төбелерді (бірақ екі еселенген төбенің өзін емес) алып тастау арқылы H графы құрылады. Алып тасталған төбелер мен екі еселенген төбенің жаңа көшірмесін бір түс класы ретінде қосуға болады, осылайша бұл жағдайда екі еселеу қадамы хроматикалық санды өзгерте алмайтыны көрсетіледі. Осы аргумент екі еселеудің берілген графтың кез келген индукцияланған подграфында клика саны мен хроматикалық санның теңдігін сақтайтынын көрсетеді, сондықтан әрбір екі еселеу қадамы графтың кемелділігін сақтайды. Кемел граф G болғанда, Ловас әрбір төбе v-ні tv төбеден тұратын кликамен алмастыру арқылы G* графы құрайды, мұнда tv – G-дегі v-ні қамтитын әртүрлі максималды тәуелсіз жиындардың саны. G-дегі әртүрлі максималды тәуелсіз жиындарды G*-дегі максималды тәуелсіз жиындардың бірімен сәйкестендіруге болады, осылайша G-дегі таңдалған максималды тәуелсіз жиындардың барлығы бірін-бірі қимайды және G-дің әрбір төбесі бір таңдалған жиынға енеді; яғни G* әрбір түс класы максималды тәуелсіз жиын болатын түстеуге ие. Бұл түстеу G*-дің оптималды түстеуі болуы керек. G кемелді болғандықтан, G* да кемелді, сондықтан оның K* максималды кликасы бар, оның мөлшері осы түстеудегі түстер санына тең, яғни G-дегі әртүрлі максималды тәуелсіз жиындардың саны; міндетті түрде K* осы максималды тәуелсіз жиындардың әрқайсысы үшін ерекше өкілді қамтиды. G-дегі K төбелер жиыны (G*-дегі кеңейтілген кликалары K*-мен қиылысатын төбелер) G-дегі әрбір максималды тәуелсіз жиынды қиып алатын қасиетке ие клика болып табылады. Сондықтан, G-ден K-ні алып тастау арқылы құрылған графтың кликалық жабын саны G-дің кликалық санынан кем дегенде біреуге кем, ал тәуелсіздік саны G-дің тәуелсіздік санынан кем дегенде біреуге кем, және нәтиже осы сан бойынша индукция арқылы шығады.
To prove the perfect graph theorem, Lovász used an operation of replacing vertices in a graph by cliques; it was already known to Berge that, if a graph is perfect, the graph formed by this replacement process is also perfect. Any such replacement process may be broken down into repeated steps of doubling a vertex. If the doubled vertex belongs to a maximum clique of the graph, it increases both the clique number and the chromatic number by one. If, on the other hand, the doubled vertex does not belong to a maximum clique, form a graph H by removing the vertices with the same color as the doubled vertex (but not the doubled vertex itself) from an optimal coloring of the given graph. The removed vertices meet every maximum clique, so H has clique number and chromatic number one less than that of the given graph. The removed vertices and the new copy of the doubled vertex can then be added back as a single color class, showing that in this case the doubling step leaves the chromatic number unchanged. The same argument shows that doubling preserves the equality of the clique number and the chromatic number in every induced subgraph of the given graph, so each doubling step preserves the perfection of the graph. Given a perfect graph G, Lovász forms a graph G* by replacing each vertex v by a clique of tv vertices, where tv is the number of distinct maximum independent sets in G that contain v. It is possible to correspond each of the distinct maximum independent sets in G with one of the maximum independent sets in G*, in such a way that the chosen maximum independent sets in G* are all disjoint and each vertex of G* appears in a single chosen set; that is, G* has a coloring in which each color class is a maximum independent set. Necessarily, this coloring is an optimal coloring of G*. Because G is perfect, so is G*, and therefore it has a maximum clique K* whose size equals the number of colors in this coloring, which is the number of distinct maximum independent sets in G; necessarily, K* contains a distinct representative for each of these maximum independent sets. The corresponding set K of vertices in G (the vertices whose expanded cliques in G* intersect K*) is a clique in G with the property that it intersects every maximum independent set in G. Therefore, the graph formed from G by removing K has clique cover number at most one less than the clique number of G, and independence number at least one less than the independence number of G, and the result follows by induction on this number.
Күшті кемелдік граф теоремасымен байланысы
Күшті кемелді граф теоремасы графтың кемелді екенін, оның ешбір индукцияланған кішкентай графтары бестен үлкен немесе беске тең тақ ұзындықтағы циклдар немесе олардың толықтырғыштары болмаса ғана анықтайды. Бұл сипаттама графты толықтыруға тәуелді болмағандықтан, ол әлсіз кемелді граф теоремасын тікелей білдіреді.
The strong perfect graph theorem of states that a graph is perfect if and only if none of its induced subgraphs are cycles of odd length greater than or equal to five, or their complements. Because this characterization is unaffected by graph complementation, it immediately implies the weak perfect graph theorem.
Жалпылау
дәлелдеді, егер толық графтың қабырғалары үш субграфқа бөлінсе, осылайша кез келген үш төбе үш субграфтың бірінде байланысқан графты тудырады, және егер екі субграф кемел болса, үшінші субграф та кемел болады. Кемел график теоремасы – үш субграфтың бірі бос граф болғанда осы нәтиженің ерекше жағдайы болып табылады.
proved that, if the edges of a complete graph are partitioned into three subgraphs in such a way that every three vertices induce a connected graph in one of the three subgraphs, and if two of the subgraphs are perfect, then the third subgraph is also perfect. The perfect graph theorem is the special case of this result when one of the three subgraphs is the empty graph.