Графтардағы түйіндік бояу және толық подграфтар туралы

Кіріспе

Графиктерде тығыз кликалық бояу қатынасы

Граф теориясында, кемел график – бұл хроматикалық саны графиктің өзінде де, әрбір туынды субграфикте де ең үлкен кликаның өлшеміне тең болатын график. Барлық графиктерде хроматикалық сан максималды кликаның өлшемінен үлкен немесе оған тең болады, бірақ бұл шамалар айтарлықтай өзгеше болуы мүмкін. График, егер осы сандар тең болса және төбелердің кез келген жиынын жойғаннан кейін де тең болып қалатын болса, кемел деп аталады. Кемел графиктер көптеген маңызды графтар отбасыларын қамтиды және осы отбасылардағы бояулар мен кликаларға қатысты нәтижелерді біріктіруге көмектеседі. Мысалы, барлық кемел графиктерде графиктерді бояу мәселесі, максималды клика мәселесі және максималды тәуелсіз жиын мәселесі, кемел емес графиктерге қарағанда күрделі болғанымен, полиномиалдық уақытта шешіледі. Сонымен қатар, комбинаторикадағы бірнеше маңызды минимакс теоремалары, оның ішінде Дилворт теоремасы және Мирскийдің ішінара реттелген жиындар туралы теоремасы, Кёнигтің сәйкестіктер туралы теоремасы және Эрдёш-Секерес теоремасы монотондық тізбектер туралы, белгілі бір байланысты графтардың кемелдігі тұрғысынан тұжырымдалады. Кемел график теоремасына сәйкес, кемел графиктің толықтыру графигі де кемел болады. Күшті кемел график теоремасы белгілі бір тыйым салынған туынды субграфтар арқылы кемел графиктерді сипаттайды, бұл график кемел екенін тексеруге арналған полиномиалдық уақыт алгоритмін құруға мүмкіндік береді.

Анықтамалар мен сипаттамалар

Бағытталмаған графиктегі клика – оның бір-біріне тікелей қосылған төбелерінің жиыны, мысалы, суреттегі қалың сызықтармен байланысқан төбелер. Клика саны – ең үлкен кликадағы төбелердің саны: көрсетілген жеті төбелі циклде екі, ал басқа графикте үш. График түсі – әр төбеге түс тағайындау, сонда әрбір екі жапсарлас төбе әртүрлі түспен боялады, бұл да суретте көрсетілген. График хроматикалық саны – кез келген түстеудегі ең аз түс саны. Көрсетілген түстеулер оңтайлы, сондықтан 7 цикл үшін хроматикалық сан үш, ал басқа график үшін төрт. Кез келген кликаның төбелері әртүрлі түспен боялуы керек, сондықтан хроматикалық сан әрқашан клика санынан үлкен немесе оған тең болады. Кейбір графтар үшін олар тең, ал басқаларында, мысалы, көрсетілгендерде, тең емес. Кемел графтар – осы екі сан тең болатын графтар ретінде анықталады, ғана емес, сонымен қатар оның бірнеше төбелері алынып тасталған кез келген индукцияланған кіші графтарда да. Кемел граф теоремасы кемел графтың толықтыру графының өзі де кемел екенін айтады. Толықтыру графында екі төбе арасында қабырға бар, егер және тек қана берілген графта қабырға болмаса. Толықтыру графындағы клика, берілген графтағы тәуелсіз жиынға сәйкес келеді. Толықтыру графының түстеуі кликалық жабуды білдіреді, яғни берілген графтың төбелерін кликаларға бөлу. Кемел графтың толықтыруының да кемел екендігі, оның тәуелсіздік санының (оның ең үлкен тәуелсіз жиынының мөлшері) кликалық жабу санына (кликелік жабуда қажетті кликалардың ең аз санына) тең екенін білдіреді. Күштірек айтқанда, бұл толықтыру графының кез келген индукцияланған кіші графында да осылай болады. Бұл кемел графтардың баламалы және эквивалентті анықтамасын береді: олар – әрбір индукцияланған кіші графтарда тәуелсіздік саны кликалық жабу санына тең болатын графтар. Күшті кемел граф теоремасы кемел графтарды олардың қасиеттері арқылы емес, құрылымы бойынша анықтаудың басқа жолын ұсынады. Ол циклдік графтар мен олардың берілген графтардағы толықтыруларының болуына негізделген. Үштен үлкен тақ ұзындығы бар цикл кемелді емес: оның клика саны екі, бірақ хроматикалық саны үш. Кемел граф теоремасы бойынша, үштен үлкен тақ циклдің толықтыруы да кемелді емес. Ұзындығы 5 циклдің толықтыруы – тағы бір ұзындығы 5 цикл, бірақ үлкен тақ ұзындығы үшін толықтыру цикл емес; ол антицикл деп аталады. Күшті кемел граф теоремасы бұл кемел графтар үшін жалғыз тыйым салынған индукцияланған кіші графтар екенін айтады: граф кемелді, егер және тек қана оның индукцияланған кіші графтары бес немесе одан да көп төбелері бар тақ цикл немесе тақ антициклді қамтымаса. Бұл жағдайда үшбұрыштар емес индукцияланған циклдер «тесіктер» деп аталады, ал олардың толықтырулары «антитесіктер» деп аталады, сондықтан күшті кемел граф теоремасын қысқаша айтуға болады: граф кемелді, егер және тек қана онда тақ тесік немесе тақ антитесік болмаса. Бұл нәтижелерді кемел графтардың тағы бір сипаттамасында біріктіруге болады: олар – клика саны мен тәуелсіздік санының көбейтіндісі төбелер санынан үлкен немесе оған тең болатын және барлық индукцияланған кіші графтар үшін де осылай болатын графтар. Бұл сипаттаманың мәлімдемесі графтардың толықтырылуы кезінде өзгермейтін болып қала беретіндіктен, ол кемел граф теоремасын білдіреді. Бұл сипаттаманың бір бағыты кемелділіктің бастапқы анықтамасынан оңай туындайды: кез келген графтағы төбелердің саны оптималды түстеудегі түс кластарының өлшемдерінің қосындысына тең және тәуелсіздік санына көбейтілген түстер санынан кем немесе оған тең. Кемел графта түстер саны клика санына тең, және оны осы теңсіздіктегі клика санымен ауыстыруға болады. Екінші бағытты тікелей дәлелдеуге болады, бірақ ол сондай-ақ күшті кемел граф теоремасынан туындайды: егер граф кемелді болмаса, онда ол тақ цикл немесе оның толықтыруын қамтиды, ал бұл кіші графтарда клика саны мен тәуелсіздік санының көбейтіндісі төбелер санынан бір кем.

