Типы графов

Технико-экономические показатели САПР

Экономическая эффективность САПР вызвана следующими факторами:

- ростом производительности труда проектировщиков;

- повышением качества проектирования;

- повышением привлекательности труда проектировщиков;

- ростом производительности труда и сокращением затрат при изготовлении продукции;

- улучшением качества организации и управления производством.

Рост производительности труда и сокращение затрат при проектировании и в процессе производства вызван следующими основными факторами:

- унификацией и стандартизацией при проектировании и производстве изделий;

- автоматизацией поиска, обработки и выдачи информации;

- автоматизацией выполнения работ по формированию графической и текстовой документации;

- снижением влияния субъективных факторов;

- улучшением организации, оперативного управления и контроля процесса проектирования.

Рост производительности труда и сокращение затрат в процессе производства вызван следующими основными факторами:

- улучшением качества конструкторской и технологической документации;

- обеспечением технологичности проектируемых изделий;

- оптимизацией созданных конструкторских и технологических решений;

- уменьшением сроков освоения и затрат по освоению новой продукции за счет унификации и стандартизации спроектированных решений, уменьшающих нагрузку на вспомогательное производство;

- автоматизацией подготовки программ для оборудования с ЧПУ;

Основные показатели эффективности автоматизации проектирования:

- уровень автоматизации проектирования (АСУП, АСНИ, САПР К, САПР ТП, САП):

- удельный вес продукции, изготовленной по документации, созданной с помощью средств САПР:

- экономия от снижения себестоимости продукции;

- условное сокращение численности работающих в проектных подразделениях и в основном производстве.

 

 

Прежде чем дать определение графа, мы покажем на рис всё 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. Таким образом, в гипотезе Улама утверждается, что любые два графа с одним и тем же набором карточек изоморфны. Кажется, более естественным пытаться доказать (или опровергнуть), что по любому допустимому набору карточек восстанавливается только один граф.