Дуальный граф
Cтраница 2
Строим граф цепи ( рис. 2.83 р), намечаем новые узлы а, б1, в, г и пунктирными линиями строим дуальный граф. [16]
В теории схем используют также понятие дуального графа ( или схемы), в котором вершины соответствуют ячейкам исходного графа, а ветви заменяют дуальными ветвями. Для получения дуального графа необходимо внутри каждой ячейки и во внешней области обозначить вершины и соединить их ветвями так, чтобы каждая из них пересекала одну ветвь исходного графа - Множество построенных таким образом вершин и ветвей и образует дуальный граф, причем дуальными ветвями являются пересекающиеся ветви. [17]
Сформулированное правило иллюстрируется рис. 2.20. Исходный граф показан на рис. 2.20, а; штриховые линии соответствуют построению дуального графа. На рис. 2.20, б изображен дуальный граф. [18]
Дуализации могут подвергаться также сжатые плоские графы. При этом происходит взаимное преобразование узлов и контуров дуальных графов. [19]
Исходные и дуальные графы механических цепей очень удобны при рассмотрении динамических аналогий между механическими и электрическими цепями ( см. том 1 гл. При использовании аналогии сила - напряжение конфигурация электрической цепи определяется конфигурацией дуального графа, а ее контурные переменные аналогичны кинематическим переменным узлов механической цепи. При использовании аналогии сила - ток конфигурация электрической цепи имеет конфигурацию исходного графа, но узловые переменные электрической цепи аналогичны кинематическим переменным узлов механической цепи. В табл. 2 приведены величины - аналоги для упомянутых аналогий. [20]
Порядок вычисления рангов вершин ППГ, определяющих функциональную значимость элемента ХТС, остается прежним, только в формулу (7.35) вместо / i - / p) нужно подставить Wt / W. Когда необходимо одновременно определять значимость элементов ХТС и значимость технологических связей, строят вспомогательный дуальный граф, дуально отображая множество вершин ППГ во множестве ребер. Значимость элемента ХТС в этом случае определяют и оценивают его принадлежностью к множеству сочленения дуального графа. [21]
На основе пунктов 2 и 3 определяем граф, дуальный графу заданной цепи. В каждой внутренней ячейке исходного графа ( рис. 3.10 6) наносим независимый узел и во внешнем контуре - опорный или базисный узел дуального графа. [22]
Читатель, видимо, уже заметил, что некоторые методы, обсуждавшиеся в этой главе, в конце концов приводят к некоторому виду комбинаторного поиска. Грамматический разбор представляет собой существенно поисковый процесс; процедура разметки линий использует дерево поиска; и, хотя мы не показали это ясно, метод дуальных графов, анализирующий степени свободы в трехмерной структуре трехгранного тела, также связан с процессом поиска. Задачи комбинаторного поиска такого рода часто возникают в области искусственного интеллекта, и были исследованы общие методы для их эффективного решения. [23]
В теории схем используют также понятие дуального графа ( или схемы), в котором вершины соответствуют ячейкам исходного графа, а ветви заменяют дуальными ветвями. Для получения дуального графа необходимо внутри каждой ячейки и во внешней области обозначить вершины и соединить их ветвями так, чтобы каждая из них пересекала одну ветвь исходного графа - Множество построенных таким образом вершин и ветвей и образует дуальный граф, причем дуальными ветвями являются пересекающиеся ветви. [24]
Интерпретация ограничена картинками трехгранных тел, но представляет интерес, поскольку она уточняет расплывчатое понятие сцепления одной грани многогранника с другой. Интерпретация основана на использовании определенного вида дуального графа изображения многогранника. Однако, если две плоскости связаны более чем одним ребром ( которые все обязательно, коллинеарны), между соответствующими узлами помещается только одна дуга. [25]
Порядок вычисления рангов вершин ППГ, определяющих функциональную значимость элемента ХТС, остается прежним, только в формулу (7.35) вместо / i - / p) нужно подставить Wt / W. Когда необходимо одновременно определять значимость элементов ХТС и значимость технологических связей, строят вспомогательный дуальный граф, дуально отображая множество вершин ППГ во множестве ребер. Значимость элемента ХТС в этом случае определяют и оценивают его принадлежностью к множеству сочленения дуального графа. [26]
Простые эвристические правила, которые мы обсуждали, для объединения областей картинки в объекты были придуманы Гузманом ( 1968); он развил эти простые методы до высокой степени совершенства и построил алгоритм, способный анализировать идеальные картинки, достаточно сложные, чтобы вызвать по крайней мере кратковременное замешательство у человека. Брайс и Феннема ( 1970) включили простую версию этих правил в программу, использующую области в качестве основного вида данных на протяжении всего анализа сцены. Определение трехмерной структуры по расширенной монокулярной информации было исследовано Фальком ( 1970), который разработал метод дуальных графов для определения количества необходимой дополнительной информации. В неопубликованном отчете Хорна ( 1968) обсуждается использование данных фокусировки для определения информации о дальности. [27]
 |
Механическая цепь ( а и ее граф, представленный в двух конфигурациях ( б и в. [28] |
Сечением называют такое множество ребер связного графа, удаление которого Делит исходный граф на два изолированных подграфа. Следовательно, сечение представляет собой разделение вершин графа. Однако могут быть и такие сечения, которые нельзя показать, не придав графу другой конфигурации. Важными являются также понятия неразделимых, пленарных и дуальных графов. Граф называют неразделимым, если каждый подграф графа имеет минимум две вершины, общие с его дополнением. Неразделимый граф соответствует неразделимой цепи. [29]
Ненаправленный граф представляет собой топологическое изображение самой электрической схемы. Узлы и ветви этого графа соответствуют ее узлам и ветвям. В ненаправленных графах в отличие от направленных стрелок на ветвях не ставят. Свойства ветвей характеризуют их проводимости. Поскольку каждой пленарной электрической цепи может быть сопоставлена некоторая дуальная ей цепь, то каждому ненаправленному графу может соответствовать дуальный граф. [30]
Страницы: 1 2 3