| Метод выделения изоморфного подграфа графа СЭП в САПР электронных схем |
|
 |
|
|
| Авторы |
| | Курапов С.В. |
| | Давидовский М.В. |
| Год публикации |
| | 2021 |
| DOI |
| | 10.31114/2078-7707-2021-3-18-25 |
| УДК |
| | 547.12 |
|
| Аннотация |
| | Актуальной задачей при создании современных САПР электронной аппаратуры является задача распознавания структур различных объектов. Данная работа представляет метод решения задачи выделения подграфа G0 графа G(V,E) изоморфного заданному эталонному графу H(X,U). Метод основан на применении полного инварианта графа, описывающего его индивидуальную структуру в числовом представлении. Предварительное определение полного инварианта эталонного графа позволяет свести задачу к поиску множества подграфов графа G c количеством вершин равным мощности множества вершин card(X) графа H. Решение сводится к перечислению всех множеств сочетаний из |V|по|X|. Такая постановка задачи позволяет свести труднорешаемую задачу к вычислительным методам, имеющим полиномиальную вычислительную сложность. |
| Ключевые слова |
| | система автоматизированного проектирования, граф схемы электрической принципиальной, изоморфизм графов, выделение изоморфного подграфа. |
| Ссылка на статью |
| | Курапов С.В., Давидовский М.В. Метод выделения изоморфного подграфа графа СЭП в САПР электронных схем // Проблемы разработки перспективных микро- и наноэлектронных систем (МЭС). 2021. Выпуск 3. С. 18-25. doi:10.31114/2078-7707-2021-3-18-25 |
| Адрес статьи |
| | http://www.mes-conference.ru/data/year2021/pdf/D065.pdf |
