Л1-Савельев, Овчинников - Конструирование ЭВМ и систем - 1984 год (999411), страница 34
Текст из файла (страница 34)
ИЗОМОРФИЗЗА И ПЛАНАРНОСТЬ ГРАФОВ Изоморфизм и изоморфиое вложение графов. В общем случае графы 6 = (Х, (») и Н = (У, ]») будут изоморфными, если существует взаимно однозначное соответствие Х г, (» ]», такое, что при соответствии вершин х», х» Е Х вершинам уд, у, ~ 'г для всех ребер, соединяющих вершины хь х», существуют ребра такого же типа, соединяющие вер- зз в е, шины уы у», или: (1уи, (х;, х») с (») (и о„(уд, у~) с ]») л, "' в, (х; — = у, й х» = у~), л» "4 где (» — множество ребер, связывающих Рас. 8.9. Изоморфяне смех; и х,; 1» — множество ребер, связы- шзнние иультвтрзфы вающих уз и уь Другими словами, графы будут изоморфны, если один может быть получен из другого простой переиндексацией вершин и соединяющих их ребер.
Отметим, что отношение изоморфизма является отношением эквивалентности. На рис. 8.9 показаны два изоморфных смешанных мультиграфа. Соответствие вершин Х и»' устанавливается подстановкой ]'х, хз хз хз хз') Уз Уз Уз Уз Уз Распознавание изоморфизма графов — достаточно сложная задача. Существует следующая теорема об изоморфизме двух ориентированных графов: для того чтобы граф 6 был изоморфен графу Н, необходимо и достаточно выполнение следующих условий: а) (Ъ'х1 Е:— Х) (Ву» Е у) ((в (х;) = в (у»)) а (Р (х») = »» (у»))]; б) существует подстановка» Е Т, такая, что 6 переводит в Н.
Здесь в, р — полустепени исхода и захода; Т вЂ” симметрическая группа подстаиовок множества элементов, которая ставит во взаимно однозначное соответствие каждому элементу х; ~ Х графа 6 элемент у» Е ]' графа Н, такой, что в (х;) =- в (у») и р (х») = р (у»). Граф 6 изоморфно вкладывается в граф Н, если 6 изоморфен какому-либо суграфу или подграфу Н' с= Н. Граф 6 (рис. 8.10, а) изоморфно вкладывается в граф Н (рис. 8.10, б), так как 6 изоморфеи подграфу Н' с: — Н, показанному на рис. 8.10, в.
163 Соответствующая подстановка имеет вид Х» Хз Хз Х« Х» (,Уз У« У» Уз У«,) Планарность графов. Связанный неориеитированный граф называется планарным, если он изоморфен плоскому графу, т.е. может быть изображен на плоскости таким образом, что его ребра пересекаются только в вершинах.
Планарность графа не изменяется при удалении петель и кратных ребер, при разбиении ребер посредством вве- а) х а7 з с х х» х» х» з» Р3 Рнс. 8.10. К и»аморфному вложению графов где ((7~ = т, !Х! = и. Верхнюю оценку числа ребер, при котором возможна планариость графа, имеющего гамильтонов цикл, получим из следующих рассуждений: внутри и вне гамильтонова цикла можно провести без пересечения ие более (п — 3) ребер, и ребер включает сам цикл, тогда т = и + 2 (и — 3) == 3 (и — 2), (8.8) т. е.
если т - 3 (и — 2) — граф непланарный. Для определения планарности графа, число ребер которого лежит в пределах и + 2( т ( 3 (и — 2), можно использовать критерий Понтрягина — Ку- 164 дения новой вершины или стягивания в одно ребер, иицидентных вершине х; с Х с локальной степенью р (х;) =- 2, путем удаления этой вершины. Графы, которые можно получать один из другого применением операции разбиения или стягивания ребер, называют изоморфными с точностью до вершин степени «2» а) ' г) в) (рис. 8.11, а).
Перед определением планарности графа целесообразно выполнить над ними следующие преобразования: Рнс. 8.11, Графы и»аморфные УДалить петли и кратные Ребра; стЯ- с точностью до вершин степени путь ребра, инцидентные вершинам «2» (а) н неплзнзрные (б, в) с р (х,) = 2; разбить граф на компоненты связности путем удаления ребер перешейков и разделения в расщепляющихся вершинах. Теперь задача определения планариости графа и его плоского изображения сводится к исследованию каждой компоненты связности в отдельности. Граф без кратных ребер планарен, если т(п+2, (8.7) ратовского: граф плаиарен, если он не содержит подграфов, изоморф.
ных с точностью до вершин степени «2» графам 6, (полный пятивершинный, рис. 8.11, б) и 6,, (однородный двудольный степени «3», рис. 8.11, в). Однако применение этого критерия требует большого перебора и на его основе нельзя сформулировать правила построения плоского графа. Определение планарности графа и поиск его плоской реализации может быть сделан методом Бадера. Над исходным графом 6 = = (Х, (7) выполняются указанные выше преобразова- в хе х и Вз ния. Определяется гамиль- а) тонов цикл каждого подграфа 6; = (Хо (7,). Ребра, не вошедшие н гамильтонов цикл„помещают в его внутреннюю или внешнюю область и строят для иих граф пересечений Н =- (г, )г).
Вершины у» ~ У этого графа сопоставляются пе- хи ресекающимся ребрам исследуемого подграфа. Реб- Рнс. 8.12. Плзнзйный Рзф (а) н плоские иво- р»женин лодгрзфон 1 (б), ~з ( ) н» () у,, если соответствующие им ребра подграфа 6; пе- о) х»»)ф "о)х )в|еду»(зн] ресекаются. Исследуется, з является ли граф Н дву- » „, з дольным, если да, то граф ~" се 6; планарен. Вершины тра- ' х, в»1«з) в»1«е)ь',1«) г«(зхф) «1«з) фа пересечений Н разби- хв ваются на два подмиожестРнс.
8.18. Преобразование иод»рафа бз (а) н граф пересечений его ребер (б) ребра графа 6; разделяются на два подмножества непересекающихся ребер, одно из которых помещается во внутреннюю область гамильтонова цикла, другое— во внешнюю.
На рис. 8.12, а показан граф 6 = (Х, (7), который после удаления ребер, соединяющих вершины х, и х„и расщепления в вершине х, разделяется иа три подграфа 6ы 6м 6,. Плоская реализация подграфа 6, очевидна (рис. 8.12, б). В подграфе 6» гамильтонов цикл проходит через вершины х„х«,х„х„х«, х„х„х,е, хз. Удалив петли и кратные ребра, поместим оставшиеся ребра подграфа 6» во внутреннюю область гамильтонова цикла (рис. 8.13, а). Граф пересечений ребер подграфа 6» показан на рис. 8.13, б. Нетрудно убедиться, что он двудольный. Плоское изображение подграфа показано на рис.
8.12, в. В подграфе 6, гамильтонов цикл проходит через вершины хыо хм, хим хиы х,«, хм, х„. После его представления в виде самонепересекающейся кривой плоское изображение подграфа 6» получим,поместив одно из ребер (хыо х„), (хыо хм) во внутреннюю, а второе во 16$ внешнюю область (рис. 8.12, г). Можно сделать вывод, что граф 6— планарен.
В том случае, если граф 6 = (Х, У) непланарен, то может быть поставлена задача его разбиения на плоские суграфы. Минимальное число 1 плоских суграфов, на которые может быть разбит граф 6, называется его толщиной. По графу пересечений Н =- (1', 'г) можно определить подмножество ребер У' ~ У, которые надо удалить из графа 6 =- (Х, (/), чтобы превратить его в плоский суграф 6, =- (Х, У,), где У, = У - У'. Количество таких ребер, т.
е. ~У'), называется числом планарногти графа. Если оставшийся суграф 6' = (Х, У') не планарен, то из него опять выделяют плоский суграф и т. д., пока не будет получено разбиение графа 6 на 1 плоских суграфов 6; =- (Х, У;), причем У =. () У;. ь=1 $ 8.3. мАтемАтические мОдели схем и мОнтАжнОТО пРОстРАнстВА Основными исходными данными для схемно-топологических задач конструирования являются схема электрическая функциональная или принципиальная и параметры типовых конструкций. Возможность формальной постановки этих задач и качество их решения в значительной степени зависят от математических моделей схемы и монтажного пространства. В общем случае к математической модели необходимо предъявить следующие основные требования: информационная полнота, т.
е. полнота отображения в модели свойств объекта, необходимых для решения задач конструкторского проектирования; высокая степень формализации отображаемого объекта; наличие математического аппарата, позволяющего выполнять формальные преобразования над моделью; однозначность и простота перехода от объекта к модели и обратно; возможность использования модели в существующих алгоритмах или возможность получения моделей. с которыми эти алгоритмы работают; наглядность представления объекта. В наибольшей степени изложенным требованиям удовлетворяет граф, являющийся содержательной моделью объекта проектирования. Геометрическое задание графа наглядно представляет отображаемый объект, а матричный и аналитический способы — формально.
Для основных задач схемно-топологического конструирования (компоновка, размещение и трассировка) в модели должна быть отражена следующая информация о схеме: связанность элементов схемы с точностью до вывода с учетом направления распространения сигнала и фактора неизвестности соединений в пределах одного комплекса, т. е. электрической цепи; топологические свойства элементов, обусловливающие ограничения на построение соединений (порядок расположения выводов, возможность прохода соединений, между ними и под элементом); метрические параметры элементов, т. е.
их размеры, координаты и размеры полей контактов; сведения об инвариант- ности выводов. Для различных задач этапа и алгоритмов их решения требуется различная информация об объекте конструирования. Например, при разрезании схемы на части и размещении элементов одного типоразме- Тбь ра существенной является только информация о связанности элементов в смысле числа электрических связей между ними без учета различия между входами и выходами; при решении задач поиска повторяющихся частей схем и их идентификации необходимо задавать направление связей между элементами с точностью до контактов этих элементов; при решении задачи трассировки для определения планар- ности схем и числа пересечений основными являются топологические свойства элементов. В связи с этим возможно использование моделей, несущих только ту часть информации о схеме, которая необходима для решения данной задачи конкретным алгоритмом.
При переходе от схемы к графу должна быть обеспечена адекватность модели и объекта в смысле отображения этой информации. Рассмотрим два основных способа перехода от схемы к графу: элементам схемы или их выводам (в зависимости от требуемой степени детализации отображения схемы) ставятся во взаимно однозначное соответствие вершины графа, а связи между ними представляются реярами. Получаем модель схемы в виде неориентированного или ориентированного обыкновенного графа (мультиграфа); каждому выводу или элементу схемы ставится во взаимно однозначное соответствие вершина гиперграфа (ультраграфа, если необходимо учитывать направление распространения сигнала), тогда каждое ребро гиперграфа (ультра- графа) соответствует электрической цепи, соединяющей эти элементы или их выводы.
При первом способе перехода от схемы к графу важным является представление электрической цепи ребрами графа,так как электрическая цепь обычно связывает более двух выводов элементов схемы. Представление схемы неориентированным мультиграфом. В этом случае, чтобы задать информацию о связанности элементов или их выводов, каждая цепь (комплекс) интерпретируется полным подграфом, что приводит к появлению избыточных ребер. Количество вершин подграфа определяется числом элементов или выводов, соединяемых данной цепью. При этом учитывается фактор неизвестности соединения, так как покрывающие деревья, построенные на полном подграфе, соответствуют возможным вариантам соединения элементов данной цепью. Модель схемы получается объединением полных подграфов. При такой интерпретации часто применяется вероятностный подход — каждому ребру и; Е У полного подграфа присваивается вес р, = 11(й — 1), (8.9) где й — количество вершин полного подграфа.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