A clique in an undirected graph is a subset of its vertices that are all adjacent to each other, such as the subsets of vertices connected by heavy edges in the illustration. The clique number is the number of vertices in the largest clique: two in the illustrated seven vertex cycle, and three in the other graph shown. A graph coloring assigns a color to each vertex so that each two adjacent vertices have different colors, also shown in the illustration. The chromatic number of a graph is the minimum number of colors in any coloring. The colorings shown are optimal, so the chromatic number is three for the 7 cycle and four for the other graph shown. The vertices of any clique must have different colors, so the chromatic number is always greater than or equal to the clique number. For some graphs, they are equal; for others, such as the ones shown, they are unequal. The perfect graphs are defined as the graphs for which these two numbers are equal, not just in the graph itself, but in every induced subgraph obtained by deleting some of its vertices. The perfect graph theorem asserts that the complement graph of a perfect graph is itself perfect. The complement graph has an edge between two vertices if and only if the given graph does not. A clique, in the complement graph, corresponds to an independent set in the given. A coloring of the complement graph corresponds to a clique cover, a partition of the vertices of the given graph into cliques. The fact that the complement of a perfect graph is also perfect implies that, in itself, the independence number (the size of its maximum independent set), equals its clique cover number (the fewest number of cliques needed in a clique cover). More strongly, the same thing is true in every induced subgraph of the complement graph. This provides an alternative and equivalent definition of the perfect graphs: they are the graphs for which, in each induced subgraph, the independence number equals the clique cover number. The strong perfect graph theorem gives a different way of defining perfect graphs, by their structure instead of by their properties. It is based on the existence of cycle graphs and their complements within a given graph. A cycle of odd length, greater than three, is not perfect: its clique number is two, but its chromatic number is three. By the perfect graph theorem, the complement of an odd cycle of length greater than three is also not perfect. The complement of a length 5 cycle is another length 5 cycle, but for larger odd lengths the complement is not a cycle; it is called an anticycle. The strong perfect graph theorem asserts that these are the only forbidden induced subgraphs for the perfect graphs: a graph is perfect if and only if its induced subgraphs include neither an odd cycle nor an odd anticycle of five or more vertices. In this context, induced cycles that are not triangles are called "holes", and their complements are called "antiholes", so the strong perfect graph theorem can be stated more succinctly: a graph is perfect if and only if it has neither an odd hole nor an odd antihole. These results can be combined in another characterization of perfect graphs: they are the graphs for which the product of the clique number and independence number is greater than or equal to the number of vertices, and for which the same is true for all induced subgraphs. Because the statement of this characterization remains invariant under complementation of graphs, it implies the perfect graph theorem. One direction of this characterization follows easily from the original definition of perfect: the number of vertices in any graph equals the sum of the sizes of the color classes in an optimal coloring, and is less than or equal to the number of colors multiplied by the independence number. In a perfect graph, the number of colors equals the clique number, and can be replaced by the clique number in this inequality. The other direction can be proved directly, but it also follows from the strong perfect graph theorem: if a graph is not perfect, it contains an odd cycle or its complement, and in these subgraphs the product of the clique number and independence number is one less than the number of vertices.

Тарих

Толық графтар теориясы Тибор Галлайдың 1958 жылғы нәтижесінен қалыптасты, оны қазіргі тілмен екі бөлікті графтың толықтығы толық деп түсіндіруге болады; бұл нәтиже екі бөлікті графтардағы сәйкестіктер мен төбелік жамылғыштарды байланыстыратын Кёниг теоремасының қарапайым теңдесі ретінде де қарастырылуы мүмкін. "Толық граф" түсінігін алғаш рет 1961 жылы Клод Берге неміс тіліндегі мақаласында келтірді, ал "толық граф" фразасы алғаш рет Бергенің 1963 жылғы мақаласында пайда болған сияқты. Осы еңбектерінде ол Галлайдың нәтижесін бірнеше ұқсас нәтижелермен біріктіріп, толық графтарды анықтады және толық граф теоремасы мен күшті толық граф теоремасын болжады. Осы ұғымдарды қалыптастырғанда Берге графтың Шеннон сыйымдылығы, (ко)толық графтар үшін ол тәуелсіздік санына тең екендігі және осыған сәйкес келмейтін графтардың ең минималды мысалдарын табу фактісімен ынталандырылды. Күшті толық граф теоремасы дәлелденгенге дейін, оның сипаттаған графтары (яғни, тақ циклдары мен тақ антициклдары жоқ графтар) Берге графтары деп аталды. Толық граф теоремасын 1972 жылы Ласло Ловас дәлелдеді, ол сол жылы күшті толық граф теоремасын пайдаланбастан, төбелер саны мен клика саны мен тәуелсіздік санының көбейтіндісі арасындағы күшті теңсіздікті дәлелдеді. 1991 жылы Альфред Леман математикалық оптимизация қоғамы мен Америка математика қоғамының бірлескен демеушілігімен берілетін Фулкерсон сыйлығын толық графтар теориясын логикалық матрицаларға жалпылау жөніндегі жұмысы үшін жеңіп алды. Болжамдалған күшті толық граф теоремасы көп жылдар бойы толық графтар теориясындағы зерттеулердің басты назары болды, оның дәлелі 2002 жылы Мария Чудновская, Нил Робертсон, Пол Сеймур және Робин Томас жариялады, ал 2006 жылы олар басып шығарды. Бұл жұмыс авторларына 2009 жылғы Фулкерсон сыйлығын жеңіп берді. Толық граф теоремасының қысқа дәлелі бар, бірақ күшті толық граф теоремасының дәлелі ұзақ және техникалық, ол Берге графтарының терең құрылымдық декомпозициясына негізделген. Байланысты декомпозиция техникалары басқа графтар кластарын зерттеуде де жемісті болды, әсіресе тырнақсыз графтар үшін. Клика саны мен тәуелсіздік санының көбейтіндісі тұрғысынан толық графтардың симметриялық сипаттамасы бастапқыда Хайнал ұсынған, ал Ловас дәлелдеген.

