НАУКА и ОБРАЗОВАНИЕ

МГТУ им. Н. Э. Баумана

Во многих проектных задачах механическая система (машина или прибор) представляется в виде совокупности элементов, на которые наложены механические связи, доставляющие изделию целостность и тождественность. Эта парадигма дает основания для постановки и решения множества прикладных задач в проектировании и подготовке машиностроительного производства. Назовем лишь несколько важных применений данной структурной модели: поиск устойчивых и кратчайших размерных схем, проектирование схемы технологического членения, структурный анализ и синтез механизмов и др.

В большинстве работ, посвященных моделированию механической структуры,  элементы и связи представляются в виде различного вида ориентированных и неориентированных графов, см. например [2]. Опыт использования этих моделей показал, что выразительные возможности ориентированных и неориентированных графов не достаточны для описания некоторых существенных связей и отношений, существующих в реальных и проектируемых  изделиях. Элементы больших механических систем могут составлять сложноорганизованные неоднородные структуры, связанные многоместными отношениями. Важным примером таких отношений служит отношение базирования между деталями машины или прибора, которое, в общем случае, может иметь переменную местность или, как иногда говорят, арность. Напомним, что базированием называется придание заготовке или детали определенного положения в процессе обработки или сборки. Ограничимся рассмотрением механосборочного передела и будем обсуждать только конструкторские базы. В общем случае носителями конструкторских баз для устанавливаемой детали могут быть подмножества, состоящие из одной, двух, трех и т.д. деталей. Это значит, что отношение базирования имеет переменную местность и не может быть адекватно описано графовыми  средствами.

В [1] предложена гиперсетевая модель механических связей, доставляющих изделию (машине или механическому прибору) определенность базирования в процессе сборки. Эта модель образуется композицией двух компонентов, которые называются  первичной и вторичной сетями. Первичная сеть представляет собой классический граф механических связей, вторичная сеть является гиперграфом, который образуется из минимальных геометрически определенных подмножеств деталей (B-множеств в терминологии [1]). В этой модели первичная сеть выполняет вспомогательные функции, с ее помощью составляется и верифицируется основной носитель информации об отношении базирования – вторичная сеть. В [1] показано, что в парадигме этой модели адекватным описанием процесса сборки является последовательность стягиваний ребер вторичной сети. Каждое такое стягивание заключается в слабом удалении ребра степени (кратности) два и отождествлении двух соединяемых этим ребром вершин. Такое стягивание принято называть нормальным.

Рис. 1. Пример конструкции

На рис. 1 приведен пример простой конструкции крепления подшипника, а на рис. 2 показана гиперсеть конструкции (a), а также первичная (b) и вторичная (c) сети.

Рис. 2. Гиперсеть и ее подсети

На рис. 3 показана последовательность r₅, r₁, r ₂, r ₄ нормальных стягиваний ребер, переводящая вторичную сеть в одновершинный гиперграф.

Рис. 3. Последовательность нормальных стягиваний вторичной сети конструкции

Поскольку в процессе создания дискретных систем процедура взаимного координирования элементов является определяющей, то, по всей видимости, предложенный формализм можно распространить на множество собираемых конструкций не машиностроительного производства: аппараты, установки, здания, сооружения и пр. По этой причине большой научный и практический интерес представляет формулировка необходимых и достаточных условий, которыми должен обладать стягиваемый гиперграф.

Уточним постановку задачи. Гиперграф WS = (X, R, W) называется стягиваемым, если существует последовательность , для элементов которой должны выполняться условия:

1.      WS₀ = WS;

2.      WS_N-1 представляет собой одновершинный гиперграф;

3.      Для всех WS_j справедливо соотношение .

4.      Каждый элемент последовательности WS_j+1 получается из предыдущего WS_j стягиванием ребра кратности 2, . Такое стягивание называется нормальным.

