Учебная САПР электронных средств. Асланянц В.Р. - 6 стр.

       • временная сложность.
       Теория графов
       Графы и гиперграфы широко используются в качестве математиче-
ских моделей (ММ) схем и конструкций в задачах синтеза и анализа ЭС
[2,6,7,8].
       Понятие граф опирается на теорию множеств и отношений. Граф
представляет собой бинарное отношение на множестве объектов (вершин
графа). Граф состоит из вершин и ребер (дуг для ориентированного графа).
       К разновидности графа относят:
               • мультиграф;
               • двудольный граф;
               • полный граф;
               • дерево;
               • гиперграф.
       Гиперграф представляет собой n-арное отношение на множестве
вершин, т.е. гиперребра могут быть инцидентны трем, четырем и белее
вершинам.
       К числовым способам представления графа относят:
       • матричное представление;
       • списковое представление.
       Существует два особенных цикла в графе: эйлеров и гамильтонов.
       Простой признак существования эйлеров цикла (это первый резуль-
тат в теории графов) сформулирован в виде теоремы Эйлера.
       Для гамильтонова цикла простого признака существования нет.
       Нахождение гамильтонова цикла минимальной длины во взвешен-
ном по ребрам графе называется задачей коммивояжера.
       Изучение графов облегчается путем введения чисел графа [12]:
       • цикломатического;
       • хроматического;
       • числа внутренней устойчивости;
       • числа внешней устойчивости;
       • числа планарности.
       Для определения максимального ВУМ (внутренне устойчивого мно-
жества вершин) и раскраски вершин графа применяют метод Магу и эври-
стические алгоритмы.
       При автоматизированном проектировании однослойных конструк-




                                                                       6