Cтраница 1
Планарные графы играют заметную роль и в задачах раскрашивания. Предположим далее, что по экономическим причинам ни одна из компаний не желает сооружать свои станции в соседних вершинах. Тогда возможно следующее решение: Шелл строит станцию в пункте Р, Эссо - - в Q, - в S, Галф - в Т, а в R строит либо Шелл, либо Галф. Однако если Галф решит отказаться от участия в строительстве, то ясно, что три оставшиеся компании не смогут построить свои станции указанным способом. [1]
Следствие 1.7. Двойственные трехсвязные планарные графы G и G реализуются двойственными многогранниками. [2]
Подмножество графов MI объединяет все заведомо планарные графы. Действительно, граф, содержащий п - J - 2 ребер, будет всегда планарен. В худшем случае из п ребер может образоваться ГЦ, который делит плоскость на две области - внутреннюю и внешнюю. Согласно теореме Жордана в этих областях можно провести по одному ребру без пересечений. Добавление некоторого ребра к графу с ( 2) ребрами может сделать его непланарным. [3]
Из утвврвдвния I вытекает, что элементарны все 3-однородные трехсвязннв планарные графы ( т.о. графы, эсе вершины которых имеют степень три), а также графы, реалкмлощие пирамиды. [4]
Проверьте, что упомянутые выше примеры планарных графов действительно являются планарными графами. Докажите, что любой подграф планарного графа планарен, и, приняв во внимание, что К3 з не планарен, определите, какие из полных двудольных графов планарны. [5]
А В предыдущем параграфе мы дали абстрактное определение двойственности, которое характеризует планарные графы. Посвятим этот небольшой параграф еще одному определению двойственности, а именно двойственности по Уитни. Хотя это определение на первый взгляд кажется довольно искусственным, мы помещаем его здесь из исторических соображений, поскольку Уитни был первым теоретиком, обратившимся к двойственным графам для описания планарных графов. [6]
Можно выбирать тот или иной тип графов, соблюдая при этом единственное условие: и планарные графы, и 4-раскрашива-емые планарные графы должны одновременно обладать этими выбранными ( характерными для рассматриваемого типа графов) свойствами. [7]
Можно выбирать тот или иной тип графов, соблюдая при этом единственное условие: и планарные графы, и 4-раскрашива-емые планарные графы должны одновременно обладать этими выбранными ( характерными для рассматриваемого типа графов) свойствами. [8]
Пусть связный граф О имеет 1-разделение ( Н К) с точкой сочленения V, и пусть Н и К - планарные графы. Тогда граф С планарен. [9]
Это классическое приложение теории паросочетании было осуществлено Кастелейном, физиком по профессии, разработавшим так называемый пфаффианов метод для перечисления совершенных паросочетании в планарных графах. Может показаться удивительным, что и другие разделы теории паросочетании, а именно, алгебраические задачи о паросочетаниях и исследования, связанные с политопами паросочетании, тоже весьма полезны в физических приложениях. [10]
Проводим индукцию по числу вершин; для планарных графов, имеющих меньше семи вершин, результат тривиален. Предположим, что G - планарный граф с п вершинами и что все планарные графы с п - 1 вершинами 6-раскрашиваемы. Без потери общности можно считать G простым графом; тогда ( по теореме 13F) он содержит вершину v, степень которой не больше пяти. Удаляя вершину v вместе с инцидентными ей ребрами, приходим к графу с п - 1 вершинами, который 6-раскрашиваем. [11]
Татта, например, его обширную теорию перечисления планарных объектов и хроматические многочлены карт, его теорему о гамиль-тоновых циклах в четырехсвязных планарных графах, гипотезу о 5-потоке ( см. разд. Привлечение миноров создает предпосылки для исследования ( среди многих других объектов и проблем) гипотезы о полном квазиупорядочении множества графов посредством отношения быть минором ( см. замечание 1 в разд. Поиски, ведущиеся в этом направлении Сеймором и Робертсоном ( бывшим студентом проф. Татта), по-видимому, обещают интересные результаты. Некоторые из указанных ( и других) тем могут дать обширный материал для следующего тома, если профессор Татт или кто-либо, тесно связанный с ним в идейном плане, решит написать такую книгу. [12]
Всякий граф, который можно так нарисовать на плоскости, что он не будет содержать пересечений ( ребер), называется планарным графом. Планарные графы играют очень важную роль в теории графов. [13]
Доказательство теоремы ведется индукцией по числу вершин. Для любого планарного графа с и 5 вершинами результат тривиален, так как любой граф п-раскрашиваем. Допустим, что все планарные графы с п вершинами, п 5, 5-раскрашиваемы. [14]
Хотя на первый взгляд определение абстрактной двойственности кажется странным, оно удовлетворяет нашим требованиям. Мы уже видели ( теорема 15С), что планарный граф имеет абстрактно двойственный ( например, любой из геометрически двойственных); покажем теперь, что верно и обратное, а именно, что любой граф, имеющий абстрактно двойственный, планарен. Тем самым мы получим абстрактное определение двойственности, обобщающее понятие геометрической двойственности и характеризующее планарные графы. [15]