Cтраница 3
КГ: Каждый планарный граф 4-раскрашиваем. Число пленарных графов равно числу 4-раскрашиваемых пленарных графов. [31]
Сечение представляет собой линию для планарного графа или замкнутую поверхность для объемного графа, которая делит граф на две части. Под пленарным графом понимается такой граф, при изображении которого на плоскости ребра не пересекаются. Объемный граф удовлетворяет последнему условию лишь при его представлении в трехмерной системе координат. [32]
На плоскости заданы п точек. Требуется построить пленарный граф с вершинами в заданных точках, такой, что каждая грань внутри выпуклой оболочки является треугольником. [33]
В силу следствия 2 из теоремы 11 в графе G найдется вершина v степени пять или менее. По индуктивному предположению пленарный граф Gv 5-раскрашиваем. [34]
За последние десять лет произошел большой прогресс в области отыскания эффективных алгоритмов проверки планарности. Наиболее ранняя характеризация пленарных графов принадлежит Куратовскому ( 1930 г.), который изложил ее в терминах двух запрещенных подграфов ( см. упр. [35]
Итак, используя индукцию, заключаем, что теорема справедлива в связном случае. Рассмотрим теперь произвольный подграф Н произвольного пленарного графа О. Каждая компонента подграфа Н является подграфом какой-то компоненты графа С и каждая компонента графа С планарна. Следовательно, каждая компонента подграфа Я планарна в силу только что полученного результата. [36]
КГ: Каждый планарный граф 4-раскрашиваем. Число пленарных графов равно числу 4-раскрашиваемых пленарных графов. [37]
Трудности, возникающие при перечислении пленарных графов, интуитивно объясняются родством этих задач с проблемой четырех красок. Если будут найдены производящие функции для числа пленарных графов и пленарных 4-хроматических графов и будет установлено равенство, то тем самым будет доказано предположение о четырех красках. С другой стороны, если будет показано, что эти числа не совпадают, то предположение о четырех красках будет опровергнуто. [38]
Как мы вскоре увидим, графы / С5 и / Сз з играют исключительную роль при характеризации планарности графов. Приведенные выше следствия очень полезны в исследовании пленарных графов, в особенности максимальных планарных графов. [39]
Заметим, что при такой процедуре удаления ребер из РСДС не все ребра, попавшие внутрь выпуклой оболочки, могут быть удалены. Однако неудаленные ( таким образом) ребра образуют пленарный граф с множеством вершин V, которые сами являются внутренними точками выпуклой оболочки. Поэтому, число неудаленных ребер пропорционально V, и полный объем памяти, занимаемой РСДС, остается пропорциональным S. Отметим, что граф с множеством вершин V не связан с графом выпуклой оболочки. [40]
Эти неопределенности беспокоят нас только в случае разделимых и 2-разделимых графов. Позже мы докажем теорему Уитни, согласно которой каждый трехсвязный пленарный граф имеет только одну планарную сеть. [41]
Двойственные графы, соответствующие различным укладкам пленарного графа на плоскости, могут не быть изоморфными, но все они имеют много общих свойств. Существует естественное взаимно однозначное соответствие между ребрами любых двух графов, являющихся двойственными для одного и того же графа; оно отображает циклы на циклы и леса на леса. Общим у этих двух графов является система тех подмножеств ребер, которые образуют леса. Уитни заметил, что эти подмножества как раз и являются зависимыми множествами соответствующего матроида. Так получаемые матроиды обычно называют графическими. Мы видим, что матроиды можно толковать как некие обобщения графов. Одна из привлекательных черт этого обобщения состоит в том, что двойственный образ матроида можно определить, обобщая двойственность для пленарных графов. Матроид, двойственный матроиду, соответствующему непланарному графу, не может быть построен из графа. Это обстоятельство показывает полезность введения данного, более общего, понятия. [42]
Наша основная стратегия состоит прежде всего в том, чтобы в графе С найти цикл С, разместить С на плоскости в виде простой замкнутой кривой, разложить оставшуюся часть С - С на непересекающиеся по ребрам пути и затем попытаться разместить каждый из этих путей либо целиком внутри С, либо целиком вне С. Если нам удалось разместить так весь граф С, то он планарен, в противном случае он непланарен. Трудность этого способа заключается в том, что при размещении путей можно выбирать либо внутренность, либо внешность С, и мы должны обеспечить, чтобы неправильный выбор области размещения на ранней стадии не устранял возможности размещения последующих путей, это могло бы привести нас к неверному заключению, что пленарный граф непланарен. [43]
Эти и другие топологические инварианты вполне могут оказаться наиболее неподатливыми из всех инвариантов, имеющих какое-либо отношение к задачам перечисления. Толщина 9 есть наименьшее число пленарных подграфов, объединение которых совпадает с графом G. Крупность - это наибольшее число реберно-непересекающихся не-планарных подграфов, объединение которых равно G. Если G - пленарный граф, то у ( G) v ( G) 0, 9 ( G) 1 и ( G) не определено. Существует много других топологических инвариантов, относящихся к графам, но все они настолько же непригодны для целей перечисления графов, как и приведенные выше четыре инварианта. [44]
Двойственные графы, соответствующие различным укладкам пленарного графа на плоскости, могут не быть изоморфными, но все они имеют много общих свойств. Существует естественное взаимно однозначное соответствие между ребрами любых двух графов, являющихся двойственными для одного и того же графа; оно отображает циклы на циклы и леса на леса. Общим у этих двух графов является система тех подмножеств ребер, которые образуют леса. Уитни заметил, что эти подмножества как раз и являются зависимыми множествами соответствующего матроида. Так получаемые матроиды обычно называют графическими. Мы видим, что матроиды можно толковать как некие обобщения графов. Одна из привлекательных черт этого обобщения состоит в том, что двойственный образ матроида можно определить, обобщая двойственность для пленарных графов. Матроид, двойственный матроиду, соответствующему непланарному графу, не может быть построен из графа. Это обстоятельство показывает полезность введения данного, более общего, понятия. [45]