The theory of perfect graphs developed from a 1958 result of Tibor Gallai that in modern language can be interpreted as stating that the complement of a bipartite graph is perfect; this result can also be viewed as a simple equivalent of Kőnig's theorem, a much earlier result relating matchings and vertex covers in bipartite graphs. The first formulation of the concept of perfect graphs more generally was in a 1961 paper by Claude Berge, in German, and the first use of the phrase "perfect graph" appears to be in a 1963 paper of Berge. In these works he unified Gallai's result with several similar results by defining perfect graphs, and he conjectured both the perfect graph theorem and the strong perfect graph theorem. In formulating these concepts, Berge was motivated by the concept of the Shannon capacity of a graph, by the fact that for (co )perfect graphs it equals the independence number, and by the search for minimal examples of graphs for which this is not the case. Until the strong perfect graph theorem was proven, the graphs described by it (that is, the graphs with no odd hole and no odd antihole) were called Berge graphs. The perfect graph theorem was proven by László Lovász in 1972, who in the same year proved the stronger inequality between the number of vertices and the product of the clique number and independence number, without benefit of the strong perfect graph theorem. In 1991, Alfred Lehman won the Fulkerson Prize, sponsored jointly by the Mathematical Optimization Society and American Mathematical Society, for his work on generalizations of the theory of perfect graphs to logical matrices. The conjectured strong perfect graph theorem became the focus of research in the theory of perfect graphs for many years, until its proof was announced in 2002 by Maria Chudnovsky, Neil Robertson, Paul Seymour, and Robin Thomas, and published by them in 2006. This work won its authors the 2009 Fulkerson Prize. The perfect graph theorem has a short proof, but the proof of the strong perfect graph theorem is long and technical, based on a deep structural decomposition of Berge graphs. Related decomposition techniques have also borne fruit in the study of other graph classes, and in particular for the claw free graphs. The symmetric characterization of perfect graphs in terms of the product of clique number and independence number was originally suggested by Hajnal and proven by Lovász.

Графиктердің отбасылары

Көптеген жақсы зерттелген графтар отбасылары кемелді, және көп жағдайда осы графтардың кемелді болуы осы графтармен анықталатын комбинаторлық құрылымның кейбір түрлері үшін минимакс теоремасына сәйкес келеді. Бұл құбылыстың мысалдары – екібөлімді графтар мен олардың желілік графтарының кемелділігі, Кениг теоремасымен байланысты, екібөлімді графтардағы максималды сәйкестіктер мен төбелік жамылғыштарды қамтиды, сондай-ақ салыстырылатын графтардың кемелділігі, Дилворт теоремасымен және Мирский теоремасымен байланысты, бұл теоремалар ішінара реттелген жиынтықтардағы тізбектер мен антитізбектер туралы айтады. Қатты кемелдік граф теоремасының тесіктері мен антитесіктерімен байланысты құрылымға ие графтардың басқа маңызды кластарына хордалық графтар, Мейниел графтары және олардың кіші топтары кіреді.

Екі жақты графиктер мен сызықтық графиктер

Екі жақты графтарда (кем дегенде бір қабырғасы бар) хроматикалық сан мен клика саны екеуі де екіге тең. Олардың туынды подграфтары екі жақты болып қалады, сондықтан екі жақты графтар кемелді. Графтардың басқа маңызды отбасылары да екі жақты, демек кемелді, мысалы, ағаштар және медианалық графтар. Кемел граф теоремасына сәйкес, екі жақты графтардағы максималды тәуелсіз жиынның мөлшері олардың минималды кликалық жабынының мөлшерімен бірдей. Максималды тәуелсіз жиын, барлық қабырғаларын тигізетін түйіндер жиынынан – минималды түйін жабынына толықтырады. Минималды кликалық жабын, барлық қалған түйіндер үшін максималды сәйкестіктен (мүмкіндігінше көп ажыратылған қабырғалардан) және бір түйінді кликалардан тұрады, ал оның мөлшері – түйіндердің санынан сәйкес келетін қабырғалардың саны кем. Сондықтан, бұл теңдікті екі жақты графтардағы максималды сәйкестіктің және минималды түйін жабынының мөлшері арасындағы теңдік ретінде де көрсетуге болады, бұл Кёниг теоремасының стандартты тұжырымы. Кез келген графтағы сәйкестік, сызықтық графтың тәуелсіз жиынымен бірдей, онда әр қабырға үшін бір түйін болады және әр екі қабырға үшін ортақ ұшы бар екі түйін арасында қабырға болады. Сызықтық графтарда екі түрлі кликалар бар: ортақ түйіні бар қабырғалар жиыны және үшбұрыштар. Екі жақты графтарда үшбұрыштар жоқ, сондықтан кликалық жабын, сызықтық графтың түйін жабынына сәйкес келеді. Сондықтан, екі жақты графтардың сызықтық графтарында тәуелсіздік саны мен кликалық жабын саны тең. Сызықтық графтардың туынды подграфтары, подграфтардың сызықтық графтары болып табылады, сондықтан екі жақты графтардың сызықтық графтары кемелді. Мысалдарға мұнара графтары, толық екі жақты графтардың сызықтық графтары жатады. Екі жақты графтың кез келген сызықтық графы, мұнара графтарының туынды подграфы болып табылады. Сызықтық графтар екі жақты болғандықтан, олардың клика саны олардың хроматикалық санына тең. Екі жақты графтың сызықтық графының клика саны, негізгі екі жақты графтың кез келген түйінінің максималды дәрежесіне тең. Екі жақты графтың сызықтық графының хроматикалық саны, негізгі екі жақты графтың хроматикалық индексіне тең, яғни қабырғаларды бояу үшін қажетті ең аз түстер саны, сонда жанасқан қабырғалар әртүрлі түске ие болады. Әр түс класы сәйкестік құрайды, ал хроматикалық индекс – барлық қабырғаларды жабу үшін қажетті сәйкестіктердің ең аз саны. Екі жақты графтардағы максималды дәреже мен хроматикалық индекс теңдігі – Денес Кёнигтің тағы бір теоремасы. Кез келген қарапайым графтарда олар бірге айырмашылығы болуы мүмкін; бұл Визинг теоремасы. Кемел сызықтық графтың негізгі графы – сызықтық кемел граф. Бұл екі жақты графтар, толық графтар және үшбұрышты кітаптар, ортақ қабырғаға ие үшбұрыштар жиыны. Бұл компоненттер кемелді, олардың үйлесімдері кемелділікті сақтайды, сондықтан кез келген сызықтық кемел граф кемелді. Екі жақты графтар, олардың толықтырулары және екі жақты графтардың сызықтық графтары мен олардың толықтырулары, күшті кемел граф теоремасының дәлелінде маңызды рөл атқаратын кемел графтардың төрт негізгі класын құрайды. Осы дәлелдемеде қолданылатын кемел графтардың құрылымдық декомпозициясына сәйкес, осы төрт классқа жатпайтын кез келген кемел графты, оның түйіндерін төрт жолдың бірімен – 2-қосылыс, 2-қосылыстың толықтыруы, біртекті жұп немесе қисық бөлім деп аталатын кіші топтарға бөлу арқылы декомпозициялауға болады.

