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

Cтраница 1

Двойственный граф был бы полным обыкновенным графом из пяти вершин, который не является плоским. [1]

Построить двойственный граф для двойственного графа, изображенного на рис. 4.7, показать, что полученный двойственный граф эквивалентен исходному. [2]

В двойственном графе это означает, что существует, по крайней мере, одна грань, ограниченная самое большее пятью ребрами, так что существует грань, ограниченная точно двумя или четырьмя ребрами. Пусть в случае двухре-берной границы R и R2 будут грани, смежные с рассматриваемой. Если мы удалим одно из двух ограничивающих ребер, удалив тем самым рассматриваемую грань, и устраним вершины степени 2, заменяя их ребра одним ребром, которое инцидентно смежным вершинам, то согласно индуктивному предположению ( индукция по числу граней) полученную карту можно окрасить тремя цветами. Нетрудно показать, что все получившиеся грани имеют четное число ребер и что полученная карта все еще является однородной степени 3 с числом граней, уменьшенным на два. Первоначально грань R имела четное число соседних граней, учитывая R. R, должно быть попеременно назначено два цвета. После возвращения двух удаленных ребер грань R может быть окрашена третьим, оставшимся цветом. [3]

Поня тие двойственного графа позволяет дать другое определение плоского графа. Оно оказывается также полезным при изучении задачи раскраски. [4]

Та часть двойственного графа, которая не вошла в максимальное дерево, не может развалиться на отдельные куски, ибо это означало бы, что наше дерево полностью окружило какую-то часть двойственного графа, а тогда оно должно было бы содержать цикл. [5]

Различные геометрически двойственные графы к одному и тому же. [6]

Другими примерами геометрически двойственных графов являются Платоновы графы: тетраэдр - самодвойственный граф, куб и октаэдр - двойственные, так же как додекаэдр и икосаэдр. [7]

Для нашего примера двойственный граф нарисован двойными линиями. [8]

Комбинаторно двойственные графы. [9]

В отличие от геометрически двойственных графов комбинаторно двойственные графы планарных графов определяются не обязательно однозначно. Соответствие хг - / г для графовG и Я, представленных на рис. 11.14, поясняет это утверждение. [10]

Уитни дал комбинаторное определение двойственного графа, которое является абстрактной формулировкой геометрически двойственного графа. [11]

Построить двойственный граф для двойственного графа, изображенного на рис. 4.7, показать, что полученный двойственный граф эквивалентен исходному. [12]

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

На рис. 4.7 показана идея построения двойственного графа, изображенного пунктирными линиями. [14]

Далее устанавливаем, что если G обладает абстрактно двойственным графом, a G гомеоморфен G, то G также обладает абстрактно двойственным графом. [15]

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