Дуальный граф
Cтраница 1
 |
Кубический граф. [1] |
Дуальный граф - это многоугольный граф, узловым точкам которого соответствуют окна первоначального графа, а окнам соответствуют узлы первоначального графа. [2]
При построении дуального графа каждый двухполюсный элемент ( е, J, r, L, С) следует рассматривать как отдельную ветвь. [3]
В каждой ветви дуального графа пунктиром изображен сротвототвуюший дуальный элемент. [4]
С практической точки зрения дуальный граф приводит к альтернативному решению задачи определения числа степеней свободы в трехмерной структуре многогранника, а именно задача определения ранга системы линейных уравнений может быть заменена задачей определения степени сливаемости графа. Более того, конкретная последовательность слияний соответствует последовательности шагов, которые может сделать человек, раскрывая трехмерную структуру посредством цепного процесса. Это само по себе может привести к полезным догадкам, поскольку это демонстрирует шаги процесса, а не прячет их в одном глобальном процессе типа обращения матрицы. [5]
Конуэй анализирует кол с помощью дуального графа карты ( рис. 29), определяя то, что он называет взрывными вершинами, и помечая их вспышками молний. Разумеется, в кол можно играть, раскрашивая области не обязательно в белый и черный цвета, а в любые два цвета. By сообщает, что в множестве всех топологически различных связных карт одной области, разделенной на 5 подобластей, в 9 случаях выигрывает игрок, делающий первый ход, и в 21 случае-игрок, делающий второй ход. В общем случае игра в кол неразрешима. [6]
 |
Построение по исходному графу ( а дуального графа ( б. [7] |
В теории схем используют также понятие дуального графа ( или схемы), в котором вершины соответствуют ячейкам исходного графа, а ветви заменяют дуальными ветвями. Для получения дуального графа необходимо внутри каждой ячейки и во внешней области обозначить вершины и соединить их ветвями так, чтобы каждая из них пересекала одну ветвь исходного графа - Множество построенных таким образом вершин и ветвей и образует дуальный граф, причем дуальными ветвями являются пересекающиеся ветви. [8]
Любому дереву исходного графа соответствуют ветви связи дерева дуального графа и наоборот. [9]
Ветвям контура ( сечения) исходного графа соответствуют ветви сечения ( контура) дуального графа. [10]
На рис. 2.23 приведен пример схемы электрической цепи и штриховыми линиями показано построение дуального графа этой схемы. [11]
Если в некотором графе число контуров равно числу ветвей дерева: д к, то дуальный граф имеет такую же структуру, как исходный. [12]
Сформулированное правило иллюстрируется рис. 2.20. Исходный граф показан на рис. 2.20, а; штриховые линии соответствуют построению дуального графа. На рис. 2.20, б изображен дуальный граф. [13]
Граф является дуальным исходному, если имеется взаимно однозначное соответствие ребер графов и взаимно однозначное соответствие контуров исходного графа вершинам дуального графа, и наоборот. [15]
Страницы: 1 2 3