Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
ІЗОМОРФІЗМ ГРАФІВ
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Комп’ютерні науки
Кафедра:
Не вказано
Інформація про роботу
Рік:
2001
Тип роботи:
Інші
Предмет:
Системи автоматизованого проектування ЗВТ
Частина тексту файла (без зображень, графіків і формул):
МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА”
В.І.Каркульовський, С.П.Ткаченко, І.І.Чура,
ІЗОМОРФІЗМ ГРАФІВ
І Н С Т Р У К Ц І Я № 5
до лабораторної роботи
з курсу
“Дискретні моделі в САПР”
для базового напрямку 6.0804 “Комп’ютерні науки”
Затверджено:
на засіданні кафедри
“Системи автоматизованого провектування”
Протокол N 4 від 18. 10. 2001 р.
Львів – 2001
Ізоморфізм графів. Інструкція до лабораторної роботи №5 з курсу “Дискретні моделі в САПР” для студентів базового напрямку 6.08.04 “Комп’ютерні науки”. /Укл. В.І.Каркульовський, С.П.Ткаченко, І.І.Чура. -Львів: НУ ЛП, 2001р. -12с.
Укладачі: В.І.Каркульовський, канд.техн.наук, доц.,
С.П.Ткаченко, канд.техн.наук, доц.
І.І.Чура, канд.техн.наук, доц..
Відповідальний за випуск: І.І.Мотика, канд.техн.наук, доц.
Рецензенти: Стех Ю.В. , канд.техн.наук, доц.
Матвійків О.М. , канд.техн.наук, доц.
1. МЕТА РОБОТИ
Метою лабораторної роботи є вивчення і дослідження основних підходів до встановлення ізоморфізму графів.
2. ТЕОРЕТИЧНІ ВІДОМОСТІ
Теорія графів дає простий, доступний і потужній інструмент побудови моделей і рішення задач впорядкування взаємозвязаних обєктів. Нині є багато проблем де необхідно дослідити деякі складні системи з допомогою впорядкування їх елементів. До таких проблем відносяться і задачі ідентифікації в електричних схемах, в авіації, в органічній хімії і т.д. Вирішення таких проблем досягається з допомогою встановлення ізоморфізму графів.
Два графа G=(X,U,P) і G'=(X',U',P') називаються ізоморфними, якщо між їх вершинами, а також між їхніми ребрами можна встановити взаємно однозначне співвідношення X <-> X', U <-> U', що зберігає інцидентність, тобто таке, що для всякої пари (x,y)єX ребра u є U, що з'єднує їх, обов'язково існує пара (x',y') є X' і ребро u' є U', що з'єднує їх, і навпаки. Тут P - предикат, інцидентор графа G. Зауважимо, що відношення ізоморфізму графів рефлексивне, симетричне і транзитивне, тобто представляє собою еквівалентність.
На даний час існує досить детальна класифікація розроблених методів рішення такого типу задач /1/. Розглядаючи комбінаторно-логічну природу вказаної задачі можна всі роботи в цьому напрямку розділити на дві групи:
рішення теоретичної задачі встановлення ізоморфізму простих графів;
розробка наближених методів, які найбільш повно враховують обмеження і специфіку задачі з застосуванням характерних ознак об’єкту дослідження.
До першої групи відносяться алгоритми: повного перебору і почергового “підвішування” графів за вершини.
а) Одним з найпростіших з точки зору програмної реалізації, є алгоритм перевірки ізоморфізму графів повним перебором(можливої перенумерації вершин), але складність цього алгоритму є факторіальною.
б) Почергове “підвішування” графів за вершини (всі ребра зрівноважені).
Суть цього алгоритму полягає в знаходженні однакових “підвішаних” графів (за довільні вершини), ізоморфність яких визначаємо. При чому в одному з графів почергово змінюється вершина за яку він “підвішується”. Ізоморфізм графів визначається по їх матрицях суміжності, які формуються по однотипних правилах:
індекс в матриці вершини за яку закріплений (“підвішаний”) граф рівний одиниці;
кортеж вершин в матриці визначається рівнями сусідів;
кортеж вершин в межах кожного рівня сусідів визначається степінню вершини, а також кількістю ребер над нею і нижче її.
Для графа G( рис.1) представлені різні варіанти його “підвіски” рис.2
Рис. 1
Рис.2.
Роботи першої групи рідко використовуються для розробки безпосередньо алгоритмів рішення задачі ідентифікації, але вони дозволяють дати оцінку обчислювальної складності алгоритмів її рішення, які відносяться до задач зі складним рішенням (NP - повні задачі), складність алгоритмів яких є експоненціальною і в деяких випадках сягає О(N!), (N - кількість вершин), тому доводиться відмовлятись від спроб досягнути точними методами їх рішення.
Наближені алгоритми використовують або допустимі рішення точних методів, або побудованні на використанні евристичних прийомів. На даний час створена певна кількість алгоритмів встановлення ізоморфізму графів, які за рахунок різних евристичних прийомів знижують складність задачі від факториальної до степеневої функції/2/. Серед них можна виділити наступні:
в) Метод побудови оптимального коду графа.
Цей метод базується на алгоритмі формування еквівалентних матриць зв'язності щляхом ідентифікації вершин з однаковими топологічними характеристиками /3/. Згідно цього алгоритму перетворюються матриці зв'язності графів однотипними методами. У випадку, коли модифіковані матриці однакові графи ізоморфні. Ізоморфізм між двома чи більше графами може бути визначений при допомозі використання їхніх оптимальних кодів. Оптимальний код графу отримується з верхнього трикутника матриці суміжності після перенумерації вершин графа/4/.
Згідно з методом побудови оптимального коду графа здійснюється перенумерація вершин графів, які досліджуються на ізоморфізм. Перенумерація вершин графа відбувається по певних вибраних критеріях оцінки вершин графу. Оцінка здійснюється по їх числових значеннях, які використовуються при формуванні оптимального коду графа.
Число U. Число U кожного першого сусіда j деякої даної вершини i є кількість вершин, які є першими сусідами сусіда j, а також першими сусідами вершини i. Для графа на рис. 3 Uij=3.
Рис. 3
Число MW. Число MW вершини i є найбільше з всіх U чисел сусідів вершини i.
MWi = max Uij
Число VN. Нехай вершина j є сусідом деякої взятої вершини i з максимальним числом U. Число VN вершини i є степінь вершини j.
VNi = val j (Uij -> max).
Число Bd (0 < d). Число Bd якоїсь непозначеної вершини j є число, яке вказує мінімальну відстань між вершиною j та позначеною вершиною Ad, де
1 <= d <= остання позначена вершина.
Число C. Число C сусіда j позначеної вершини i показує кількість сусідів вершини j, які зв'язані з сусідами вершини i. Для графа на рис. 4 Cij=3.
Рис. 4
Дані критерії можуть бути використані для рішення задачі встановлення ізоморфізму графів як регулярних (в яких всі вершини мають рівну степінь), так і нерегулярних.
Опишемо алгоритм побудови оптимального коду ненаправленого нерегулярного графа. Даний алгоритм використовує представлення графів у вигляді матриці суміжності MSUM=[mij] та матриці найменшої відстані MNV = [aij]. Матриця найменшої відстані графу G з P вершинами є P*P матриця, в якій aij показує довжину найменшого шляху від вершини i до вершини j.
Алгоритм побудови оптимального коду графа представлений такими процедурами:
1. Будуємо матрицю суміжності MSUM(N*N) та матрицю найменшої відстані MNV(N*N) для графу G (N,L), де N - кількість вершин в графі, а L - кількість зв'язків між вершинами. Приймаємо k = 1.
2. З головної діагоналі матриці найменшої відстані MNV знаходимо вершину (вершини) найбільшої степені. Якщо є єдина вершина з найбільшою степенню, то позначаємо її як Ak та переходимо на 10-й крок. В противному випадку (якщо маємо більше ніж одну вершину з найбільшою степенню) переходимо на 3-й крок.
3. Нехай, скажемо, є j вершин з найбільшою степенню (M1,M2,...,Mj). Для кожної вершини знаходимо число MW. Якщо є єдина вершина з найбільшим числом MW, то позначеємо цю вершину як Ak та переходимо на 10-й крок. Якщо маємо більше, ніж одну вершину з найбільшим числом MW, то переходимо на 4-й крок.
4. Нехай є j вершин з найбільшим числом MW (M1,M2,...,Mj). Для кожної вершини знаходимо число VN. Якщо є єдина вершина з найбільшим числом VN, то позначимо цю вершину як Ak та переходимо на 10-й крок. Якщо є більше ніж одна вершина з найбільшим числом VN, то переходимо на 5-й крок.
5. Нехай маємо i вершин з найбільшим числом VN(M1,M2,...,Mi). На даному етапі ми не можемо виділити з I вершин одну кращу вершину на місце Ak. Всі I вершин є можливими претендентами на Ak, отже ми повинні тепер виконувати процедури пошуку наступних вершин для I можливих претендентів на Ak, поки та чи інша єдина вершина не стане кращою виборкою для Ak, або поки не завершиться алгоритм. Переходимо на 10-й крок.
6. Знаходимо число B1 для всіх непозначених сусідів вершини Aq (визначення подано на 11-тому кроці). Якщо є єдина вершина, яка має найменше число B1, то позначаємо її як Ak та переходимо на 10-й крок. В противному випадку підраховуємо числа Bd (2 <= d <= k-1) для тих вершин, які мають мінімальне число Bd-1. Якщо знайдена єдина вершина з найменшим числом Bd, то позначаємо цю вершину як Ak та переходимо на 10-й крок. Якщо є більше ніж одна вершина з найменшим числом Bd, та якщо d = k-1, то перейти на 7-й крок. Якщо d < k-1, то збільшити d на одиницю та повторити обчислення.
7. Підраховуємо число U для кожних перших ссусідів вершини Aq, що мають найменше число Bd. Якщо є єдина вершина з найбільшим числом U, то позначити цю вершину як Ak та перейти на 10-й крок. В противному випадку переходимо на 8-й крок.
8. Обчислюємо степінь кожного першого непозначеного сусіда Aq, який має найменше число Bd та найбільше число U. Якщо є єдина вершина з найбільшою степенню, то позначити цю вершину як Ak та перейти на 10-й крок. В противному разі перейти на 9-й крок.
9. Підраховуємо число C для кожного першого сусіда Aq, який має найменше число Bd та найбільші число U і степінь. Якщо є єдина вершина з з найбільшим числом C то позначаємо цю вершину як Ak та переходимо на 10-й крок. Нехай, скажемо, є L вершин з найбільшим числом C (M1,M2,...,Ml). Тоді всі ці L вершин є претендентами на Ak, отже ми повинні тепер викрнувати процедури пошуку наступних вершин для L можливих претендентів на Ak. Переходимо на 10-й крок.
10. Якщо k = 1, то перейти на 11-й крок. Якщо є тільки одна виборка для Ak-1, то перейти на 11-й крок. Припустимо що є P виборок для Ak-1. Якщо вершина Ak не позначена для всіх виборок, то визначаємо Aq та переходимо на 6-й крок для позначення Ak для ще одніє] виборки Ak-1 (порядок не важливий). В противному випадку для кожно] виборки виводимо числа Bd, число U, степінь та число c вершин, позначених як Ak у вигляді підкодів. Найкращими варіантами є підкоди з найменшими числами Bd та найбільшим числом U, степенню та числом C. Припустимо, що тільки R підходів є оптимальними. Далі ми будемо розглядати тільки ці підкоди. Переходимо на 11-й крок, щоб призначити Ak+1 для вершин Ak, що залишились.
11. Приймаємо k = k+1. Якщо k = N, то переходимо на 12-й крок. Якщо k = N, то знаходимо Aq, де Aq - вже позначена вершина з найнижчим індексом, яка має принаймні одного непозначеного першого сусіда. Якщо Aq має тільки одного непозначеного першого сусіда, то призначити цього сусіда як Ak та перейти на 10-й крок. Якщо Aq має більше, ніж одного непозначеного першого сусіда, то перейти на 6-й крок.
12. Коли k=N, то вершина, яка залишається непозначеною, позначається як Ak для всіх виборок Ak-1. Якщо ми маємо P виборок, то тепер будуємо P оптимальних кодів. Якщо ці коди не є тотожніми, то код з найбільшою вагою вибирається як оптимальний код графа.
Поза тим обчислювальна складність такого алгоритму залишається досить високою, як правило не менше О(N5)/5/.
б) З використанням згортки графа.
В наш час створена велика кількість алгоритмів встановлення ізоморфізму графів, які за рахунок різних евристичних прийомів знижують складність задачі від фактoріальної (експоненціальної) до степеневої функції. Тим не менш обчислювальна складність цих алгоритмів залишається досить високою, як правило не менше O(N5), або ж її можна знизити ще на 1-2 порядки для графів, що мають якісь специфічні властивості.
Враховуючи характер задачі встановлення ізоморфізму графів, а вона є як складною комбінаторно-логічною задачею, так і задачею розпізнавання, для її рішення можна з успіхом використати метод паралельного згортання (редукції) схем /6/. При цьому можна отримати алгоритми, придатні для встановлення ізоморфізму графів (гіперграфів) любих видів, що мають обчислювальну складність, яка визначається базовим алгоритмом і не перевищує, відповідно, O(N3). Алгоритми базуються на двох наслідках з теорем, доведених в /7/. Вони носять евристичний характер і знаходять підстановку ізоморфізма для двох графів (гіперграфів), якщо ізоморфізм існує, і не знаходять її, якщо він відсутній.
В силу своєї евристичності при встановленні ізоморфізму нерегулярних ізоморфних графів (гіперграфів), які мають деякі регулярні вершини з однаковим ступенем, відповідна підстановка може бути не знайдена з огляду на відсутність повного перебору можливих варіантів згортки. Інакше можна прийти до схеми методу гілок та границь із відповідною обчислювальною складністю. Для рішення задачі використовується модифікація алгоритму /8/ з нарощуванням по “динамічному “ образу.
В процесі пошуку рішення задачі проходить паралельне нарощування ізоморфних підграфів (кусків), що знаходиться у повній відповідальності із гіпотезою Ілама /9/. При цьому на нульовому кроці роботи алгоритму необхідно провести класифікацію вершин графів по їх степеням, що допомагає при згортці графів і утворенні в процесі редукції нових кусків належним чином ранжувати зовнішні ребра цих кусків. В якості критеріїв згортки для одного з графів (обраного у якості образу) можна використати любий з відомих критеріїв (наприклад, cij max, де сij – елемент матриці зв’язності C) або їх комбінацію адитивну чи мультиплікативну, чи з ранжуванням до можливого усунення невизначеності редукції. Для іншого графа критерієм оптимальної редукції буде утворення кусків (підграфів), ізоморфних образу на даному кроці редукції. Інакше кажучи, повинні будуватись в процесі рішення задачі тотожні (ізоморфні) дерева паралельної редакції /6/ для двох досліджуваних графів (еквівалентні зображення).
Для зменшення ймовірності виникнення невизначеностей в процесі редукції її слід з першого кроку зробити направленою (примусовою), використовуючи в якості обов’язкових “центрів кристалізації” (зародків по критерію сij max) вершини того класу, який має для графу-образа мінімальну потужність. Попередньою необхідною умовою рішення задачі буде співпадіння на нульовому кроці потужностей відповідних класів вершин, які мають однакові степені.
Таким чином, існує два варіанта створення подібних алгоритмів. Це утворення динамічного образа з примусовою “кристалізацією” (з наперед визначеними одновершинними “зародками” – кусками), а також зі свобідною редукцією образа по наперед обраних критеріях (напр., ( = max сij , ( = min (cI + cj - 2cij), де ( - основний, а ( – додатковий критерій згортки, і т.д.).
В любому випадку спочатку робиться крок паралельної згортки на графі-образі, а потім еквівалентий йому крок на іншому графі, ізофорфізм з яким досліджується. Причому тут реалізується принцип зворотнього зв’язку, тобто, наприклад, у випадку примусового нарощення в графі-образі розглядаються по черзі всі зовнішні ребра кожного нарощуваного куска, якщо це необхідно для знаходження еквівалентного йому зв’язку (ребра) в іншому графі.
Неможливість побудови на якомусь кроці для двох досліджуваних на ізоморфізм графів тотожніх дерев паралельної редукції свідчит про відсутність ізоморфізма або неможливість його встановлення даним алгоритмом .
Згідно з /7/ код, тобто вага відповідної вершини дерева оптимальної (паралельної) редукції, порівняння пар кусків (вершин), які можуть об’єднатись у процесі редукції повинен містити наступні впорядковані характеристики:
комбінацію класів вершин (кусків);
кількість вершин (кусків), що об’єднуються інцидентних ребрам, які стають внутрішніми при об’єднанні;
кількість спільних ребер для кусків, що об’єднуються;
кортеж класів вершин, інцидентних спільним ребрам;
кількість зовнішніх ребер утворююваного куска;
кортеж класів вершин, інцидентних зовнішнім ребрам утворюваного куска.
Для гіперграфів характерні будуть також “змішані” ребра, в зв’яку з чим з’являться ще дві характеристики в ході порівняння, аналогічні чотирьом останнім з описаних вище. Зауважимо, що формування коду простіше в тому випадку, коли процес редукції є направленим, тобто тоді, коли проходить паралельна редукція графів з обмеженою кількістю “зародків” у вигляді наперед визначених вершин.
В роботі /10/ код був доповнений характеристиками:
7) кількість паралельно-суміжних вершин, по типам(рис.5, типи вершин C i E є різні);
Рис.5
8) кількість трьохвершинних циклів(рис.6, для вершини А кількість рівна трьом), що включають дану вершину;
Рис.6.
9) кількість чотирьохвершинних циклів(рис.7., для вершини А кількість рівна двом), що включають дану вершину;
Рис.7
Отже можна зробити висновок, що серед існуючих методів визначення ізоморфізму їх редукція, що відображається бінарним деревом, дозволяє звести встановлення ізоморфізму до встановлення тотожності інформаційних кодів графів, а запропоновані характеристики інформаційного коду вершини(куска або підграфа) графа в більшості випадків дозволяють ідентифікувати вершини(куски або підграфи) для вирішення задачі покриття.
КОНТРОЛЬНІ ЗАПИТАННЯ
Які Ви знаєте алгоритми рішення задачі встановлення ізоморфізму графів?
Як вирішується теоретична задача встановлення ізоморфізму простих графів?
Яка ідея рішення задачі встановлення ізоморфізму наближеними методами?
Які основні кроки алгоритму побудови оптимального коду ненаправленого нерегулярного графа?
Яка сутність методів згортки(редукції) графа?
4. ЛАБОРАТОРНЕ ЗАВДАННЯ
Отримати у викладача індивідуальне завдання.
Підготувати вхідне завдання на ЕОМ за зразком описаним в інструкції для роботи з учбовою програмою DIP. Подальші пункти повторити для різних методів.
Запустити на виконання програму відповідного методу.
Проглянути результат роботи програм. Результат роботи може бути: ізоморфізм встановлено або не встановлено.
У випадку, коли ізоморфізм встановлено (не встановлено), необхідно модифікувати граф, коректуючи два або три зв’язки, щоб знайти такий граф, на якому ізоморфізм не встановлюється (встановлюється).
Зафіксувати результати роботи у викладача.
Оформити і захистити звіт.
5. ЗМІСТ ЗВІТУ
Опис методів рішення задачі комівояжера.
Нарисувати графи і вхідні дані, що їх описують для двох результатів.
Результати розрахунків.
Висновки.
6. ЛІТЕРАТУРА
Руссо, Вольф. Машинно-ориентированный метод разбиения и отображения графов логических схем ЭВМ. В кн.: Автоматизация в проектировании. М.: Мир, 1972.
134, Оцуки Т. Эвристические алгоритмы для комбинаторных задач с большим обьемом вычислений."Дэнси цусим гакайси", 1975,58, N4, с.416-423.
Оре О. Графы и их применение. М., "Мир", 1965.
Карелин В.П., Миронов Б.Н. Алгоритм направленного случайного поиска для распознавания изоморфного вложения графов на автоматной модели. В кн.:Однородные цифровые вычислительные и интегрирующие структуры, вып.6. Таганрог, ТРТИ,1976, с.84-93.
Горинштейн Л.Л. Метод упорядоченного перебора для разрезания графов. Таганрог, ТРТИ, 1970.
Базилевич Р.П., Ткаченко С.П. Решение задачи методом параллелього свертивания. В кн.: Вычислительная техника,VII, Каунас, КПИ, 1975, с. 295-298.
Ткаченко С.П. Разработка и исследование алгоритмических методов решения задач декомпозиции для использования в автоматизированных системах конструкторского проектирования. Диссертация на соискание ученой степени кандидата технических наук. Львов, ЛПИ, 1980.
Ткаченко С.П. и др. Поиск в схеме подсхем с заданными характеристиками. В сб.: Автоматизация проектирования радиоэлектронной аппаратуры на промышленных предприятиях. Киев, РДЭНТП 1976.
Харари Ф. Теория графов. М; “Мир”, 1973, 302 с.
Павлів О.О., Ткаченко С.П Чура І.І. Методика перевірки відповідності спроектованої топології МЕП вхідній ПС.Вісник Державного університету “Львівська політехніка” № 322 ”Комп’ютерна іженерія та інформаційні технології”. -Львів, 1994р.
Додаткова література:
Абукаримов Р.Т. Алгоритмы распознавания, основанные на поиске признаков классов."Вопросы кибернентики", вып. 88, 1976, с.3-20.
Асельдеpов З.М., Г.А.Донец. Пpедставление гpафов и востановление гpафов . - Киев, Наук. думка, 1991, - 192с.
Асельдеpов З.М.и др. Пpедставление гpафов и опеpации над ними. - Киев, 1987, - 18с.
Кохов В.А., Лазарев В.А. Алгоритм идентификации обыкновеных графов. -"Тр. Моск. энерг.ин-та", 1976, вып.299, с.53-60.
Курейчик В.М., Королев А.Г. Применение алгоритма изоморфизма графов для контроля схем БИС. - Микроэлектроника, 1976, т.5, вып 5, с.400.
Курейчик В.М., Королев А.Г. Об одном методе изоморфного вложения графов. В кн.: Методы расчета и автоматизации проектирования устройств микроэлектронных ЦВМ. Киев, ИК АН УССР, 1975, с.6-16.
Мелихов А.Н., Курейчик В.М., Королев А.Г. Решение задач контроля при техническом проектировании на основе распознавания изоморфизма графов. В кн.:Вычислительная техника, IX, Каунас, КПИ, 1977, с.139-141.
НАВЧАЛЬНЕ ВИДАННЯ
ІЗОМОРФІЗМ ГРАФІВ
І Н С Т Р У К Ц І Я
до лабораторної роботи № 5
з курсу
“Дискретні моделі в САПР”
для базового напрямку 6.0804 “Комп’ютерні науки”
Укладачі: Володимир Іванович Каркульовський
Сергій Петрович Ткаченко
Ігор Іванович Чура
Редактор
17.07.2020 15:07-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора