В. В. Павлов, д-р техн. наук проф., МГТУ "Станкин"

Полихроматические графы в теории систем

Одним из основных аспектов моделирования сложных систем является отображение различных связей между элементами этих систем, для чего используется аппарат теории графов [1]. Однако традиционный математический аппарат теории графов [2] не содержит средств одновременного описания и состава и разнообразных свойств вершин и ребер графа, что сужает возможности моделирования реальных систем. Такие средства содержит аппарат полихроматических ПS-множеств и ПS-графов. Более детальные исследования структуры и операций над ПS-множествами [З, 4, 5] позволяют существенно расширить представления о свойствах ПG-графов и возможностях их использования при моделировании систем.

Состав IIG-графа

Обычным графом называется пара G = (А, С), состоящая из множества A вершин и множества C ребер, связанных отношением инцидентности [2]. Полихроматическим назовем граф ПG с унитарной раскраской F(G), вершины и/или ребра которого являются полихроматическими множествами

                                             (1)

            (2)

где A, С — множества вершин и ребер, рассматриваемых без учета их раскраски; F(a), F(c) — множества различных персональных цветов всех вершин и ребер; F(A), F(C) — множество унитарных цветов — унитарные раскраски ПS_А и ПS_C;  — булевы матрицы персональных раскрасок отдельных вершин и ребер;  — булевы матрицы персональных цветов вершин и ребер, одноименных с унитарными цветами F(A), F(C);  — булевы матрицы вариантов тел, обеспечивающих существование унитарных цветов F(A), F(C). Унитарная раскраска F(G) ПG-графа определяется раскрасками его вершин и ребер.

Обычное множество А можно принять как полихроматическое, но с пустым составом унитарных цветов и пустыми составами персональных цветов элементов:

                                      (3)

аналогично можно представить множество С в виде

                                      (4)

Поэтому любой ПG-граф представляется тройкой

Состав ПS_А вершин в ПG - графе может соответствовать (1) или (3), а состав ПS_C ребер может соответствовать (2) или (4). Поэтому ПG-граф может относиться к одному из следующих видов:

                                                      (5)

                                                           (6)

                                                           (7)

Из (1)—(7) следует, что в любом ПG-графе существуют множества А и С, определяющие обычный граф G = (A, C), вершины и ребра которого бесцветны; этот граф называется бесцветным каркасом ПG-графа. Например, на рис. 1 приведены компоненты ПG-графа вида (5). Множество ПS_A вершин этого ПG- графа представляет собой элементы производственной системы, а множество ПS_C дуг характеризует возможные пути перемещения обрабатываемых деталей на производственном участке. Бесцветный каркас ПG-графа показан в виде обычного графа G = (A, C). Состав унитарных цветов, характеризующих виды обрабатываемых поверхностей и другие свойства заготовок и деталей,

F(G) = (F₁, F₂, F₃, F₄, F₅, F₆, F₇, F₈, F₉, F_l0, F₁₁, F₁₂)

является объединением унитарных цветов вершин F(A) и дуг F(C).

Рис. 1. ПG-граф структурной модели производственного участка:

Вершины ПG-графа: a₁ — горизонтально-фрезерный станок; a₂ — вертикально-фрезерный станок; a₃ — токарный станок; а₄ — сверлильный станок; а₅ — рабочий; a₆ — промышленный робот; а₇ — склад деталей.

Цвета ПG-графа — свойства заготовок и деталей: F₁ — плоская поверхность; F₂ — торец; F₃ — наружная поверхность вращения; F₄ — круглое отверстие; F₅ — фасонная поверхность; F₆ — паз прямолинейный сквозной; F₇ — паз прямолинейный глухой; F₈ — паз криволинейный; F₉ — перемещение заготовки (детали); F₁₀ — нежесткая деталь; F₁₁ — масса заготовки Р ≤ 15кг; F₁₂ — масса заготовки 15 < Р ≤ 50кг; • — элемент булевой матрицы c_p(q) = 1

Унитарная раскраска ПG-графа

