Проблема розбиття графа на ізоморфні підграфи
Loading...
Date
2022
Authors
Брагiнець, Дмитро
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
З’ясовано типові методи пошуку ізоморфного підграфа для графа що можна розбити на дві частини. Тривіальний метод обходу за правою стороною лабіринту, чи методи перерозподілу клітин по рядкам і стовпчикам – "перетікання" не спрацьовують. Для пошуку ізоморфних підграфів при діленні на дві частини необхідно аналізувати зовнішний контур породженого поліміно, та задавати відповідний контур при діленні навпіл. Для знаходження підграфів більшої кількості (3+) необхідно проводити окремі дослідження. Емпіричний метод дає ясно зрозуміти, що складність пошуку підграфа посилюється не зі збільшенням розмірності вузлів-вершин, себто габаритами породженого поліміно, а кількості ізоморфних підграфів, які утворюють граф.
Description
Keywords
ізоморфний граф, Crazy Cut, правило правої руки, медіанне перетікання зубців, курсова робота