Технико-экономические показатели САПР
Экономическая эффективность САПР вызвана следующими факторами:
- ростом производительности труда проектировщиков;
- повышением качества проектирования;
- повышением привлекательности труда проектировщиков;
- ростом производительности труда и сокращением затрат при изготовлении продукции;
- улучшением качества организации и управления производством.
Рост производительности труда и сокращение затрат при проектировании и в процессе производства вызван следующими основными факторами:
- унификацией и стандартизацией при проектировании и производстве изделий;
- автоматизацией поиска, обработки и выдачи информации;
- автоматизацией выполнения работ по формированию графической и текстовой документации;
- снижением влияния субъективных факторов;
- улучшением организации, оперативного управления и контроля процесса проектирования.
Рост производительности труда и сокращение затрат в процессе производства вызван следующими основными факторами:
|
|
- улучшением качества конструкторской и технологической документации;
- обеспечением технологичности проектируемых изделий;
- оптимизацией созданных конструкторских и технологических решений;
- уменьшением сроков освоения и затрат по освоению новой продукции за счет унификации и стандартизации спроектированных решений, уменьшающих нагрузку на вспомогательное производство;
- автоматизацией подготовки программ для оборудования с ЧПУ;
Основные показатели эффективности автоматизации проектирования:
- уровень автоматизации проектирования (АСУП, АСНИ, САПР К, САПР ТП, САП):
- удельный вес продукции, изготовленной по документации, созданной с помощью средств САПР:
- экономия от снижения себестоимости продукции;
- условное сокращение численности работающих в проектных подразделениях и в основном производстве.
Прежде чем дать определение графа, мы покажем на рис всё 11 графов с четырьмя вершинами. Позже мы увидим, что:
1) любой граф с четырьмя вершинами изоморфен одному из них;
2) пять графов, которые на рисунке расположены слева от штриховой линии, не связны;
3) шесть графов, расположенные справа от штриховой линии, связаны;
4) последний граф — полный;
5) первый граф — пустой или вполне несвязный;
6) первый граф с четырьмя ребрами — цикл;
7) первый граф с тремя ребрами — простая цепь. Вместо того чтобы продолжать
повествование на интуитивном уровне, вводя время от времени, различные понятия теории графов, мы перейдем к систематическому, хотя и утомительному, введению этих понятий одного за другим. Граф G состоит из конечного непустого множества V, содержащего р в ершин, и заданного множества X, содержащего q неупорядоченных пар различных вершин из V.
|
|
Каждую пару x= {и, v} вершин в X называют ребром графа G
и говорят, что x соединяет u и v. Мы будем писать x=uv и говорить, что u и v - смежные вершины иногда это обозначается u adj v; вершина u и ребро х инцидентны так же как v и x. Если два различных ребра x и y инцидентны одной и той же вершине, то они называются смежными. Граф с р вершинами и q ребрами называется (р, q)-графом. (1,0)-граф называется тривиальным.
Обычно граф представляется диаграммой, и ее-то часто называют графом. Таким образом, у графа G на рисунке вершины u и v смежные, а вершины u и w нет; ребра x и y смежные, а x и z нет. Хотя на диаграмме ребра x и y пересекаются, их точка пересечения не является вершиной графа.
Имеется несколько типов графов, которые целесообразно привести. Отметим, что из определения вытекает, что в графе не может быть петель, т. е. ребер, соединяющих вершины сами с собой. В мультиграфе не допускаются петли, но пары вершин могут соединяться более чем одним ребром; эти ребра называются кратными. Если допускаются петли и кратные ребра, получаем псевдограф.
На рис. приведены мультиграф и псевдограф, в основе которых «лежит» один и тот же граф - треугольник.
Ориентированный граф, или орграф, D состоит из конечного непустого множества V вершин и заданного набора X упорядоченных пар различных вершин. Элементы из X называются ориентированными ребрами, или дугами. По определению в орграфе нет
петель и кратных дуг. Направленный граф — это орграф, не имеющий симметричных пар ориентированных ребер. На рисунке приведены все орграфы с тремя вершинами и тремя дугами; два последних из них — направленные графы.
Граф называется помеченным. (или перенумерованным), если его вершины отличаются одна от другой какими-либо пометками, например v1,..., vn. Графы G1 и G2 на рисунке помеченные, а граф G3 нет.
Два графа G и Н изоморфны (записывается G@H или иногда G=H), если между их множествами вершин существует взаимно однозначное соответствие, сохраняющее смежность. Например, G1 и G2 на изоморфны при соответствии ui <--> vi и чисто случайно оказалось, что граф G3 изоморфен каждому из них. Совершенно очевидно, что изоморфизм есть отношение эквивалентности на графах.
Инвариант графа G — это число, связанное с G, которое принимает одно и то же значение на любом графе, изоморфном G. Так, числа р и q являются инвариантами графа. Полный набор инвариантов определяет граф с точностью до изоморфизма Например, числа р и q образуют полный набор инвариантов для всех графов с числом вершин, меньшим четырех. В настоящее время мы не знаем ни одной полной нетривиальной системы инвариантов для графов.
Подграфом графа G называется граф, у которого все вершины и ребра принадлежат G. Если d— подграф графа G, то G называется надграфом (supergraph) графа d. Остовный подграф — это подграф графа G, содержащий все его вершины. Для любого подмножества S вершин графа G порожденным подграфом <S> называется максимальный подграф графа G, множеством вершин которого является S. Таким образом, две вершины из S смежны в <S> тогда и только тогда, когда они смежны в G. На рисунке G2— остовный подграф графа G1, а G2 нет; G1 - порожденный подграф, а G2 нет.
Удаление вершины u,- из графа G приводит к подграфу G - vi, содержащему все вершины графа G, за исключением vi, и все ребра графа G, не инцидентные vi. Другими словами, G - vi есть максимальный подграф графа G, не содержащий vi. Удаление ребра xj из G приводит к остовному подграфу, содержащему все ребра графа G, за исключением xj, т. е. G - xj есть максимальный подграф графа G,
не содержащий xj. Удаление произвольного множества вершин или ребер из G определяется как последовательное удаление всех элементов этого множества. С другой стороны, если vi и ui не смежны в G, то добавление ребра viui образует наименьший надграф графа G, содержащий ребро viui. Эти понятия иллюстрируются на рисунке.
|
|
Существуют графы, для которых результат удаления вершины или ребра или же добавления ребра не зависит от выбора вершины или ребра. Для графа G, обладающего этим свойством, обозначим соответствующие графы через G - u, G - x и G+x;
Улам [1] высказал предположение, что набор подграфов G—vi несет полную информацию о всем графе G.
Гипотеза Улама. Пусть граф G имеет р вершин и, граф Н имеет р вершин ui и р>= 3. Если для каждого i подграфы Gi = G - vi и Н = Н - ui изоморфны, то и графы G и Н изоморфны.
Нарисуем каждый из р непомеченных графов G-u, на карточке размером 3x5. В гипотезе говорится, что любой граф с р вершинами, из которого, удаляя каждый раз лишь по одной вершине, можно получить данные подграфы и только их, изоморфен G. Таким образом, в гипотезе Улама утверждается, что любые два графа с одним и тем же набором карточек изоморфны. Кажется, более естественным пытаться доказать (или опровергнуть), что по любому допустимому набору карточек восстанавливается только один граф.