Унитарная раскраска ПG-графа зависит как от раскрасок вершин и ребер, так и от взаимосвязи цветов вершин и ребер по условиям их существования. Возможны два вида такой взаимосвязи:

·        условия существования унитарных цветов вершин не зависят от цветов ребер и, наоборот, условия существования унитарных цветов ребер на зависят от цветов вершин;

·        условия существования унитарных цветов вершин зависят от цветов ребер и/или условия существования унитарных цветов ребер зависят от цветов вершин.

В реальных системах первому случаю соответствует ситуация, когда элементы системы — вершины ПG-графа — являются функционально самостоятельными объектами, свойства которых не зависят от других объектов и связей между ними. Примером является структурная модель производственного участка (см. рис. 1). Второму случаю соответствует, например, структурная модель конструкции сборного изделия, в которой свойства сопряжений — ребер ПG-графа — зависят от свойств сопрягаемых деталей — вершин ПG-графа.

При первом виде взаимосвязи F(A), F(C) и F(G) унитарные цвета вершин F(A) и ребер F(C) определяются независимо друг от друга в множествах ПS_A и ПS_C. Методика определения унитарных цветов ПS-множества в зависимости от состава его элементов и их персональных цветов приведена в [3]. Взаимосвязь всех персональных цветов F(a_i) элементов А и унитарных цветов F(A) множества ПS_A по условиям их существования описывается булевой матрицей

                (8)

состав персональных цветов F(a_i), непосредственно влияющих на существование унитарных цветов F(A), удобно представить в блочной булевой матрице

                          (9)

Блок  описывает зависимость существования каждого унитарного цвета F_j(A) от существования других унитарных цветов; блок вида  описывает зависимость существования каждого унитарного цвета от существования определенных персональных цветов элемента a_i ПS_A-множества. Зависимость существования F_j(A) от персональных цветов элементов ПS_A-множества описывается логическим уравнением дизъюнктивной нормальной формы

                                              (10)

Персональному цвету F_jk(a_ik) элемента a_ik, влияющему на существование F_j(A), соответствует равный единице элемент j-го столбца булевой матрицы (9), расположенный в j_k-й строке, принадлежащей персональным цветам F(a_ik). Если существование F_j(A) зависит только от персональных цветов, входящих в (10), условие существования имеет вид

                    (11)

Состав персональных цветов ребер, влияющих на существование унитарных цветов F(C), описывается аналогичной (9) булевой матрицей

                            (12)

а зависимость существования F_j(C) от персональных цветов ребер описывается аналогичным (10) уравнением

                                                       (13)

С помощью булевой матрицы (9) и вычисления условий вида (11) определяется состав F(A) унитарных цветов вершин ПS_A. Аналогично и независимо от F(A) определяется состав F(C) унитарных цветов ребер ПS. Унитарная раскраска ПG-графа в этом случае определяется с помощью операций над F(A) и F(C), например,

                                                           (14)

                                                           (15)

и других. В логической форме, при представлении всех цветов в едином булевом векторном пространстве [3], соотношения (9), (10) имеют вид

                                                         (16)

                                                          (17)

Известно, что взаимосвязь персональных и унитарных цветов ПS-множества может иметь дизъюнктивную или конъюнктивную форму [3]; соответственно множества (1) и (2) могут быть дизъюнктивными или конъюнктивными. При описании ПS_A и ПS_C составы их компонент могут быть представлены как полными наборами (1), (2), так и сокращенными наборами [4]; минимальными наборами компонент дизъюнктивных множеств будут

                                              (18)

                                             (19)

а минимальными наборами компонент конъюнктивных множеств будут

                           (20)

                           (21)

Состав (5), (6) или (7) ПG-графа с учетом форм взаимосвязи персональных и унитарных цветов вершин и ребер, а также отношений (16), (17) определяется по схеме

        (22)