Теорема 1. Любой стягиваемый гиперграф является связным и имеет, по крайней мере, одно ребро кратности 2. Число вершин | X | и число ребер | R | стягиваемого гиперграфа удовлетворяют соотношению .

Доказательство. Докажем вначале связность. Гиперграф называется связным, если любые две его вершины связаны маршрутом. Наличие такого маршрута следует из существования подпоследовательности нормальных стягиваний, реализация которых отождествляет эти вершины.

Первое нормальное стягивание состоит в слабом удалении ребра, соединяющего две вершины, и отождествлении этих вершин. Отсюда следует, что в гиперграфе должно наличествовать хотя бы одно ребро кратности два.

Неравенство докажем индукцией по числу вершин n = | X | гиперграфа. Для n = 2 гиперграф, состоящий из одного ребра степени 2, является стягиваемым. Включение в гиперграф любого числа дополнительных ребер, очевидно, не нарушит ни неравенства, ни свойства стягиваемости.

Пусть это неравенство выполняется для всех k-вершинных стягиваемых гиперграфов, где k<n, n>2. Покажем, что их этого следует выполнение неравенства для любого стягиваемого n-вершинного гиперграфа .

Последняя операция нормального стягивания заключается в отождествлении двух вершин x и y, соединенных, по крайней мере, одним ребром r_xy. Количество вершин n_x, n_y в каждом из подграфов , стянутых на вершины x и y не превышает n-1. По индуктивному предположению  и . Число ребер | R | в WS  не меньше суммы | R | + | R | + r_xy, а количество вершин | X | = n_x + n_y. Из этого следует, что . Теорема доказана.

Рассмотрим ситуацию, когда неравенство, связывающее число вершин и ребер стягиваемого гиперграфа, строгое, т.е. | X | < | R | + 1. Результатом стягивания такого гиперграфа будет одновершинный гиперграф с k = | R | - | X | + 1 петлями, т.е. ребрами, которые замыкаются на одну вершину. Пример такого образования показан на рис. 4.

Рис. 4. Гиперграф с k петлями

Типичная ситуация возникновения петель показана на рис. 5, где отождествление вершин x и y и слабое удаление ребра r₂ порождает петлю r₁.

Рис. 5. Порождение петли

Для гиперграфов, которые представляют собой модели отношений базирования в реальных изделиях, появление петель недопустимо, поскольку логически и физически противоречиво. В самом деле, собранное изделие – это изделие, все позиционные механические связи которого реализованы. Если следовать этому толкованию, то одновершинный гиперграф с петлями соответствует собранному изделию с нереализованными механическими связями.

Приведем аргументы физического характера, свидетельствующие о недопустимости петель. Пусть для некоторой вторичной WS сети изделия выполняется соотношение | X | < | R | + 1. Тогда на i-ой операции нормального стягивания возникнет ситуация, показанная на рис. 6, когда одновершинный подгиперграф WS_i соединяется с вершиной y гиперребрами r_j, j = 1,k.

Рис. 6. Установка y по совокупности механических связей

Если эти ребра таковы, что только реализованные вместе доставляют элементу y определенность базирования, то, по правилам построения вторичной сети, они должны быть заменены одним ребром, как показано на рис. 7.

Рис. 7. Замена ребер

Пусть среди всех связей r_j, j = 1,k, соединяющих y с WS_i (см. рис. 6), существуют, по крайне мере, две связи r_s, r_t, доставляющие y определенность геометрического расположения относительно WS_i. В этом случае при установке y на WS_i данный элемент должен быть скоординирован относительно двух внешних систем координат, которые образуют конструктивы связей r_s, r_t. Эти конструктивы принадлежат одному собранному фрагменту WS_i, поэтому создается ситуация «избыточной скоординированности» y, когда для установки этого элемента требуется реализовать два полных комплекта конструкторских баз. Это типичная и достаточно распространенная ошибка проектирования. На стадии подготовки проектной документации она порождает неразрешимые размерные цепи, а на стадии технологической подготовки производства служит причиной явления, называемого перебазированием.

