ПОИСК Статьи Чертежи Таблицы Элементы теории графов из "Математические модели технических объектов (САПР 4) " Графы в математическом обеспечении САПР используются при решении задач синтеза, особенно в конструкторском проектировании, при проектировании программного обеспечения, баз данных, при решении задач анализа на макроуровне. [c.109] Топологические уравнения подсистем записываются для узлов и контуров эквивалентной схемы, поэтому получение эквивалентной схемы — необходимый этап подготовки технического объекта к моделированию. Поскольку существующие методы получения топологических уравнений основаны на применении графов, рассмотрим основные определения и понятия из их теории. [c.109] Граф — совокупность вершин (узлов) и связывающих их ребер (ветвей). Если ребра графа имеют определенное направление, то такой граф называют ориентнронанпым (орграфом), а его ребра —дугами (рис. 3.1). [c.109] Часть графа — граф, образованный из исходного графа удалением некоторых вершин и ребер. [c.109] Подграф — часть графа, образованная некоторым подмножеством ребер графа и всеми инцидентными им вершинами. [c.109] Граф (а) и его фундаментальные деревья (б, в). [c.110] Суграф — часть графа, образованная удалением из исходного графа некоторых ребер. Количество вершин графа и сугра-фа одинаково. [c.110] Маршрут — последовательность смежных ребер. Смежными считаются ребра, инцидентные одной и той же вершине, или вершины, инцидентные одному и тому же ребру. В общем случае маршрут может содержать повторяющиеся ребра и вершины. [c.110] Цепь — маршрут, в котором все ребра различны. [c.110] Замкнутая цепь называется циклом. [c.110] Простой цикл (контур)— цикл, не содержащий повторяющихся вершин. [c.110] Граф является связным, если можно указать маршрут, охватывающий все вершины. [c.110] Дерево графа — связный подграф, не имеющий циклов. [c.110] Фундаментальное дерево (остов) — связный суграф, не имеющий циклов, т. е. фундаментальное дерево охватывает все вершины графа и не образует ни одного цикла. [c.110] Ветви дерева — ребра графа, вошедшие в дерево. [c.110] Хорды — ребра графа, не вошедшие в дерево. [c.110] На рис. 3.2,0 представлен пример связного графа, а на рис. 3.2, б — его фундаментальное дерево. Ветвями дерева будут ребра б, г, е, ж, и, хордами — ребра а, в, д, к. [c.110] Выбор фундаментального дерева графа не однозначен, для одного и того же графа их может быть несколько. Так, на рис. 3.2, в представлено еще одно фундаментальное дерево графа (рис. 3.2, а). При этом ребра а, б, в, д, и — ветви дерева, г, е, ж, к — хорды. [c.110] П р н м е ч а н п с. Ниже будут рассматриваться только фундаментальные деревья. [c.110] При моделировании на макроуровне особый интерес представляет дерево, в которое ребра включаются согласно некоторому приоритету. Если, изображая структуру технического объекта, за каждым ребром графа закреплять обозначение заменяемого нм элемента, то мож1го построить нормальное дерево графа. [c.110] Вернуться к основной статье