При втором виде взаимосвязи F(A), F(C) и F(G), когда унитарные цвета вершин и ребер взаимозависимы по условиям существования, состав F(A) унитарных цветов ПS_A-множества вершин определяется в зависимости от персональных цветов и вершин и ребер, инцидентных этим вершинам. Поэтому булева матрица (9) дополняется блоками вида , описывающими зависимость существования унитарных цветов F(A) от персональных цветов ребра c_i ПS_A-множества, и матрица принимает вид

                 (23)

Операции над ПG-графами

При выполнении операций над ПG-графами возникает проблема идентификации вершин и ребер в целях выявления их эквивалентности, поскольку эквивалентные элементы, в силу закона идемпотентности [6], при теоретико-множественных и логических операциях поглощаются друг другом. Эквивалентность элементов ПS-множеств рассмотрена в [5]. В операциях над ПS-графами проблема эквивалентности должна решаться и для вершин, и для ребер. При моделировании реальных систем эквивалентность вершин и ребер будет относительным понятием, зависящим от их влияния на определенные свойства системы, описываемые унитарными цветами ПG-графа. Условия эквивалентности вершин a_i, a_j, как элементов ПS_A-множества [5], устанавливаются достаточно строгими:

                                        (28)

или менее строгими:

                                               (29)

Иногда условия эквивалентности устанавливаются с учетом не всего состава цветов F(a_i), F(c_j), а лишь определенной группы цветов :

                                (30)

Эквивалентность ребер с_i, c_j ПG-графов может определяться аналогичными условиями:

                                         (31)

или

                                                            (32)

или

                                 (33)

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

Наиболее простыми являются операции изменения состава исходного ПG-графа за счет исключения отдельных вершин и ребер. Исключая вершину a_j из ПS_A, исключают ее из A, а также исключают соответствующую строку из матриц  и ; при этом могут измениться составы цветов F(a), F(A) и тел A(F). Если в исходном графе существовало ребро c_ij, то это ребро исключается из состава ПS_C, так как оно лишается второй инцидентной вершины. Аналогично поступают при исключении ребра из ПS_C,, однако вершину, оставшуюся без инцидентного ребра, удаляют из ПS_A только в случае, если это специально оговорено в условиях задачи.

Зависимость существования унитарного цвета F_j(A) от персональных цветов вершин и ребер описывается в этом случае не (10), а логическим уравнением

                  (24)

где n' — число ребер, персональные цвета которых влияют на существование F_j(A).

Аналогичным способом определяется состав унитарных цветов F(C) ПS_C-множества ребер в зависимости от персональных цветов и ребер и вершин, инцидентных этим ребрам. Для этого булева матрица (12) дополняется блоками вида , описывающими зависимость существования унитарных цветов F(C) ребер от персональных цветов вершин a_i ПS_A-множества:

                 (25)

Зависимость существования F_j(C) от персональных цветов и вершин и ребер описывается логическим уравнением (13), дополненным конъюнкцией персональных цветов F_j’k(a_i’k) вершин, влияющих на существование F_j(C):

                (26)

Несмотря на внешнее сходство формул (24) и (26), их содержание может быть различным, поскольку они относятся к принципиально разным объектам системы — ее элементам и связям между элементами.

После определения унитарных цветов F_j(A) по матрице (9), а унитарных цветов F_j(C) — по матрице (25) унитарная раскраска F(G) ПG-графа в некоторых случаях может определяться так же, как в первом случае, по формулам вида (16), (17), и состав ПG-графа определяется по схеме (22). Следует иметь в виду, что использование формул (16), (17) предполагает определенную независимость унитарных цветов вершин и ребер по их влиянию на унитарную раскраску ПG-графа. Более общим является случай, когда такая независимость отсутствует и унитарная раскраска F(G) определяется по булевой матрице

       (27)

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