Простой пример избыточных связей и вызванного ими перебазирования дает конструкция крепления подшипника, показанная на рис.1. Вторичная сеть этой конструкции (см. рис. 2, с) состоит из пяти вершин и пяти ребер, т.е. для этого примера выполняется соотношение | X | < | R | + 1. Легко видеть, что вершина x₄ (крышка) соединяется с подсетью, состоящей из вершин x₁, x₂, x₃ двумя ребрами r₃, r₄, каждое из которых определяет положение крышки (x₄) относительно стакана (x₁), подшипника (x₂) и шайбы (x₃) в сборе. В зависимости от индивидуальных размеров деталей и выбранной последовательности установки между крышкой и шайбой или между крышкой и стаканом неизбежно возникнет зазор или натяг, не указанные на чертеже. Поэтому одна из связей r₃ или r₄ является фиктивной. Если сохранить обе эти связи, то в процессе сборки этого простого узла возникнет эффект перебазирования при установке крышки x₄ на собранный фрагмент, состоящий из деталей x₁, x₂ и x₃. Эту ситуацию ясно демонстрируют два последних фрагмента на рис. 3.

Итак, можно утверждать, что любой гиперграф, описывающий структуру позиционных механических связей собираемого изделия, должен удовлетворять условию | X | = | R | + 1. Сказанное позволяет сформулировать необходимые условия нормальной стягиваемости гиперграфов. Если существует последовательность нормальных стягиваний вершин гиперграфа WS = (X, R, W), превращающая WS в одновершинный гиперграф без петель, то должны выполняться следующие условия:

1.      Среди ребер WS существует по крайне мере одно ребро степени 2.

2.      Гиперграф является связным.

3.      Количество вершин | X | и ребер | R | гиперграфа WS удовлетворяют линейному ограничению | X | = | R | + 1.

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

На рис. 8 показаны три нестягиваемых гиперграфа четвертого порядка. Первый и второй образцы представляют собой два изоморфных образца одного гиперграфа. Комбинаторное разнообразие этого класса невелико, поэтому можно проверить непосредственно, что двумя приведенными примерами исчерпываются все неизоморфные нестягиваемые гиперграфы четвертого порядка.

Рис. 8. Нестягиваемые гиперграфы четвертого порядка

На рис. 9 изображены четыре неизоморфных гиперграфа пятого порядка. Для лучшего восприятия третьего сложного примера его ребра  нарисованы линиями разного стиля.

Рис. 9. Нестягиваемые гиперграфы пятого порядка

Множество неизоморфных нестягиваемых образцов очень быстро растет с увеличением количества вершин. Так, по приведенным на рис. 9 примерам легко построить множество новых нестягиваемых гиперграфов пятого порядка. Можно предложить и общую схему порождения подобных примеров. Они состоят преимущественно из ребер высоких степеней (четвертой и выше) и небольшого числа ребер второй степени. Причем последние являются либо мостами, либо соединяют вершины, не принадлежащие разным ребрам высоких степеней. В этом случае стягивание ребра второй степени не приводит к снижению размерности других ребер и появлению индуцированных ребер второй степени, которые, в свою очередь, могут быть стянуты. Это делает невозможным продолжение нормальных стягиваний ребер гиперграфа.

Пока не удалось сформулировать и доказать достаточные условия стягиваемости для гиперграфов общего вида, но для некоторых важных частных случаев эта задача решена.

Определение 1. Конечное семейство подмножеств  называется независимым, если существует такая перестановка U_i1, U_i2, … ,U_in его множеств, при которой . Семейство, не допускающее таких упорядочений, называется зависимым. Пустое семейство при n = 0 --  независимо по определению.

Из приведенных определений следует, что семейство, состоящее из одного множества, независимо тогда и только тогда, когда , семейство  из двух одинаковых множеств  -- всегда зависимо. Всякое подсемейство независимого семейства  -- независимо, а семейство, содержащее зависимое подсемейство, само является зависимым.

