Cтраница 2
Теперь мы приходим к другому очень полезному результату о структуре r - критических графов. Андрашфаи ( 1967) доказал, что любые два смежных ребра r - критического графа содержатся в нечетном цикле, а Байнеке, Харари и Пламмер ( 1967) установили, что любые два смежных ребра т-критического графа содержатся в цикле без хорд. Следующая теорема Бержа ( 1972) дает естественное обобщение этих двух результатов. [16]
Холла будут представлены ( или упомянуты) различные доказательства, в которых используются метод критических графов, индукция по размерам графов, техника чередующихся цепей и ( см. гл. Такие средства доказательства окажутся полезными в различных разделах общей теории паросочетаний ( а не только при рассмотрении двудольных графов) и, следовательно, они заслуживают достойного места в арсенале исследователя. Ряд других приемов доказательства этих теорем - например, использование теорем двойственности линейного программирования и теории определителей - будут рассмотрены в гл. [17]
Во введении к этой главе мы говорили, что полного описания структуры r - критических графов не существует. Однако эти графы имеют ряд важных структурных свойств, которые приводят к интересным следствиям для числа вершинного покрытия и в случае графов общего вида. [18]
Его значение состоит в том, что оно предлагает меру сложности для r - критических графов. [19]
Каждый граф в таблице Берра может служить основой и для игры, и для задачи Рамсея, хотя найти критическую раскраску для критического графа ( т.е. решить задачу Рамсея) оказалось гораздо легче, чем найти критическую раскраску для классического числа Рамсея. [20]
Доказательство теоремы 5.5.24. Сначала заметим, что если р 1 ( G) - нечетное число, то на основании теоремы Галлаи - Эдмондса граф G, будучи вершинно транзитивным, является критическим графом. [21]
Мы видели, что А: - хроматический граф содержит конечный подграф с тем же хроматическим числом. Следовательно, каждый А-хроматиче-ский граф содержит конечный критический граф с тем же хроматическим числом. [22]
Во многих случаях при построении алгоритмов проектирования приходится удалять некоторые вершины и ребра графа. Это приводит к необходимости использования понятия критического графа. [23]
Таким образом, б1 1 - особая точка, и можно полагать, что представляющее интерес поведение графов вблизи этой точки сложно и трудно поддается исследованию. Действительно, не очень много известно о свойствах критических графов. Здесь приводится только одно утверждение о предельном поведении таких графов. [24]
Теперь мы приходим к другому очень полезному результату о структуре r - критических графов. Андрашфаи ( 1967) доказал, что любые два смежных ребра r - критического графа содержатся в нечетном цикле, а Байнеке, Харари и Пламмер ( 1967) установили, что любые два смежных ребра т-критического графа содержатся в цикле без хорд. Следующая теорема Бержа ( 1972) дает естественное обобщение этих двух результатов. [25]
Доказательства этих результатов чрезвычайно просты и мы предлагаем их провести читателю. Заметим, что из леммы 12.1.2 следует, что пересечение всех наименьших вершинных покрытий и пересечение всех наибольших независимых множеств в r - критическом графе являются пустыми. [26]
Связный граф G называется А-угольно-критическим, если в нем нет совершенных 2-паросочетаний, не содержащих А - угольников, но для каждой вершины v 6 V ( G) граф G - v имеет совершенное 2-паросочетание, не содержащее А - угольников. Очевидно, что Z - угольно-критические графы являются факторно-критическими. Одновершинный граф есть 0-угольно-критический и других 0-уголь-но - критических графов не существует. [27]
Здесь мы рассматриваем работы, в которых исследуется взаимосвязь между разными свойствами одного и того же графа. Заметим еще, что объектами многочисленных исследований были и остаются всевозможные критические графы: например, критический хроматический граф в ряде работ определяется как такой, что удаление из него хотя бы одной вершины приводит к уменьшению хроматического числа; максимально насыщенный граф имеет наибольшее возможное число ребер при данном количестве вершин и данной плотности. Келли и других авторов, специально посвященные строению критических графов, опубликованы до 1962 года, а некоторые работы, напротив, выходят только в 1963 году. Но и во многих работах 1962 года ( и предшествующих им), для которых изучение критических графов не является основной целью, такое изучение вместе с соответствующими построениями оказывается необходимым при выводе различных оценок, а особенно при доказательстве достижимости этих оценок. В дальнейшем мы не будем специально подчеркивать роль критических графов. [28]
Вследствие NP-полноты задачи о нахождении величины r ( G) мы не можем надеяться, что r - критические графы имеют действительно простое строение. Мы представим эти результаты при обзоре теории r - критических графов в разд. [29]
Граф называется критическим, если удаление любой из его вершин ( вместе с инцидентными ей ребрами) приводит к графу с меньшим хроматическим числом. Покажите, что ( i) / Cn является критическим для всех п; ( ii) Сп является критическим тогда и только тогда, когда п нечетно. Покажите также, что если п нечетно, то соединение Сп Сп является критическим графом, хроматическое число которого равно шести. [30]