При добавлении новой вершины a_k вначале проверяется условие ее эквивалентности другим вершинам ПS_A: если существует a_j = a_k, то добавление a_k не имеет смысла, так как в силу закона идемпотентности она будет поглощена a_j, и состав ПS_A не изменится. Поэтому следует брать вершину, не эквивалентную ни одной из вершин в ПS_A. Однако при моделировании реальных систем в некоторых случаях необходимо иметь эквивалентные по своим свойствам элементы — например, с целью резервирования или дублирования для повышения надежности системы. В таких случаях эквивалентному элементу a_k формально присваивается новое свойство F_q — быть "резервным", "дублирующим" и т. п., и это свойство включается как новый цвет в F(a_k), после чего a_k уже не будет эквивалентным a_j по условию (29) или (28). После добавления a_k в матрицах  и  добавляется новая строка, соответствующая a_k. Если при этом , то изменится состав F(a) за счет добавления новых персональных цветов и, возможно, появятся новые тела в A(F) и новые унитарные цвета в F(A). Введение a_k в ПS_A требует также решения вопроса о появлении новых связей между элементами исходного множества вершин и a_k, т. е. о добавлении нового ребра или нескольких ребер. Добавление нового ребра c_jk в состав ребер исходного ПG-графа осуществляют по методике, аналогичной добавлению новой вершины; однако следует иметь в виду, что добавить ребро c_jk можно только в случае, если в ПS_A существуют вершины a_j, a_k, которые будут инцидентными вершинам этого ребра.

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

Простой является операция выделения части ПG-графа, так как в ней участвуют вершины и ребра только одного, исходного ПG-графа. Известно [2], что частью обычного графа G = (А, С) называется граф G_i = (A_i, C_i) такой, что  и для каждого ребра  в составе A_i имеются обе инцидентные этому ребру вершины a_j, a_k. Частью ПG-графа будет граф , бесцветный каркас G_i = (A_i, C_i) которого является частью каркаса G = (А, С) исходного ПG-графа. В выделяемой части ПG_i составы унитарных цветов

и условия существования унитарных цветов в F(G_i), F(A_i), F(C_i) соответствуют условиям существования этих цветов в исходном ПG-графе. Выделение  осуществляется по-разному в зависимости от условий задачи. Если в состав исходных данных входят вершины или ребра искомой части ПG-графа, то задача решается двумя путями.

1. Задается исходный ПG-граф и состав  вершин искомого ПG-графа, а затем определяется состав  ребер, инцидентные вершины которых входят в А_i, и определяются унитарные цвета F(A_i), F(C_i), F(G_i). Способ определения унитарных цветов зависит от условий их существования: если унитарные цвета вершин и ребер существуют независимо друг от друга, то используются булевы матрицы вида (9), (12) и формулы (10), (13); если унитарные цвета взаимозависимы по условиям их существования, то используются булевы матрицы (23), (25) и, возможно, (27), а также формулы (24), (26). В этом случае в ПG_i могут существовать изолированные вершины.

2. Задается исходный ПG-граф и состав  ребер искомого ПG-графа, а затем определяется состав  вершин, инцидентных заданным ребрам. Унитарные цвета F(A_i), F(C_i), F(G_i) определяются аналогично п. 1. В этом случае в ПG_i не будут существовать изолированные вершины.

Если в составе исходных данных указывается только унитарная раскраска F(G_i) выделяемой части , то задача будет определенной, только если в исходном ПG-графе взаимосвязь между унитарными цветами соответствует (17), ибо в этом случае имеет место , и условию задачи удовлетворяют значения F(A_i) = F(C_i) = F(G_i). Для определения состава вершин A_i используются столбцы матрицы [А х F(A)], соответствующие унитарным цветам F(A_i); для определения минимального набора вершин A_i используется матрица [А х A(F)] вариантов тел, обеспечивающих существование унитарных цветов F(A_i). Состав ребер C_i выделяемой части ПG-графа определяется аналогично определению состава вершин.

Если взаимосвязь между унитарными цветами в исходном ПG-графе соответствует (16), то при задании в исходных данных требуемого состава F(G_i) унитарных цветов выделяемой части ПG_i необходимо дополнительно указать либо желаемый состав F(A_i), либо F(C_i), после чего задача решается изложенными выше способами.