In bipartite graphs (with at least one edge) the chromatic number and clique number both equal two. Their induced subgraphs remain bipartite, so bipartite graphs are perfect. Other important families of graphs are bipartite, and therefore also perfect, including for instance the trees and median graphs. By the perfect graph theorem, maximum independent sets in bipartite graphs have the same size as their minimum clique covers. The maximum independent set is complementary to a minimum vertex cover, a set of vertices that touches all edges. A minimum clique cover consists of a maximum matching (as many disjoint edges as possible) together with one vertex cliques for all remaining vertices, and its size is the number of vertices minus the number of matching edges. Therefore, this equality can be expressed equivalently as an equality between the size of the maximum matching and the minimum vertex cover in bipartite graphs, the usual formulation of Kőnig's theorem. A matching, in any graph , is the same thing as an independent set in the line graph , a graph that has a vertex for each edge in and an edge between two vertices in for each pair of edges in that share an endpoint. Line graphs have two kinds of cliques: sets of edges in with a common endpoint, and triangles in In bipartite graphs, there are no triangles, so a clique cover in corresponds to a vertex cover in Therefore, in line graphs of bipartite graphs, the independence number and clique cover number are equal. Induced subgraphs of line graphs of bipartite graphs are line graphs of subgraphs, so the line graphs of bipartite graphs are perfect. Examples include the rook's graphs, the line graphs of complete bipartite graphs. Every line graph of a bipartite graph is an induced subgraph of a rook's graph. Because line graphs of bipartite graphs are perfect, their clique number equals their chromatic number. The clique number of the line graph of a bipartite graph is the maximum degree of any vertex of the underlying bipartite graph. The chromatic number of the line graph of a bipartite graph is the chromatic index of the underlying bipartite graph, the minimum number of colors needed to color the edges so that touching edges have different colors. Each color class forms a matching, and the chromatic index is the minimum number of matchings needed to cover all edges. The equality of maximum degree and chromatic index, in bipartite graphs, is another theorem of Dénes Kőnig. In arbitrary simple graphs, they can differ by one; this is Vizing's theorem. The underlying graph of a perfect line graph is a line perfect graph. These are the graphs whose biconnected components are bipartite graphs, the complete graph , and triangular books, sets of triangles sharing an edge. These components are perfect, and their combination preserves perfection, so every line perfect graph is perfect. The bipartite graphs, their complements, and the line graphs of bipartite graphs and their complements form four basic classes of perfect graphs that play a key role in the proof of the strong perfect graph theorem. According to the structural decomposition of perfect graphs used as part of this proof, every perfect graph that is not already in one of these four classes can be decomposed by partitioning its vertices into subsets, in one of four ways, called a 2 join, the complement of a 2 join, a homogeneous pair, or a skew partition.

Салыстырмалылық графиктері

Ішінара реттелген жиын элементтер жиынтығымен анықталады, ал салыстыру қатынасы рефлексивті (барлық элементтер үшін), антисимметриялық (егер және , онда ) және транзитивті (егер және , онда ) болады. Элементтер және салыстырмалы, ал әйтпесе – салыстырусыз. Мысалы, жиынтықтың кіші жиынтығының қатысы кез келген жиынтар жинағын ішінара реттейді. Ішінара реттелген жиынның салыстырмалылық графигінде жиын элементтері төбелер болып табылады, ал кез келген екі салыстырмалы элементті қосатын қабырға бар. Оның толықтығы – салыстырусыздық графигі деп аталады. Әртүрлі ішінара реттелулердің бірдей салыстырмалылық графигі болуы мүмкін; мысалы, барлық салыстыруларды кері қайтару реттілікті өзгертеді, бірақ графикті емес. Шектеулі салыстырмалылық графиктері (және олардың толықтырылған салыстырусыздық графиктері) әрқашан кемелді болады. Салыстырмалылық графигіндегі клика – барлық жұптары салыстырмалы элементтердің кіші жиынтығынан туындайды; мұндай кіші жиынтық тізбек деп аталады және берілген ішінара реттелу бойынша сызықтық реттелуге ие. Тәуелсіз жиын – екеуі де салыстырмалы емес элементтердің кіші жиынтығынан туындайды; мұндай кіші жиынтық антитізбек деп аталады. Мысалы, көрсетілген ішінара реттелуде және салыстырмалылық графигінде – тізбек, ал – антитізбек. Осылайша, салыстырмалылық графигін түстеу – оның элементтерін антитізбектерге бөлу, ал кликалық жабын – элементтерін тізбектерге бөлу. Дилворт теоремасы, ішінара реттелулер теориясында, кез келген шектеулі ішінара реттелу үшін ең үлкен антитізбектің мөлшері элементтерді бөлуге болатын ең аз тізбектер санына тең болады. Графиктер тілінде бұл былай тұжырымдалады: кез келген шектеулі салыстырмалылық графигі кемелді. Сол сияқты, Мирский теоремасы кез келген шектеулі ішінара реттелу үшін ең үлкен тізбектің мөлшері элементтерді бөлуге болатын ең аз антитізбектер санына тең немесе кез келген шектеулі салыстырусыздық графигі кемелді. Бұл екі теорема кемелді график теоремасы арқылы эквивалентті, бірақ Мирский теоремасын Дилворт теоремасына қарағанда тікелей дәлелдеу оңай: егер әрбір элемент ең үлкен тізбектегі максималдығының мөлшерімен белгіленсе, онда тең белгілерге ие кіші жиынтықтар антитізбектерге бөлінеді, антитізбектердің саны жалпы ең үлкен тізбектің мөлшеріне тең. Кез келген екі бөліктік график – салыстырмалылық графигі. Осылайша, Кёниг теоремасын Дилворт теоремасының ерекше жағдайы ретінде қарастыруға болады, ол кемелді графиктер теориясы арқылы байланысты. Пермутациялық график элементтердің толық реттелген тізбегі (әдетте, -ден -ге дейінгі бүтін сандар) бойынша пермутациядан анықталады, олар график төбелері болып табылады. Пермутациялық графиктің қабырғалары берілген пермутация бойынша реттілігі кері айырылатын элементтер жұбын байланыстырады. Бұл табиғи түрде салыстырусыздық графиктері, ішінара реттелу үшін, егер элемент берілген тізбекте және оның пермутациясында бірінші келсе. Пермутациялық графиктің толықтығы – берілген пермутацияның керісі үшін басқа пермутациялық график. Сондықтан, салыстырусыздық графиктерімен қатар, пермутациялық графиктер де салыстырмалылық графиктері болып табылады. Шын мәнінде, пермутациялық графиктер – салыстырмалылық және салыстырусыздық графиктері болатын графиктер. Пермутациялық графиктегі клика – берілген пермутацияда өсу ретімен орналасқан элементтердің тізбегі, ал тәуелсіз жиын – кему ретімен орналасқан элементтердің тізбегі. Кез келген кемелді графикте клика саны мен тәуелсіздік санының көбейтіндісі кемінде элементтер санына тең; пермутациялық графиктер үшін осы теңсіздіктің ерекше жағдайы – Эрдос-Секерес теоремасы. Интервалдық графиктер – интервалдық реттелулердің салыстырусыздық графиктері, интервалдың сол жағында орналасқан нақты сызықтағы интервалдар жиынтығымен анықталған реттелулер. Тиісті интервалдық графикте екі интервалдың ортақ нүктесі болғанда қабырға бар. Бұл графиктерді түстеу тапсырмаларға ресурстарды бөлу мәселелерін модельдеу үшін қолданылуы мүмкін (мысалы, сыныптарды сабақтарға), интервалдар әр тапсырманың жоспарланған уақытын сипаттайды. Интервалдық және пермутациялық графиктер трапециялық графиктермен жалпыланады. Екі емес интервалдардың жүйесі графиктердің шектеулі класын, бейтараптық графиктерін, жартылай реттелулердің салыстырусыздық графиктерін тудырады. Бұлар адамдық қалауларды модельдеу үшін қолданылған, егер заттардың пайдалылығы өте жақын болса, олар салыстырусыз болады деген болжаммен. Әрбір жұп ұяланған немесе бөлек болса, тривиальды кемелді графиктер, реттелген ағаштардың салыстырмалылық графиктері туындайды. Оларда тәуелсіздік саны максималды кликалар санына тең.

