Преобразованный граф
Cтраница 2
В регулярном графе при отсутствии очевидной симметрии все вершины должны быть проверены тем же способом. Затем для каждого преобразованного графа получают линейное обозначение для матрицы смежности. Если вершины в исходном графе 13 связаны симметрией, то они будут давать идентичные линейные обозначения для преобразованных графов, приводя к трем различным классам эквивалентности. [16]
Следует отметить, что преобразование можно осуществлять не только непосредственно по графу, но и при помощи операций, выполняемых над матрицей А, которая соответствует преобразуемому графу. Подвергшаяся изменениям матрица А, будет соответствовать преобразованному графу. В настоящей книге эти операции не рассматриваются, а излагаются правила, позволяющие выполнять преобразования непосредственно по графу. [17]
Следует отметить, что преобразование можно осуществлять непосредственно по графу или при помощи операций, выполняемых над матрицей [ А ], которая отвечает преобразуемому графу. Подвергшаяся изменениям матрица [ А ] будет соответствовать преобразованному графу. В настоящей книге эти операции не рассматриваются, а излагаются правила, позволяющие проводить преобразования непосредственно по графу. [18]
В регулярном графе при отсутствии очевидной симметрии все вершины должны быть проверены тем же способом. Затем для каждого преобразованного графа получают линейное обозначение для матрицы смежности. Если вершины в исходном графе 13 связаны симметрией, то они будут давать идентичные линейные обозначения для преобразованных графов, приводя к трем различным классам эквивалентности. [19]
Заметим, что рассмотренный алгоритм применим для определения планарности мультиграфов. В этом случае вершины графа располагаются, как было предложено выше, а множество ребер графа дополняется фиктивными ребрами так, чтобы образовывался псевдогамильтонов цикл. Теперь, если в результате применения алгоритма окажется, что преобразованный граф планарен, то исходный граф будет заведомо пла-нарным, в противном случае необходимо провести дополнительные исследования. [20]
 |
Дуальные графы.| Ориентированный граф. [21] |
Более сложным преобразованием является дуализация плоского несжатого графа. Для дуализации плоский граф изображают с непересекающимися ветвями. Затем в каждой неперекрывающейся ячейке ( включая внешнюю) намечают по одному новому узлу для преобразованного графа. Например, для графа, изображенного на рис. 2.27, е, такие новые узлы а, б, в, г, показаны на рис. 2.30, а. Далее каждое ребро исходного графа пересекают новым ребром, соединяя им новые узлы в смежных ячейках, как показано цветными линиями на рис. 2.30, а. При этом образуется новый граф, который перечерчен на рис. 2.30, б в более удобном виде. [22]
Страницы: 1 2