К операциям выделения части ПG-графа относится, например, построение маршрутов — цепей, циклов и т. п. Для этих частей обычного графа характерной является упорядоченная последовательность вершин и ребер, образующих маршрут [2]. Так, в графе G = (А, С) простой элементарный путь μ_i можно описать тремя способами:

                                        (34)

                                              (35)

                         (36)

Полагая, что G = (А, С) — бесцветный каркас ПG-графа, получим

                   (37)

Рассмотрим построение путей в ПG-графе (см. рис. 1). В соответствии со схемой (22) этот граф имеет вид

Унитарная раскраска вершин F(A), дуг F(C) и пути в целом F(G) определяется так же, как при выделении части ПG-графа с независимыми условиями существования унитарных цветов вершин и ребер. Так, для пути

получим: поскольку  — дизъюнктивное множество, то по матрице [А х F(A)] получим

поскольку  — конъюнктивное множество, то по матрице [С x F(C)] получим

и по матрице [С x C(F)] определим состав тел, реализующих эти цвета:

C₄(F₉)=C₄(F₁₀)=C₄(F₁₁)=(c₅₍₁₎, c₁₍₃₎, c₃₍₄₎, c₄₍₇₎).

Таким образом, унитарная раскраска части ПG-графа (см. рис. 1), соответствующей пути μ_i вычисляемая по формуле (16), равна

В отличие от операции выделения части ПG-графа, при вычислении разности, пересечения и объединения участвуют разные ПG-графы; кроме того, эти операции могут выполняться раздельно над множеством вершин и ребер исходных ПG-графов. Рассмотрим, например, исходные графы

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

(38)

Таким образом, если операции объединения ПG_iи ПG_j соответствует

                 (39)

операции пересечения соответствует

          (40)

операции разности соответствует

                           (41)

то

                (42)

                       (43)

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

Если раскраски вершин и ребер в ПG-графах взаимно независимы по условиям их существования, то все виды операций из (38) над ПG_i и ПG_j выполняются раздельно над их множествами вершин и множествами ребер, как это, например, описывается в (39)—(43) и т. п. При этом следует иметь в виду, что операция над множествами ПS_Ci, ПS_Cj ребер должна выполняться после операции над множествами ПS_Ai, ПS_Aj вершин, и в состав ребер искомого ПG-графа включаются только те ребра, для которых имеются обе инцидентные вершины. Методы выполнения операций объединения, пересечения и разности ПS-множеств приведены в [5]. После операции над ПS-множествами вершин и ребер по формулам (14), (15) или (16), (17) определяется унитарная раскраска F(G) ПG-графа. Операции пересечения и разности графов ПG_i и ПG_j не вызывают особых трудностей, поскольку результатом их выполнения являются части исходных ПG_i-графов. Действительно, при выполнении операции пересечения (40) получается часть исходного ПG_i-графа, вершины и ребра которой эквивалентны вершинам и ребрам ПG_j-графа; при выполнении операции разности (41) получается часть исходного ПG_i-графа, вершины и ребра которой не эквивалентны вершинам и ребрам ПG_j -графа. В обоих случаях на полученную часть вершин и ребер распространяются условия существования раскрасок исходного ПG_i-графа. Рассмотрим, например, операции над ПG-графами (рис. 2, а, б):

Рис. 2. Полихроматические графы ПG_i(a) и ПG_j(б):

• - c_p(q) = 1 и a_p входит в составы тел унитарного цвета F_q;

○ – c_p(q) = 1, но a_p не входят в сотавы тел унитарного цвета F_q

При пересечении  получается часть ПG_i^’ с составами вершин и ребер

Исключая из булевых матриц (рис. 2, а) строки, соответствующие не вошедшим в пересечения вершинам и ребрам, получим новые матрицы и раскраски:

следовательно, унитарная раскраска части ПGi^’, вычисляемая по формуле (14), равна

При разности ПG_i \ ПG_j получается часть ПG_i^” , в которой состав вершин равен

Состав ребер С_i^”, вычисляемый как разность множеств C_i и C_j равен

однако только ребра c_1,4 и c_1,6 имеют обе инцидентные вершины — (a₁, a₄) и (a₁, a₆), поэтому

