Двойственный граф

Cтраница 3

Граф, двойственный триангуляционному графу ( плоской триангуляции), является 2-связным, плоским и однородным степени 3; верно и обратное. Правильная 3-цветная раскраска ребер соответствует в терминах двойственного графа такой 3-цветной раскраске ребер плоской триангуляции, при которой три ребра, ограничивающие любую грань, будут иметь разные цвета. [31]

Как следует из определения, геометрически двойственный граф плоского графа G также плоский, а двойственный к двойственному графу графа G - это первоначальный граф G. Однако абстрактный граф, допускающий более чем одну укладку на сфере, может дать более чем один двойственный граф. [32]

В этой главе приведены все известные критерии планарности. В их число входят теоремы Понтрягина - Куратовского и Вагнера, в которых пленарные графы характеризуются в терминах запрещенных подграфов; результат Уитни о связи планарности графа с существованием комбинаторно двойственного графа; данное Мак-Лейном описание планарности, в котором используется циклическая структура графа. [33]

Соблазнительно было бы сказать, что области из Р образуют разбиение внутренности многоугольника Р, но мы не можем так сказать, так как мы пока не знаем, имеет ли многоугольник Р внутренность. Однако, учитывая, каким образом были получены области из Р, мы знаем, что их можно склеить вместе по горизонтальным сторонам, определяющим пары видимости, таким образом, что получившаяся область будет топологически эквивалентна кругу. Алгоритм вычисления пар видимости легко модифицировать так, чтобы он выполнял такое склеивание, или, более правильно, порождал двойственный граф склеенной области, в котором области представляются вершинами, и вершины, соответствующие областям, разделяемым горизонтальной стороной, определяющей пару видимости, соединяются ребром. [34]

Это позволяет естественным образом установить соответствие между точками границы многоугольника дР и точками окружности С. Для; каждой ВС - или СС-пары видимости в Р, порождаемой алгоритмом вычисления пар видимости, соединим соответствующие точки некоторой кривой, лежащей внутри окружности С. Кривые будем проводить таким образом, чтобы они нигде не пересекались, за исключением концевых точек. Двойственный граф областей, входящих в Р, дает естественный и конструктивный способ реализации этой операции. Обрабатывая вершину двойственного графа, степень которой равна единице, мы должны провести кривую между двумя точками, лежащими на С. Эта кривая разбивает круг на две части, одна из которых может быть исключена из рассмотрения на последующих этапах построения отображения. Таким образом, полное построение требуемой совокупности кривых может быть осуществлено в результате последовательной обработки с удалением вершин двойственного графа, имеющих степень, равную единице, выполняемой до тех пор, пока двойственный граф не станет пустым. [35]

Двойственный граф Г разрешения приводимой кривой. [36]

Одна из возможностей уменьшить множество, где отображение П неинъективно, состоит в редуцировании градуированного пространства Y следующим образом. Связные компоненты дополнения Х Х, не содержащие начальный дивизор 1 разрешения, - это некоторые тупиковые дуги двойственного графа Г разрешения с соответствующими конечными вершинами S. [37]

Непланарность графа Петерсена. [39]

Вслед за классическим результатом Понтрягина и Куратовского были предложены другие критерии планарности. Плоский чая внешнюю) по одной вершине графа G и, граф и геометрически если две области имеют общее ребро х, сое-двойственный к нему. В результате всегда получится плоский псевдограф, как, например, на рис. 11.13, где ребра графа G указаны сплошными линиями, а ребра двойственного графа G - штриховыми. Ясно, что G имеет петлю тогда и только тогда, когда в G есть концевая вершина; G имеет кратные ребра тогда и только тогда, когда две области графа G содержат по крайней мере два общих ребра. [40]

Страницы: 1 2 3