запропоновано метод дифференцации вершин і ребер гіперграфу, який реалізує ідею інтеграції структурних відмінностей в гіперграфах і отримання інтегральних характеристик для вершин і ребер. Розроблено та обґрунтовано ефективний алгоритм вирішення задачі визначення ізоморфізму гіперграфів, в основу якого покладено метод паралельного диференціювання вершин і ребер в декількох гіперграфах. Робота алгоритму показана на прикладі визначення ізоморфізму двох гіперграфів.

Анотація наукової статті з математики, автор наукової роботи - Погрібний Володимир Кирилович


The differentiation method of hypergraph vertices and edges implementing the idea of ​​structural differences integration in hypergraph and obtaining integral characteristics for vertices and edges has been proposed. The efficient algorithm of solving the problem of determining isomorphism of hypergraphs was developed and justified. The method of parallel differentiation of vertices and edges in several hypergraphs is taken as a principle of this algorithm. Algorithm functioning is shown by the example of determining isomorphism of two hypergraphs.


Область наук:
  • Математика
  • Рік видавництва: 2010
    Журнал: Известия Томського політехнічного університету. Інжиніринг ГЕОРЕСУРСИ

    Текст наукової роботи на тему «Алгоритм розв'язання задачі визначення ізоморфізму гіперграфів»

    ?004.94

    АЛГОРИТМ РІШЕННЯ ЗАВДАННЯ ВИЗНАЧЕННЯ ізоморфізму гіперграфах

    В.К. Погрібний

    Томський політехнічний університет E-mail: Ця електронна адреса захищена від спам-ботів. Вам потрібно увімкнути JavaScript, щоб побачити її.

    Запропоновано метод дифференцации вершин і ребер гіперграфу, який реалізує ідею інтеграції структурних відмінностей в гіперграфах і отримання інтегральних характеристик для вершин і ребер. Розроблено та обґрунтовано ефективний алгоритм вирішення задачі визначення ізоморфізму гіперграфів, в основу якого покладено метод паралельного диференціювання вершин і ребер в декількох гіперграфах. Робота алгоритму показана на прикладі визначення ізоморфізму двох гіперграфів.

    Ключові слова:

    Гіперграфовая модель, ізоморфізм гіперграфів, метод дифференцации вершин і ребер, метод паралельної дифференцации, інтеграція структурних характеристик, інтегральні характеристики вершин і ребер. Key words:

    Hypergraph model, isomorphism of hypergraphs, differentiation method of vertices and edges, method of parallel differentiation, Integration of structural characteristics, integral characteristics of vertices and edges.

    Для аналізу структурних властивостей складних розподілених систем широко використовуються графові моделі. Прагнення підвищити адекватність моделі призводить до необхідності використовувати не тільки бінарні відносини між компонентами системи (вершинами графа), а й відносини, які об'єднують більше двох вершин. У цьому випадку в якості моделі використовується гіперграф [1]. Ребро гіперграфу, що зв'язує сукупність вершин, відповідає певному відношенню між даною сукупністю вершин. Це, наприклад, може бути сукупність компонентів (вершин) системи, що беруть участь у виконанні певної функції, або сукупність даних, що описують певний об'єкт, властивості, події, або сукупність елементів радіоелектронної апаратури, об'єднаних в одну електричну ланцюг [2].

    При вирішенні завдань декомпозиції безлічі компонентів системи на підмножини вирішується завдання розрізання графа на підграфи. У процесі декомпозиції часто виникає потреба у встановленні структурної і функціональної еквівалентності подграфов, т. Е. Рішенні задачі визначення ізоморфізму графів. Відомо, що дана задача відноситься до неполіноміальному класу складності. Тому, як правило, алгоритми її вирішення розроблялися для приватних умов і видів графів. В роботі [3] запропонований алгоритм рішення задачі визначення ізоморфізму для графів загального вигляду.

    Основна ідея, висунута в [3] і покладена в основу розробки алгоритму, полягає у визначенні для кожної вершини графа інтегральної характеристики, узагальнюючої її відносини з інтегральними характеристиками всіх інших вершин графа. Інтегральні характеристики вершин виходять за допомогою рекурсивного правила інтеграції відмінностей вершин. Процедура, яка реалізує дане правило, послідовно виконує ітерації згідно глибині рекурсії. Число ітерацій при цьому не перевищує діаметр гра-

    фа. На к-ой ітерації для кожної вершини узагальнюються відомості про характеристики суміжних з нею вершин. Характеристики цих суміжних вершин в свою чергу були отримані на (к-1) -й ітерації як результат узагальнення характеристик своїх суміжних вершин. В результаті виконання рекурсивного правила кожна вершина отримує свою унікальну інтегральну характеристику. Можна сказати, що отримана таким чином характеристика вершини інтегрально відображає унікальність її положення щодо структури унікальних положень всіх інших вершин в графі.

    Два графа є ізоморфними, якщо між інтегральними характеристиками вершин даних графів має місце взаємно однозначна відповідність. В [3] знайдено простий і ефективний механізм, що дозволяє втілити цю ідею у формі алгоритму узагальнення характеристик вершин. Мета цієї статті полягає в розробці алгоритму розв'язання задачі визначення ізоморфізму гіперграфів, що використовує ідею отримання інтегральних характеристик.

    Характеристики вершин і ребер гіперграфів

    і завдання визначення ізоморфізму

    У моделі, представленої гіперграфах # = (2, Л, /), безліч вершин 0 = {д}, г = 1,2, ..., і відповідає безлічі компонентів системи, безліч ребер Я = {г), / = 1 , 2, ... т відповідає безлічі відносин, що задаються на безлічі компонентів, а функція ^ виконує роль ІНЦІ-дентора, який кожному ребру г ставить у відповідність підмножина вершин пов'язаних між собою / -м ставленням.

    Гіперграф можна уявити матрицею ІНЦІ-денця Л = || а / || "хі, де а = 1, якщо вершина инцидентна ребру / і а = 0, в іншому випадку. Гіперграфах Н1 = (01, Я1,? 1) і Н2 = (0ьЯьВ2) за умови, що | й | = 02 | і | Д | = | Л2 |, ​​є ізоморфними, якщо між множинами і 02 і між множинами Я1 і Я2 можна встановити взаємно однозначні відповідності, при яких інцідентори

    = 1 2 3 4 5 6 а, а2 а0

    1 = 1 1 1 1 3 3 1

    А = 2 1 1 1 3 3 1

    3 1 1 1 3 4 2

    4 1 1 1 3 3 1

    5 1 1 1 3 3 1

    А2 2 + 2 3 3 3

    Р, 3 4 3 4 4 4

    Р ° 1 2 1 3 3 × 3

    а

    Мал. 1. Приклад візуального та матричного уявлення гіперграфу

    і збігаються і, отже, матриці А1 і А2, побудовані з урахуванням цих відповідностей, повинні бути рівні, т. е. А1 = А2.

    З цього визначення випливає, що ізоморфізм двох гіперграфів можна встановити шляхом послідовного перебору перестановок рядків і стовпців в матриці інціденцій одного з гіперграфів і після кожної перестановки порівнювати отриману матрицю з матрицею іншого гіперграфу. У загальному випадку число перебираються варіантів матриць може досягти п! Хт! Очевидно, що, якщо гіперграфах неізоморфних, то для того, щоб переконатися в цьому, потрібно перебрати всі п! Хт! варіантів.

    Приклад гіперграфу, що містить 5 вершин і 6 ребер, на рис. 1, а, представлений візуально і на рис. 1, б, матрицею інціденцій. Зокрема, для визначення ізоморфізму двох гіперграфів такої розмірності число перебираються матриць складе 5! Х6! = 86400.

    Істотне скорочення переборовши досягається на основі використання ряду структурних характеристик вершин і ребер гіперграфу. Якщо для окремих вершин і ребер вдається отримати унікальні значення характеристик, то відповідні вершини і ребра можуть бути виключені з перестановок. Для розглянутого прикладу гіперграфу (рис. 1) наведені значення двох характеристик а1 і А2 для вершин і двох характеристик Д і Д для ребер.

    Характеристика а1; дорівнює числу ребер інцидентних вершині д ,, а характеристика А2! позначає ступінь зв'язності вершини д з іншими вершинами гіперграфу (рис. 1, а). Так, вершина Д3 пов'язана з усіма вершинами, т. Е. А23 = 4, а для інших вершин д характеристика 2 = 3.

    Характеристика Д визначає число вершин інцидентних ребру г, а характеристика Д дорівнює числу ребер в гіперграфах суміжних з ребром г ,. Наприклад, з рис. 1, а слід, що ребро г2 несуміжних тільки з ребром г5, т. Е. Д5 = 4, а ребро г1 суміжно з ребрами г2, г5, г6 і Д21 = 3.

    Значення показників | аг | = (а1, а2) і {Д} = (Д, Д) для гіперграфу (рис. 1, а) представлені на рис. 1, б, справа і знизу від матриці А. Унікальні значення характеристик в даному примі-

    ре отримали вершина Д3 з (а13, А23) = (3,4) і ребро г2 з (Д2, Д2) = (2,4). З огляду на відміну характеристик у ребер г2, г3 і г4, г5, г6, число перебираються варіантів скорочується до 4! Х2! Х3! = 288.

    Можна припустити, що при розширенні числа характеристик в сумах а = (аг | і Д = {Д} буде зростати відмінність (диференціація) вершин і ребер за значеннями даних характеристик. Однак, залучаються з цією метою характеристики аг і Д не завжди приводять до диференціації вершин і ребер. Так, для прикладу на рис. 1, б, все вершини щодо характеристики а1 виявилися невиразні. Крім того, прагнення підвищити диференціацію за рахунок розширення характеристик в сумах {аг} і {Д} може привести до такого зростання витрат на їх обчислення, до віді виявляться порівнянними з витратами на рішення вихідної задачі. Тому важливо знайти механізм диференціації вершин і ребер на основі простих і легко обчислюваних характеристик.

    Метод диференціації вершин і ребер гіперграфу

    Розглядається ситуація, коли для вершин і ребер гіперграфу # = (2, Л, /) визначені значення сукупностей простих характеристик а = {ае} і Д = {Д}. Введемо функції 5 (а) і 8 (Д), значення яких є числами натурального ряду в інтервалі 1,2, ..., п для 8 (а) і в інтервалі 1,2, ..., т для 8 (Д ). Функція 8 (а) кожної сукупності значень характеристик а; = (а1; а2;, ...) вершини д ставить у відповідність кодове число а, ° ізряда чисел 1,2,., П так, щоб різні сукупності значень отримали різні кодові числа, т. е. дотримувалася умова:

    ^ Чг>Чк е 1 * до [(ача, ...) *

    * ( «1 до, а2к. •••)] ^ (а0 * ак0) -зауважив, що елементи в сумах (а1; а2;, ...) впорядковані і порівняння сукупностей при виконанні функції 8 (а) має виконуватися з урахуванням цього порядку.

    Аналогічно виконується функція 8 (Д), привласнюючи сукупності значень характеристик Д = (Д, -Д2 /, "-) кодове число Д0 з ряду чисел, т.

    1,2,

    У підсумку виходять вектори «, = {а? 0} і

    Р ° = {Р °}, елементи яких відображають відмінності серед вершин і ребер щодо введених характеристик. Для прикладу гіперграфу (рис. 1) вектори а ° ІР ° показані праворуч і знизу від матриці.

    Для продовження процесу диференціації вершин і ребер введемо операцію попарного твори елементів двох векторів і позначимо її символом т. Е. X®Y = Z. Тут вектор Х = {х;}, вектор У = М, а елементи вектора Z = {z;} виходять в результаті твори, 1 = ху. Застосовуючи операцію ® для вектора а "і вектор-стовпця А матриці А, отримаємо вектор Р / = оІ®АР. Елементи вектора ^ 'будемо розглядати як значення сукупності з п характеристик По відношенню до дан-

    вим совокупностям можна застосувати функцію 5 (Р) і отримати вектор / '= {//}, елементи якого є кодовими числами р'ізряда чисел 1,2,., т. Вектор а? = {а /} отримаємо аналогічно як результат застосування операції ® для вектора / "івектор-рядків а; матриці а, а / = Р ° ®А ;, і виконання функції 5 (а) щодо векторів АМА / аД .-. а1). При виконанні функцій 5 (а) і 5Ф ) елементи векторів / і а'прінімаются неупорядкованими. Тому, два вектора а'і а1, є рівними, а 1 = АК1, якщо між їх елементами а'і а ^ 'мож-но встановити взаємно-однозначна відповідність так, що для всіх пар (а] 1, а] к1) справедливо Щ1 = а%.

    В якості вихідного вектора, з якого починається процес диференціації, можна використовувати як вектор а, так і Для визначеності будемо вважати, що перша ітерація виконується на основі характеристик вершин, т. Е. Вектор Р1 визначається на основі вектора а0. На цій ітерації при виконанні функції 5 (Р) можуть враховуватися кодові числа вектора Таким чином, процес диференціації на основі вихідного вектора а / = а "зводиться до послідовного виконання ітерацій / = 0,1,2,., Що реалізують рекуррентное правило, представлене такими виразами:

    8 (.Р)

    а ® А} = р + 1 +1,] = 1,2, ..., т;

    г (а)

    Р + 1 ®А = а {+1 +1, I = 1,2, ..., п.

    Процес диференціації вершин і ребер триває до тих пір, поки на деякій / -й ітерації вектор а = а-1 та, відповідно, Р / = Р / -1. Такі вектори будемо називати стійкими і позначати а 'і Отримання стійкого вектора відповідає двом ситуацій. У першій з них відбувається повна диференціація вершин, т. Е. Все вершини отримують різні кодові числа а /, іменовані інтегральними характеристиками. Друга ситуація відповідає неповної диференціації, коли деякі вершини мають однакові інтегральні характеристики. Сукупності вершин з однаковими інтегральними характеристиками названі однорідними групами. У загальному випадку вектори а * і / 'можуть містити по декілька однорідних груп.

    Вивчення властивостей однорідних груп і умов застосування методу диференціації вершин в цих групах вимагає окремого дослідження. У даній роботі основна увага зосереджена, безпосередньо, на методі диференціації та його застосуванні для вирішення завдання визначення ізоморфізму гіперграфів. Для більш глибокого розуміння методу спробуємо на змістовному рівні дати інтерпретацію процесу диференціації вершин і ребер гіперграфу. З цією метою розглянемо процес диференціації на прикладі гіперграфу, представленого матрицею інціденцій А на рис. 2. Приклад підібраний так, що вершини за влучним висловом а1 і ребра за влучним висловом р невиразні, т. Е. Число одиниць в рядках дорівнює чотирьом, а в стовпчиках -равно трьом. Відповідно всі елементи векторів а ° і / "рівні 1.

    Припустимо, що нам вдалося підібрати таку іншу характеристику а ,, по якій вершина д1 отримала унікальну характеристику (на рис. 2 позначена *), а характеристики всіх інших вершин залишилися невиразні. В цьому випадку вершині д1 присвоюється кодове число ап ° = 2, а у решти вершин зберігаються кодові числа а; ° = 1. Отриманий вектор а0іспользуется при диференціації в якості вихідного.

    Як випливає з рис. 2 для повної диференціації вершин і ребер знадобилося три ітерації, / * = 3. Записи а (Р0 і Р \ а / -1) вказують, що вектор а отриманий на основі вектора р / і, відповідно, Р на основі а-1. У дужках на рис. 2 наведені тільки ненульові елементи векторів а {і / р. Елементи перераховані без роздільників, т. К. В даному прикладі всі вони є однорозрядного числами.

    Процес диференціації в основному зводиться до виконання операцій ® і функцій 5 (а) і г (Р). Наприклад, ненульовим елементам вектора, отриманим в результаті виконання операції Р'®А; = А5) = (1212), функція? (А1) поставила у відповідність кодове число а5 '= 3, т. К. Вектору а1 селементамі (2211), т. е. А51 = а31, раніше вже було присвоєно кодову число а31 = 3.

    Повна диференціація, отримана в даному прикладі означає, що кожна вершина і ребро гіперграфу займає унікальне положення, яке фіксується відповідної інтегральної характеристикою (кодовою числом). Зауважимо, що в нашому прикладі характеристика ае для вершини д1 вносилася як деяка абстрактна величина, яка не відображає будь-яких структурних властивостей гіперграфу. Тому інтеграція відмінностей на всіх ітераціях диференціації могла фіксувати лише структурні відмінності відносин між вершинами і ребрами. Якщо все вершини і ребра розглядати як центри, щодо яких здійснюється інтеграція відмінностей, то кожна ітерація диференціації збільшує на одиницю радіус (глибину) охоплення вершин і ребер гіперграфу, залучених в інтеграцію разли-

    Мал. 2. Приклад диференціації вершин і ребер гіперграфу

    чий. Тому число ітерацій, як правило, не перевищує діаметр гіперграфу. Зокрема, наявність однорідних груп на ітерації / * свідчить про те, що всі вершини і ребра залучені в інтеграцію відмінностей, але цього виявилося недостатньо для повної диференціації.

    Алгоритм визначення ізоморфізму гіперграфів

    Для визначення ізоморфізму гіперграфах використовується викладений вище метод диференціації, що виконується одночасно (паралельно) в досліджуваній групі гіперграфів. Метод паралельної диференціації відрізняється тим, що при призначенні кодових чисел вектори а / (або Д) у всіх гіперграфах розглядаються спільно. Так, якщо на деякій / -й ітерації паралельної диференціації в двох графах Н1 = (01 ^ 1 ^ 1) і Н2 = (02 ^ 2 ^ 2) отримані вектори а / (Н1) = а / (Н2), то їм повинні бути призначені рівні кодові числа, т. е. а (Н) = а (щ.

    При виконанні паралельної диференціації один з гіперграфів (будь-який) приймається в якості ведучого, а всі інші відомими. Диференціація в провідному гіперграфах нічим не відрізняється від викладеного вище методу і представлена ​​на рис. 2. Призначення кодових чисел в ведених гіперграфах здійснюється з урахуванням призначених раніше кодових чисел в провідному гіперграфах. Якщо при виконанні чергової / -й ітерації вектор а1 (або вектор Д) веденого гіперграфу не збігається з вектором а! (Або ДО ведучого гіперграфу, то даний ведений гіперграф неізоморфен ведучому. Процес паралельної диференціації закінчується на ітерації / *. При цьому вектори а (і вектори Д) в ізоморфних гіперграфах повинні збігатися.

    Теорема. Два гіперграфу Н1 і Н2 є ізоморфними, якщо виконання в них паралельної диференціації призводить до повної диференціації вершин і ребер.

    Доведення. Якщо повна диференціація вершин і ребер гіперграфів Н1 і Н2 не досягається, то можливі дві ситуації завершення паралельної диференціації. У першій з них на ітерації / * вектори а * (Щ = а * (Н2) і Д * (Н1) = Д * (Н2) містять однорідні групи і в цьому випадку робити висновки про ізоморфізмі гіперграфів або його відсутності передчасно. Друга ситуація можлива на ітерації /, коли И (Н1) Фа / (Н2) або Д ^ ЩфД ^ Щ. Нерівність даних векторів можливо лише при розбіжності інціденторов F1 і F2 і, отже, гіперграфах Н1 і Н2 неізоморфних. З цього випливає необхідність повної диференціації.

    Покажемо достатність умови повної диференціації для ізоморфізму гіперграфів. Припустимо, що повна диференціація досягнута, а гіперграфах Н1 і Н2 не є ізоморфними. Зауважимо також, що перестановки рядків і стовпців в матриці А гіперграфу можна здійснювати незалежно один від одного, не порушуючи інцідентор F. Тому, якщо перенумерувати вершини і ребра в гіперграфах Н2 відповідно до кодовими числами векторів а '(Н2) і Д' (Н2 ) і впорядкувати рядки і стовпці в матриці А (Н2), то, враховуючи, що гіперграфах Н1 і Н2 неізоморфних, повинна виконуватися умова Л (Н1) ^ Л (Н2). Але це можливо тільки в разі, якщо мають місце нерівності а {(Щфа {(Н2) або ДД (ЩфД * (Н2), що суперечить умові про повну диференціації вершин і ребер. Теорема доведена.

    Алгоритм визначення ізоморфізму гіперграфів Н1 і Н2 заснований на затвердження теореми і реалізує метод паралельної диференціації вершин і ребер. Основні операції алгоритму зводяться до наступного.

    1. Для гіперграфів Н1 і Н2 за заданими характеристиками визначаються вектори а "і Д °. В якості ведучого приймається гіперграф Н1. Якщо по векторах а" і Д ° диференціація

    2.

    б)

    в)

    г)

    вершин і (або) ребер не відбувається, то виконується п. 3 алгоритму.

    Виконуються ітерації паралельної диференціації вершин і ребер гіперграфів Н1 і Н2. Після виконання черговий / -й ітерації аналізуються можливі ситуації: а) якщо вектори а / (Н1) = а / (Н2) і Р / (Н1) = Р / (Н2), то виконується наступна ітерація; якщо виконується одна з нерівностей аюан), ^ (ЩфУН), то в разі диференціації вершин однорідної групи відбувається перехід до п. 3, а в разі диференціації від векторів а ", фіксується, що гіперграфах Н1 і Н2 неізоморфних; якщо отримані стійкі вектори а (Н \) = а (Н2), Р "(Н1) = Р" (Н2), що містять однорідні групи, то відбувається перехід до п. 3;

    якщо досягнута повна диференціація вершин і ребер, то гіперграфах є ізоморфними і відбувається перехід до п. 4. Виконується диференціація вершин і ребер однорідної групи. З цією метою в гіперграф Н1 вводиться абстрактна характеристика, за якою однією з вершин однорідної групи присвоюється кодове число рівне максимальному елементу вектора а (Н1) збільшеному на одиницю. Дане кодове число послідовно присвоюється вершин відповідної однорідної групи в гіперграфах Н2 і після кожного присвоєння виконуються ітерації паралельного диференціювання відповідно до п. 2. 4. За векторах а (Н1) і а * (Н2) встановлюється відповідність вершин ізоморфних гіперграфів Н1 і Н2, а по векторах Р '(Щ і Р' (Н2) - відповідність ребер.

    Роботу алгоритму покажемо на прикладі, в якому гіперграф, представлений на рис. 2, приймемо в якості ведучого (Н1), а ведений гіперграф Н2 і процес його паралельної диференціації

    3

    представимо на рис. 3. Зауважимо, що відносно вихідних характеристик а1 і / 31 гіперграфах Н1 і Н2 є однорідними групами. Тому процес паралельної диференціації здійснюється з введенням абстрактної характеристики а для вершини д1 в гіперграфах Н1 (рис. 2) і послідовним присвоєнням цієї характеристики вершин гіперграфу Н2 (рис. 3). Необхідність послідовного присвоєння абстрактної характеристики є цілком очевидною і пояснюється тим, що ми не знаємо, яка вершина в однорідній групі гіперграфу Н2 відповідає вершині, якої було присвоєно абстрактна характеристика в однорідній групі гіперграфу Н1.

    З рис. 3 випливає, що присвоєння абстрактної характеристики вершин д1 і Д2 виявилися невдалими і призвели до ситуацій, які відповідають п. 2б алгоритму. На рис. 3 для векторів Д / Ю = (3,3,3) і аж) = (2ЛЛЛ) в провідному гіперграфах Н1 (рис. 2) не знайшлися аналоги. Ці ситуації на рис. 3 позначені знаком (?). Повна диференціація досягнута в результаті присвоєння абстрактної характеристики вершині Д3. Графи відповідності для вершин і ребер ізоморфних гіперграфів Н1 і Н2 наведені на рис. 2.

    Для досягнення повної диференціації в провідному гіперграфах Н1 треба було виконати 3 ітерації. Зокрема, при повному переборі матриць для даного прикладу розмірністю ПХТ = 6х8 треба було б порівнювати 6! Х8! = 29030400 варіантів матриць. З огляду на, що перевірці на ізоморфізм піддаються фрагменти графових моделей, їх розмірність, як правило, не перевищує кількох десятків вершин і ребер. Рішення задач з такою і більш високою розмірністю для запропонованого алгоритму не викликає ускладнень. Це випливає зі змісту основних обчислювальних процедур алгоритму і підтверджується можливістю його виконання навіть вручну для розмірностей в межах 10-15 вершин і ребер.

    3 = 1 2 3 4 5 6 7 8 «1 а0 а« Ж) «I« Ж) «> «ЧР1) а1 а2 (Р3) а а 3 (Р3) а3

    1-1 1 1 1 1 4 1 & 2 (1111) 1 1 (2221) 2 1 (2121) 3 (2131) 3 (6145) 5

    2 1 1 1 1 4 1 - 1 (2212) 2 2 (ІІ) 1 1 (1212) 3 (4213) 3 (7253) 3

    > II 1 1 1 1 4 1 - 1 (2121) 3 1 (1221) 3 2 (ІІ) 1 (4141) 1 (7185) 1

    1 1 1 1 4 1 - 1 (1222) 2 1 (2111)? 1 (2122) 2 (2423) 2 (6723) 4

    5 1 1 1 1 4 1 - 1 (1221) 3 1 (2122) 1 (2212) 2 (2243) 2 (6284) 2

    6 1 1 1 1 4 1 - 1 (1212) 3 1 (2221) 1 (1122) 3 (1433) 5 (1843) 6

    А 3 3 3 3 3 3 3 3

    1 1 1 1 1 1 1 1 Р р; ) Р; Р, РЧСО Р1 Р2 (а) Р2 Г (А2) р3

    .7 = 1 (211) 1 (123) 4 (1П) 2 (1П) 2 (322) 2 (422) 6

    2 (111) 2 (232) 2 (211) 1 (121) 1 (312) 4 (312) 7

    3 (111) 2 (223) 2 (211) 1 (111) 2 (322) 2 (322) 2

    4 (211) 1 (133) 1 (111) 2 (121) 1 (313) 1 (415) 1

    Н, 5 (111) 2 (333) 7 (111) 2 (211) 1 (123) 4 (12Ь) 8

    6 (211) 1 (133) (111) 2 (111) 2 (323) 3 (425) 4

    7 (211) 1 (123) (121) 1 (112) 1 (331) 1 (431) 5

    8 (111) 2 (223) (211) 1 (111) 2 (323) 3 (325) 3

    Мал. 3. Приклад паралельної диференціації вершин і ребер гіперграфу

    На закінчення відзначимо, що поряд з характеристиками структурного типу таких, наприклад, як а1, а2 і Д, Д2 в методі диференціації в якості вихідних можуть використовуватися показники, що відображають фізичні, хімічні, біологічні та інші властивості вершин і ребер гіперграфових моделей. Процес інтеграції відмінностей при введенні таких характеристик, як правило, призводить до повної диференціації за 1-2 ітерації. Тут важливо підкреслити, що використання даних характеристик слід розглядати як вимушений захід, пов'язану з необхідністю адекватного уявлення фрагментів розподілених систем у вигляді гіперграфових моделей і встановлення їх еквівалентності, а не з метою прискорення збіжності алгоритму.

    У зв'язку з можливістю введення таких характеристик слід зазначити ще одну важливу обставину. Для алгоритму основною перешкодою до досягнення повної диференціації вершин і ребер є наявність в гіперграфах однорідних груп. Раніше вже зазначалося, що однорідні групи, виявлені в процесі інтеграції відмінностей, вимагає окремого дослідження. Разом з тим однорідні групи в цих досліджень-

    СПИСОК ЛІТЕРАТУРИ

    1. Зиков А.А. Основи теорії графів. - М .: КомКнига, 2004. -644 с.

    2. Корнієнко А.В., Погрібний В.К. Модель і алгоритм розбиття схем обчислювальних пристроїв на функціональні блоки // Керуючі системи та машини. - 1976. - № 5. -С. 94-98.

    пах становлять інтерес не тільки з позиції розробки правил диференціації для вирішення завдання визначення ізоморфізму, а й з метою аналізу структурних властивостей графовой моделі в цілому.

    Задачу, пов'язану із застосуванням методу диференціації шляхом інтеграції відмінностей з метою виявлення і дослідження окремих труднооб-наружіваемих структурних властивостей, по відношенню до задачі визначення ізоморфізму можна розглядати як зворотну. Уже сам факт наявності однорідних груп і ефективного методу їх виділення може виявитися досить корисною основою для дослідження структурних особливостей графових моделей. При цьому немає підстав виключати і можливість того, що для самих різних додатків, що використовують графові моделі, метод диференціації вершин і ребер на основі інтеграції відмінностей, а також методи виділення і дослідження однорідних груп, можуть виявитися більш затребуваними, ніж рішення завдання визначення ізоморфізму.

    Робота виконана при проведенні НДР в рамках реалізації ФЦП «Наукові та науково-педагогічні кадри інноваційної Росії» 2009-2013 рр. Держконтракт № П2396.

    3. Погрібний В.К. Про один метод визначення ізоморфізму графів // Кібернетика. - 1982. - № 2. - С. 7-13.

    Надійшла 29.8.09.2010 г.


    Ключові слова: гіперграфовая модель / ізоморфізм гіперграфів / метод дифференцации вершин і ребер / метод паралельної дифференцации / інтеграція структурних характеристик / інтегральні характеристики вершин і ребер / in! tegration of structural characteristics / hypergraph model / isomorphism of hypergraphs / differentiation method of vertices and edges / method of parallel differentiation / integral characteristics of vertices and edges

    Завантажити оригінал статті:

    Завантажити