Cтраница 2
При решении задачи вручную не следует переходить к двойственному графу. Номера Ni пишутся на гранях графа. [16]
Поставим в соответствие каждому ребру исходного графа то ребро двойственного графа, с которым оно пересекается. [17]
Для плоских графов задача перечисления разрезов эквивалентна задаче перечисления циклов двойственного графа. [18]
Уитни дал комбинаторное определение двойственного графа, которое является абстрактной формулировкой геометрически двойственного графа. [19]
Покажите, что для бинарных матроидов определение двойственного матроида обобщает определение алгебраически двойственного графа ( которое дано в упр. [20]
Заметим, что ( как указывалось ранее) планарный граф может иметь несколько различных двойственных графов, тогда как матроид имеет только один двойственный матроид. Это объясняется тем, что, как легко проверить, если G и 0х - два ( возможно, неизоморфных) двойственных графа для G, то циклические матроиды для G и Gx изоморфны. [21]
Как было замечено выше, достаточно доказать, что если граф G обладает абстрактно двойственным графом G, то G планарен. Доказательство проводится в четыре этапа. [22]
Построить двойственный граф для двойственного графа, изображенного на рис. 4.7, показать, что полученный двойственный граф эквивалентен исходному. [23]
Отметим, что при использовании Li-метрики диаграмма Вороного не является однозначной, и как следствие ее двойственный граф не является триангуляцией Делоне. Триангуляция Делоне - это ( единственная) триангуляция, такая, что окружность, описанная вокруг каждого треугольника, не содержит внутри ни одной другой точки. Таким образом, для построения триангуляции Делоне в случае Li-метрики мы не можем воспользоваться диаграммой Вороного и требуется прямой метод. [24]
Как следует из определения, геометрически двойственный граф плоского графа G также плоский, а двойственный к двойственному графу графа G - это первоначальный граф G. Однако абстрактный граф, допускающий более чем одну укладку на сфере, может дать более чем один двойственный граф. [25]
Допустим, что М - максимальное двойственное дерево, а С - остальная, не вошедшая в него часть двойственного графа. [26]
Далее устанавливаем, что если G обладает абстрактно двойственным графом, a G гомеоморфен G, то G также обладает абстрактно двойственным графом. [27]
Однако поскольку трехсвязный граф допускает только одну укладку на сфере, как отмечено в теореме 11.5, то у него должен быть единственный геометрически двойственный граф. [28]
В силу взаимно однозначного соответствия между ребрами исходного графа и двойственного к нему графа любая игра Шен нона на исходном графе порождает такую игру Шеннона на двойственном графе, что если Закоротить выигрывает исхоД - ную игру, то Вырубить выигрывает двойственную игру, и наоборот. [29]
Та часть двойственного графа, которая не вошла в максимальное дерево, не может развалиться на отдельные куски, ибо это означало бы, что наше дерево полностью окружило какую-то часть двойственного графа, а тогда оно должно было бы содержать цикл. [30]