A partially ordered set is defined by its set of elements, and a comparison relation that is reflexive (for all elements , ), antisymmetric (if and , then , and transitive (if and , then ). Elements and are comparable if or , and incomparable otherwise. For instance, set inclusion partially orders any family of sets. The comparability graph of a partially ordered set has the set elements as its vertices, with an edge connecting any two comparable elements. Its complement is called an incomparability graph. Different partial orders may have the same comparability graph; for instance, reversing all comparisons changes the order but not the graph. Finite comparability graphs (and their complementary incomparability graphs) are always perfect. A clique, in a comparability graph, comes from a subset of elements that are all pairwise comparable; such a subset is called a chain, and it is linearly ordered by the given partial order. An independent set comes from a subset of elements no two of which are comparable; such a subset is called an antichain. For instance, in the illustrated partial order and comparability graph, is a chain in the order and a clique in the graph, while is an antichain in the order and an independent set in the graph. Thus, a coloring of a comparability graph is a partition of its elements into antichains, and a clique cover is a partition of its elements into chains. Dilworth's theorem, in the theory of partial orders, states that for every finite partial order, the size of the largest antichain equals the minimum number of chains into which the elements can be partitioned. In the language of graphs, this can be stated as: every finite comparability graph is perfect. Similarly, Mirsky's theorem states that for every finite partial order, the size of the largest chain equals the minimum number of antichains into which the elements can be partitioned, or that every finite incomparability graph is perfect. These two theorems are equivalent via the perfect graph theorem, but Mirsky's theorem is easier to prove directly than Dilworth's theorem: if each element is labeled by the size of the largest chain in which it is maximal, then the subsets with equal labels form a partition into antichains, with the number of antichains equal to the size of the largest chain overall. Every bipartite graph is a comparability graph. Thus, Kőnig's theorem can be seen as a special case of Dilworth's theorem, connected through the theory of perfect graphs. A permutation graph is defined from a permutation on a totally ordered sequence of elements (conventionally, the integers from to ), which form the vertices of the graph. The edges of a permutation graph connect pairs of elements whose ordering is reversed by the given permutation. These are naturally incomparability graphs, for a partial order in which whenever occurs before in both the given sequence and its permutation. The complement of a permutation graph is another permutation graph, for the reverse of the given permutation. Therefore, as well as being incomparability graphs, permutation graphs are comparability graphs. In fact, the permutation graphs are exactly the graphs that are both comparability and incomparability graphs. A clique, in a permutation graph, is a subsequence of elements that appear in increasing order in the given permutation, and an independent set is a subsequence of elements that appear in decreasing order. In any perfect graph, the product of the clique number and independence number are at least the number of vertices; the special case of this inequality for permutation graphs is the Erdős–Szekeres theorem. The interval graphs are the incomparability graphs of interval orders, orderings defined by sets of intervals on the real line with whenever interval is completely to the left of interval In the corresponding interval graph, there is an edge from to whenever the two intervals have a point in common. Coloring these graphs can be used to model problems of assigning resources to tasks (such as classrooms to classes) with intervals describing the scheduled time of each task. Both interval graphs and permutation graphs are generalized by the trapezoid graphs. Systems of intervals in which no two are nested produce a more restricted class of graphs, the indifference graphs, the incomparability graphs of semiorders. These have been used to model human preferences under the assumption that, when items have utilities that are very close to each other, they will be incomparable. Intervals where every pair is nested or disjoint produce trivially perfect graphs, the comparability graphs of ordered trees. In them, the independence number equals the number of maximal cliques.

Бөлінетін графиктер және кездейсоқ кемелді графиктер

Бөлінген график – кликаға және тәуелсіз жиынға бөлінетін график. Оны максималды кликаның әрбір төбесіне жеке түс тағайындау арқылы, содан кейін қалған әрбір төбеге кликамен қабыспайтын төбеге сәйкес түс беру арқылы бояуға болады. Сондықтан, мұндай графиктердің клика саны мен хроматикалық саны тең болады және олар толықтай кемелді. Графиктердің кеңірек класы – бірполярлы графиктерді кликаға және кластерлік графқа, яғни кликалардың біріккен жиынына бөлуге болады. Бұған екі бөлікті графиктер де жатады, онда кластерлік график тек бір клика болып табылады. Бірполярлы графиктер мен олардың толықтырулары бірге жалпыланған бөлінген графиктер класын құрайды. Көптеген толық графиктер жалпыланған бөлінген графиктер болып табылады, яғни, толық төбелік графиктердің жалпыланған бөлінген графиктер болып табылатын үлесі, g шексіз үлкен мәнге ұмтылғанда бірге жуықтасады. Көптеген толық графиктердің басқа да шектік қасиеттерін жалпыланған бөлінген графиктерді зерттеу арқылы анықтауға болады. Осылайша, көптеген толық графиктерде Гамильтон циклы бар екені көрсетілді. Егер G кездейсоқ график болса, үлкен кездейсоқ толық графиктің индукцияланған кішкентай графигі ретінде G пайда болуының шектік ықтималдығы 0, 1/2 немесе 1 болады, тиісінше, G жалпыланған бөлінген график болмаса, бірполярлы немесе ко-бірполярлы болса, бірақ екеуі де емес, немесе бірполярлы және ко-бірполярлы болса.

Үдемелі құрылыстар

Бірнеше толық графтар отбасылары белгілі бір ережелерге сәйкес, графтар бір уақытта бір төбе қосылып, графтың әр төбе қосылғаннан кейін толық болатынына кепілдік беретін инкременттік құрылыммен сипатталуы мүмкін. Хордалық графтар – бұл осы типтегі құрылым арқылы қалыптасқан графтар, онда төбе қосылған кезде оның көршілері кликаны құрайды. Хордалық графтар тесіктері жоқ (жұп немесе тақ) графтар ретінде сипатталуы мүмкін. Олардың ішінде орман, аралық графтар және максималды сыртқы жазықтық графтар ерекше жағдай болып табылады. Бөлінген графтар – дәл созысты және созысты комплементіне ие графтар. Ағаш енінің анықтамасы үшін негізгі болып табылатын k ағаштар – бұл (k + 1) төбесі бар кликадан басталып, бірнеше рет төбелерді қосу арқылы қалыптастырылған хордалық графтар, сондықтан ол және оның көршілері бірдей өлшемді клика құрайды. Алыстан мұрагерлік графтар бір төбелік графтан бастап, бір дәрежелі төбелерді ("жапырақ төбелер") немесе қолданыстағы төбелердің көшірмелерін (бірдей көршілерімен) бірнеше рет қосу арқылы қалыптастырылады. Әрбір төбе және оның көшірмесі іргелес (нағыз егіздер) немесе іргелес емес (жалған егіздер) болуы мүмкін. Осы графтардың әрбір қосылған индукциялық субграфтарында төбелер арасындағы қашықтықтар бүтін графтардағыдай болады. Егер тек егіз операциясы қолданса, онда кограф пайда болады. Кографтар – қатардағы параллельді бөлшек тәртіптердің салыстырмалылық графтары, сондай-ақ оларды графтардың толықтығын және ажыратылған біріктірілуін біріктіретін басқа құрылыс процесі арқылы да құрастыруға болады. Хордалық және арақашықтық мұрагерлік графтар Птолемейлік графтар деп аталады, өйткені олардың арақашықтықтары Птолемейдің теңсіздіктеріне бағынады. Олардың қашықтыққа байланысты мұрагерлік құрылысының шектеулі түрі бар, онда жалған егіз тек оның көршілері кликаны құраған кезде ғана қосылуы мүмкін. Олардың ішінде арнайы жағдай ретінде бір төбеден біріктірілген кликалардан тұратын жел желінің графтары және әрбір екі жақты компоненті клика болып табылатын блок графтары бар. Шекті графтар бос графтан оқшауланған төбені (басқа ештеңемен байланыспаған) немесе әмбебап төбені (барлық басқа төбелермен байланысқан) қайта-қайта қосу арқылы құрылады. Олар бөлінген графтар мен тривиалды түрде кемелді графтардың ерекше жағдайлары. Олар дәл сол графтар, олар бір уақытта тривиалды түрде кемелді және тривиалды түрде кемелді графтың толықтырғышы; олар сонымен қатар дәл сол графтар, олар кографтар және бөлінген графтар. Егер хордалық графиктің төбелері ашкөз бояу алгоритмін қолдана отырып, инкременттік құрылыс тізбегінің ретімен боялса, нәтиже оңтайлы бояу болады. Бұл құрылыста пайдаланылған төбелер ретінің керісінше жою тәртібі деп аталады. Сол сияқты, егер арақашықтық мұрагерлік графиктің төбелері инкременттік құрылыс тізбектілігі бойынша боялған болса, онда түстеудің нәтижесі оңтайлы болады. Егер салыстырмалылық графигінің төбелері оның негізгі ішінара реті бойынша сызықтық ұзарту тәртібімен боялған болса, онда түстеудің нәтижесі оңтайлы болады. Бұл қасиет толық реттелген графтар отбасында жалпыландырылады, олар үшін кез келген индукцияланған субграфикке шектелген кезде ашкөз бояудың оңтайлы болуына себеп болатын ретке келтіру бар. Кографтар – бұл барлық төбелер ретінің осы қасиетке ие графтары. Кемелді реттелген графтардың тағы бір кіші класы толеранттылық графтарының толықтырмалары болып табылады, интервалдық графтардың жалпылануы.

Several families of perfect graphs can be characterized by an incremental construction in which the graphs in the family are built up by adding one vertex at a time, according to certain rules, which guarantee that after each vertex is added the graph remains perfect. The chordal graphs are the graphs formed by a construction of this type in which, at the time a vertex is added, its neighbors form a clique. Chordal graphs may also be characterized as the graphs that have no holes (even or odd). They include as special cases the forests, the interval graphs, and the maximal outerplanar graphs. The split graphs are exactly the graphs that are chordal and have a chordal complement. The k trees, central to the definition of treewidth, are chordal graphs formed by starting with a (k + 1) vertex clique and repeatedly adding a vertex so that it and its neighbors form a clique of the same size. The distance hereditary graphs are formed, starting from a single vertex graph, by repeatedly adding degree one vertices ("pendant vertices") or copies of existing vertices (with the same neighbors). Each vertex and its copy may be adjacent (true twins) or non adjacent (false twins). In every connected induced subgraph of these graphs, the distances between vertices are the same as in the whole graph. If only the twin operations are used, the result is a cograph. The cographs are the comparability graphs of series parallel partial orders and can also be formed by a different construction process combining complementation and the disjoint union of graphs. The graphs that are both chordal and distance hereditary are called Ptolemaic graphs, because their distances obey Ptolemy's inequality. They have a restricted form of the distance hereditary construction sequence, in which a false twin can only be added when its neighbors would form a clique. They include as special cases the windmill graphs consisting of cliques joined at a single vertex, and the block graphs in which each biconnected component is a clique. The threshold graphs are formed from an empty graph by repeatedly adding either an isolated vertex (connected to nothing else) or a universal vertex (connected to all other vertices). They are special cases of the split graphs and the trivially perfect graphs. They are exactly the graphs that are both trivially perfect and the complement of a trivially perfect graph; they are also exactly the graphs that are both cographs and split graphs. If the vertices of a chordal graph are colored in the order of an incremental construction sequence using a greedy coloring algorithm, the result will be an optimal coloring. The reverse of the vertex ordering used in this construction is called an elimination order. Similarly, if the vertices of a distance hereditary graph are colored in the order of an incremental construction sequence, the resulting coloring will be optimal. If the vertices of a comparability graph are colored in the order of a linear extension of its underlying partial order, the resulting coloring will be optimal. This property is generalized in the family of perfectly orderable graphs, the graphs for which there exists an ordering that, when restricted to any induced subgraph, causes greedy coloring to be optimal. The cographs are exactly the graphs for which all vertex orderings have this property. Another subclass of perfectly orderable graphs are the complements of tolerance graphs, a generalization of interval graphs.

Қуатты кемелдік

Қатты кемелдік графтар — әрбір индукцияланған субграфта барлық максималдық кликаларды қиып өтетін тәуелсіз жиынтық болатын графтар. Мейниел графиктері немесе өте мықты кемелдік графтарда әрбір төбе осындай тәуелсіз жиынтыққа жатады. Мейниел графиктерін әрбір бес немесе одан ұзын тақ циклдің кем дегенде екі акордысы бар графтар ретінде сипаттауға болады. Паритеттік граф — кез келген екі төбе арасындағы барлық индукцияланған жолдардың тең паритеті бар деген қасиетпен анықталады: олардың барлығы жұп немесе барлығы тақ ұзындықта болады. Бұларға екі төбе арасындағы барлық индукцияланған жолдардың бірдей ұзындықта болатын арақашықтық мұрагерлік графтар және кез келген екі төбе арасындағы барлық жолдардың (тек индукцияланған жолдар емес) тең паритеті болатын екі жақты графтар жатады. Паритеттік графтар — Мейниел графтары, демек, олар кемелді: егер ұзын тақ циклде тек бір ғана акорды болса, онда акордтың соңғы нүктелері арасындағы циклдің екі бөлігі әртүрлі паритетті индукцияланған жолдар болады. Кез келген паритеттік графиктің (оның бір жиекті Картезиан көбейтіндісі) үстіндегі призма — тағы бір паритеттік граф, ал паритеттік графтар — призмалары кемелді болатын жалғыз графтар.

Матрицалар, полиэдрлер және бүтін сандарды бағдарламалау

Перфект графтары сызықтық бағдарламалау және бүтін сандық бағдарламалау теориясымен тығыз байланысты. Сызықтық бағдарламалар мен бүтін сандық бағдарламалар да сызықтық шектеулерге сәйкес сызықтық мақсатты функцияны барынша арттыратын векторды іздеу ретінде канондық түрде көрсетіледі және . Мұнда матрица ретінде, ал және екі вектор ретінде беріледі. Сызықтық бағдарламалар мен бүтін сандық бағдарламалар осылай көрсетілгенімен, олардың арасындағы айырмашылық сызықтық бағдарламада шешім векторының коэффициенттері кез келген нақты сандар болуы мүмкін, ал бүтін сандық бағдарламада бұл белгісіз коэффициенттер бүтін сандар болуы керек екендігінде. Бұл осы проблемалардың есептеу күрделілігіне елеулі әсер етеді: сызықтық бағдарламалау полиномиалдық уақытта шешіледі, бірақ бүтін сандық бағдарламалау NP-қиын. Егер бірдей , және мәндері сызықтық бағдарламаны және бүтін сандық бағдарламаны анықтау үшін қолданылса, олар әдетте әртүрлі оңтайлы шешімдерге ие болады. Егер бүтін сандық бағдарламаның оңтайлы шешімі сызықтық бағдарлама үшін де оңтайлы болса, онда сызықтық бағдарлама интегралды сызықтық бағдарлама деп аталады. (Басқа жағдайда, екі шешімнің мәндерінің арақатынасы интегралдылық алшақтық деп аталады және бүтін сандық бағдарламаның жуықтау алгоритмдерін талдау үшін маңызды.) (0, 1) матрицаларын (яғни, барлық коэффициенттері 0 немесе 1 болатын матрицаларды) сипаттау үшін перфект графтарды келесі қасиетімен қолдануға болады: егер бірліктерден тұратын вектор болса, онда барлық таңдаулары үшін алынған сызықтық бағдарлама интегралды болады. Вацлав Шватал дәлелдегендей, осы қасиетке ие әрбір матрица (қажетсіз "басымды" қатарларды алып тастағаннан кейін) перфект графтың максималды кликаға қарсы төбелік инциденттік матрицасы болып табылады. Бұл матрицада графтың әрбір төбесі үшін баған және әрбір максималды клика үшін қатар болады, коэффициенті кликаға кіретін төбелердің бағандарында 1, ал қалған бағандарда 0 болады. Бұл матрицамен кодталған интегралды сызықтық бағдарламалар берілген графтың максималды салмақты тәуелсіз жиынтығын іздейді, салмақтар векторымен беріледі. Перфект графтан осылай анықталған матрица үшін теңсіздіктер жүйесін қанағаттандыратын векторлары интегралды политопты құрайды. Бұл графтың тәуелсіз жиынтықтарының индикаторлық векторларының дөңгелек қабығы, жақтары графтың максималды кликаларына сәйкес келеді. Перфект графтар – тәуелсіз жиынтықтар мен максималды кликалар арқылы осылай анықталған екі политоптың сәйкес келетін жалғыз графтары.

Perfect graphs are closely connected to the theory of linear programming and integer programming. Both linear programs and integer programs are expressed in canonical form as seeking a vector that maximizes a linear objective function , subject to the linear constraints and Here, is given as a matrix, and and are given as two vectors. Although linear programs and integer programs are specified in this same way, they differ in that, in a linear program, the solution vector is allowed to have arbitrary real numbers as its coefficients, whereas in an integer program these unknown coefficients must be integers. This makes a very big difference in the computational complexity of these problems: linear programming can be solved in polynomial time, but integer programming is NP hard. When the same given values , , and are used to define both a linear program and an integer program, they commonly have different optimal solutions. The linear program is called an integral linear program if an optimal solution to the integer program is also optimal for the linear program. (Otherwise, the ratio between the two solution values is called the integrality gap, and is important in analyzing approximation algorithms for the integer program.) Perfect graphs may be used to characterize the (0, 1) matrices (that is, matrices where all coefficients are 0 or 1) with the following property: if is the all ones vector, then for all choices of the resulting linear program is integral. As Václav Chvátal proved, every matrix with this property is (up to removal of irrelevant "dominated" rows) the maximal clique versus vertex incidence matrix of a perfect graph. This matrix has a column for each vertex of the graph, and a row for each maximal clique, with a coefficient that is one in the columns of vertices that belong to the clique and zero in the remaining columns. The integral linear programs encoded by this matrix seek the maximum weight independent set of the given graph, with weights given by the vector
For a matrix defined in this way from a perfect graph, the vectors satisfying the system of inequalities , form an integral polytope. It is the convex hull of the indicator vectors of independent sets in the graph, with facets corresponding to the maximal cliques in the graph. The perfect graphs are the only graphs for which the two polytopes defined in this way from independent sets and from maximal cliques coincide.

Алгоритмдер

Барлық кемелді графиктерде графикті бояу мәселесі, максималды клика мәселесі және максималды тәуелсіз жиын мәселесі полиномиалдық уақытта шешіледі. Жалпы жағдай үшін алгоритм осы графиктердің Ловасс санын қолданады. Кез келген графиктің Ловасс санын оның төбелерін жоғары өлшемді бірлік векторлармен белгілеу арқылы анықтауға болады, сондықтан жақын емес екі төбеде перпендикулярлы белгілер болады және барлық векторлар мүмкіндігінше кіші ашылу бұрышы бар конуста орналасады. Содан кейін, Ловасс саны , мұндағы конустың жарты бұрышы. Осы күрделі анықтамаға қарамастан, Ловасс санын жартылай анықталған бағдарламалауды қолдану арқылы дәл сандық мәнін есептеуге болады, және кез келген график үшін Ловасс саны хроматикалық сан мен клика саны арасында жатады. Бұл екі сан бір-біріне тең болғандықтан, олар да Ловасс санына тең. Осылайша, оларды Ловасс санын жеткілікті дәлдікпен есептеу және нәтижені ең жақын бүтін санға дейін дөңгелектеу арқылы табуға болады. Бұл алгоритм қолданатын жартылай анықталған бағдарламалардың шешім әдісі сызықтық бағдарламалаудың эллипсоидтық әдісіне негізделген. Бұл кемелді графиктердегі хроматикалық сан мен клика санын есептеуге арналған полиномиалдық уақыт алгоритміне әкеледі. Дегенмен, Ловасс саны мен эллипсоидтық әдісті қолдану арқылы осы мәселелерді шешу қиын және жоғары полиномиалдық көрсеткішке ие. Көптеген ерекше жағдайларда тиімді комбинаторлық алгоритмдер белгілі. Бұл әдіс салмақтық графикте клика санының орнына кликаның ең үлкен салмағын табу үшін де жалпылауға болады. Осы әдістер арқылы ең үлкен немесе ең үлкен салмақты клика және графиктің оңтайлы бояуы табылады, ал ең үлкен тәуелсіз жиын графиктің толықтыруына бірдей тәсілмен қолдану арқылы табылады. Мысалы, максималды кликаны келесі алгоритммен табуға болады: График төбелері арқылы жүзу. Әр төбе үшін келесі қадамдарды орындаңыз: Графиктен төбені уақытша алып тастаңыз. Нәтижелі индукцияланған кішіграфтың клика санын анықтау үшін жартылай анықталған бағдарламалауды қолданыңыз. Егер бұл клика саны бүкіл граф үшін бірдей болса, төбені тұрақты түрде алып тастаңыз; әйтпесе, төбені графқа қайта қосыңыз. Барлық тұрақты алып тастаулардан кейін қалған кішіграфты қайтарыңыз. Оңтайлы бояуды табу алгоритмі күрделірек және сызықтық бағдарламалардың дуалдық теориясына байланысты, бұл клика табу алгоритмін бөлу оракулы ретінде пайдаланады. Осы мәселелерді шешуден басқа, кемелді графиктерге қатысты маңызды есептеу мәселесі – оларды тану, яғни берілген графиктің кемелді екенін тексеру мәселесі. Көп жылдар бойы Берге графтарын танудың күрделілігі мен кемелді графтарды танудың күрделілігі бөлек қарастырылды (өйткені олардың әлі де бірдей екендігі белгілі емес еді) және екеуі де ашық мәселе болып келді. Олардың екеуі де NP-ге тең екендігі белгілі болды; Берге графтары үшін бұл анықтамадан, ал кемелді графиктер үшін клика саны мен тәуелсіздік санының көбейтіндісін пайдалана отырып сипаттаудан туындайды. Күшті кемелді граф теоремасы дәлелденгеннен кейін, Чудновский, Корнуеолс, Лю, Сеймур және Вускович тақ тесіктердің немесе анти-тесіктердің болуын тексеруге арналған полиномиалдық уақыт алгоритмін тапты. Күшті кемелді граф теоремасы бойынша, бұл берілген графиктің полиномиалдық уақыт ішінде кемелді екенін тексеру үшін пайдаланылуы мүмкін.

In all perfect graphs, the graph coloring problem, maximum clique problem, and maximum independent set problem can all be solved in polynomial time. The algorithm for the general case involves the Lovász number of these graphs. The Lovász number of any graph can be determined by labeling its vertices by high dimensional unit vectors, so that each two non adjacent vertices have perpendicular labels, and so that all of the vectors lie in a cone with as small an opening angle as possible. Then, the Lovász number is , where is the half angle of this cone. Despite this complicated definition, an accurate numerical value of the Lovász number can be computed using semidefinite programming, and for any graph the Lovász number is sandwiched between the chromatic number and clique number. Because these two numbers equal each other in perfect graphs, they also equal the Lovász number. Thus, they can be computed by approximating the Lovász number accurately enough and rounding the result to the nearest integer. The solution method for semidefinite programs, used by this algorithm, is based on the ellipsoid method for linear programming. It leads to a polynomial time algorithm for computing the chromatic number and clique number in perfect graphs. However, solving these problems using the Lovász number and the ellipsoid method is complicated and has a high polynomial exponent. More efficient combinatorial algorithms are known for many special cases. This method can also be generalized to find the maximum weight of a clique, in a weighted graph, instead of the clique number. A maximum or maximum weight clique itself, and an optimal coloring of the graph, can also be found by these methods, and a maximum independent set can be found by applying the same approach to the complement of the graph. For instance, a maximum clique can be found by the following algorithm:
Loop through the vertices of the graph. For each vertex , perform the following steps:
Tentatively remove from the graph. Use semidefinite programming to determine the clique number of the resulting induced subgraph. If this clique number is the same as for the whole graph, permanently remove ; otherwise, restore to the graph. Return the subgraph that remains after all the permanent removals. The algorithm for finding an optimal coloring is more complicated, and depends on the duality theory of linear programs, using this clique finding algorithm as a separation oracle. Beyond solving these problems, another important computational problem concerning perfect graphs is their recognition, the problem of testing whether a given graph is perfect. For many years the complexity of recognizing Berge graphs and perfect graphs were considered separately (as they were not yet known to be equivalent) and both remained open. They were both known to be in co NP; for Berge graphs, this follows from the definition, while for perfect graphs it follows from the characterization using the product of the clique number and independence number. After the strong perfect graph theorem was proved, Chudnovsky, Cornuéjols, Liu, Seymour, and Vušković discovered a polynomial time algorithm for testing the existence of odd holes or anti holes. By the strong perfect graph theorem, this can be used to test whether a given graph is perfect, in polynomial time.

Қарым-қатынас ұғымдары

Кемел графиктерді жалпылағанда, егер кластағы графиктердің хроматикалық саны олардың клика санының функциясымен шектеле алса, онда бұл график класы χ-шектеулі деп аталады. Кемел графиктер – бұл функция графиктің өзі үшін де, оның барлық индукцияланған кіші графиктер үшін де сәйкестік функциясы болатын графиктер. Кемел графиктерде клика саны мен хроматикалық санның теңдігі басқа график кластарын анықтауға түрткі болды, онда басқа график инварианттары бір-біріне тең болады. Мысалы, доминациялық кемел графиктер – бұл әрбір индукцияланған кіші графикте ең кішкентай доминациялық жиынның (қалған барлық төбелерге іргелес төбелер жиыны) доминациялық жиын болатын ең кішкентай тәуелсіз жиынға тең болатын графиктер. Мұндай графиктерге, мысалы, тырнақсыз графиктер жатады.