Определение 2. Рангом  семейства  называется наибольшее количество его множеств, образующих независимое подсемейство. Очевидно, что ранг семейства не изменится, если пустые удалить все множества и дубликаты.

Определение 3. Рангом конечного гиперграфа WS = (X, R, W) называется ранг семейства всех его ребер, рассматриваемых как множества инцидентных вершин, т.е. .

Иными словами, равенство  означает, что в R можно выбрать последовательность из  (не более) ребер  для которой .

Теорема 2. Если гиперграф WS = (X, R, W), не содержащий висячих ребер, удовлетворяет равенствам | X | = | R | + 1 и , то он стягиваемый.

Доказательство. Так как ранг гиперграфа равен n = | R |, то семейство  ребер, каждое из которых рассматривается как множество инцидентных вершин, является независимым. Т.е. существует последовательность X_i1, X_i2, … , X_in такая, что , , здесь X_ik - сокращенное обозначение X(r_ik). Каждое X_ik отличается от  по крайней мере одной вершиной. Поэтому для всех  выполняется неравенство . Поскольку по условиям теоремы | X | = | R | + 1 = n +1, то справедливо соотношение  для всех .

Для k=1 , а так как гиперграф WS не содержит висячих ребер, то степень X_i1 равна 2. Стягиванием ребра X_i1 получаем составную вершину y.

Из независимости подсемейства  и неравенства  следует, что ребро X_i2 инцидентно только одной вершине x, не принадлежащей X_i1. Поскольку , то это ребро соединяет составную вершину y и простую вершину x, поэтому стягивание ребра X_i2 будет правильным.

Распространяя это рассуждение на все , получим, что гиперграф WS = (X, R, W) стягиваемый, а последовательность X_i1, X_i2, … , X_in представляет собой последовательность правильных стягиваний ребер, которая переводит WS в одновершинный гиперграф без петель. Теорема доказана.

Удалось сформулировать и доказать достаточные условия стягиваемости для нескольких интересных частных классов гиперграфов. Готовится к печати продолжение этой статьи, в которой будут приведены полученные результаты. Достаточные условия стягиваемости гиперграфов общего вида пока неизвестны. Эта открытая и интригующая проблема может оказаться весьма сложной, но можно привести множество ослабленных постановок и частных случаев, представляющих большой научный и практический интерес. Приведем две важные постановки:

1.      Достаточные условия стягиваемости для гиперграфов с ребрами ограниченных степеней, например не выше 4. Если обратиться к базовой интерпретации гиперграфов как вторичных сетей механических изделий, ребра которых описывают минимальные геометрические группировки деталей, то такое ограничение обретает необходимую легитимацию. Инженерная практика не знает конструкций, где определенность базирования доставляется множеством из пяти и более деталей.

2.      Достаточные условия линейной стягиваемости гиперграфов. В технологии машиностроения линейной называется сборка изделия без предварительного разбиения на сборочные единицы. Математическим описанием этого важного производственного процесса является линейное стягивание гиперграфов. В этом случае гиперграф переводится в одновершинное состояние такой последовательностью нормальных стягиваний, когда каждое удаляемое ребро, инцидентно, по крайней мере, одной не составной вершине.

Список литературы

1.      Божко А.Н. Моделирование механических связей изделия// Электронное научно-техническое издание «Наука и образование» – 2011. – ╧3.

2.      Сборка и монтаж изделий машиностроения: справочник в 2-х томах / Под ред. В.С. Корсакова, В.К. Замятина. – М.: Машиностроение, 1983. – 480+360 с.

3.      Солонин И.С. Солонин C.И. Расчет сборочных и технологических размерных цепей. – М.: Машиностроение, 1980. – 112.

4.      Тимковский В.Б. Дискретная математика в мире станков и деталей. – М.: Наука, 1992. – 145 с.