Раскраски компонентов ПG_j^” равны

поскольку в матрице  на рис. 2, а нет ни одного тела, реализующего унитарные цвета F(A_i) при A_i^” = (a₁, a₄, a₆). Поэтому унитарная раскраска ПG_i^” равна

При разности ПG_j\ПG_i получается часть ПG_j^’ с составом вершин и ребер

ребра c_2,8, c_3,7 и c_5,7 не входят в C_j^’ из-за отсутствия второй инцидентной вершины. Раскраска этой части ПG_j-графа (рис. 2, б) равны

Таким образом, при вьщелении части ПG-гpaфа, при вычислении пересечения или разности

ПG_i ПG_j в составах унитарных цветов вершин, ребер и ПG-графа в целом не могут появиться новые унитарные цвета, не существовавшие ранее в исходных составах F(A), F(C) и F(G). В отличие от этих операций, объединение , соответствующее (39), связано с возможностью появления новых унитарных цветов из-за увеличения составов ПS_A и ПS_С за счет новых вершин и ребер. Примером объединения ПG_i, ПG_j, показанных на рис. 2, является ПG-граф (рис. 3). Булева матрица  этого графа являются объединениями соответствующих матриц исходных графов (см. рис. 2). Из матрицы [А х A(F)] ПG-графа (рис. 3) следует, что здесь не только сохранились все тела унитарных цветов F(A_i) и F(A_j), но дополнительно появились новые тела A₁(F₆) и A₃(F₃); кроме того, появились тела A₁(F₆), A₂(F₆) унитарного цвета F₆(A), не существовавшего ранее в F(A_i) и F(A_j).

Рис. 3. ПG-граф обьединения ПG_i и ПG_j:

• - c_p(q) = 1 и a_p входит в составы тел унитарного цвета F_q;

○ – c_p(q) = 1, но a_p не входят в сотавы тел унитарного цвета F_q

Из рассмотренных примеров следует, что при выполнении операций объединения, пересечения и разности графов ПG_i, ПG_j с независимыми условиями существования унитарных цветов вершин и ребер определение раскрасок F(A) и F(С) искомого ПG-графа осуществляется раздельно. Аналогично определяются раскраски вершин и ребер при выполнении комбинированных операций вида (42), (43) и т. п. Если условия существования унитарных цветов вершин и ребер исходных графов ПG_i, ПG_j взаимозависимы, то определение унитарных раскрасок F(A) и F(C) несколько усложняется, поскольку приходится использовать булевы матрицы (23), (26), однако это не вносит принципиальных трудностей. Аппарат полихроматических графов открывает широкие возможности структурного моделирования сложных систем и унификации математического обеспечения компьютерных технологий проектирования [7].

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

1. Технология системного моделирования /Е. Ф. Аврамчук, А. А, Вавилов, С. В. Емельянов и др.; Под общ. ред С. В. Емельянова и др. М.: Машиностроение; Берлин: Техник, 1988, 520 с.

2. Зыков А. А. Основы теории графов. М.: Наука, 1987. 384 с.

3. Павлов В. В. Полихроматические множества в теории систем. Структура ПS-множеств / Информационные техноло­гии. 1997. № 7. С. 11-16.

4. Павлов В. В. Полихроматические множества в теории систем. Изменение состава ПS-множеств / Информационные технологии. 1998. № 1. С. 4—8.

5. Павлов В. В. Полихроматические множества в теории систем. Операции над ПS-множествами / Информационные технологии. 1998. № 3. С. 8—13.

6. Куратовский К., Мостовский А. Теория множеств. М.: Мир, 1970. 416 с.

7. САПР. Типовые математические модели объектов проектирования в машиностроении / Методические указания РД50—464—84. М.: Изд-во Стандартов, 1985, 202 с.

МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ И СТРУКТУРНЫЙ СИНТЕЗ

ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ, № 6, 1998

Ключевые слова: Теория систем, моделирование, полихроматические графы, раскраска графа, операции над полихроматическими графами, логические матрицы.