Іновативний підхід до вирішення впертої та дуже важливої задачі у теорії графів — математичної теорії мереж вершин та їх взаємозв'язків — може сигналізувати про перший серйозний прогрес у цій сфері за понад 30 років.
Лашло Бабай, математик та комп'ютерний теоретик з Чиказького університету в Іллінойсі, описав цей метод під час математичної конференції минулого тижня. А тепер деталі з'являються від математиків, які її відвідали.
“Раптом був зроблений неочікуваний та гігантський прорив”, — вважає комп'ютерний науковець з Чиказького університету Стюарт Курц.
У своїй доповіді вчений сформулював аргумент, який демонструє, що проблема ізоморфізму графів, тобто визначення, чи два графи ідентичні між собою, може бути вирішена набагато швидше, ніж досі вважали.
Графи — це відносно прості математичні об'єкти, абстрактні репрезентації мереж, які часто з'являються у фізиці, хімії та комп'ютерних науках. В їх основі лежать вершини (nodes) та зв'язки між ними, тобто їх можна зобразити як сукупність точок, сполучених лініями. Проблема ізоморфізму графів запитує, чи два графи ідентичні, не дивлячись на те, як вони накреслені чи як названі їх вершини.
За словами Яноша Саймона, комп'ютерного теоретика з Чиказького університету, проблема може здаватися простою, але насправді продуктивні підходи до її вирішення не створювалися з 1983 р.
У комп'ютерних науках часто постає питання про складність алгоритму, тобто кільки потрібно часу, щоб він розв'язав проблему або довів, що розв'язок правильний. За цим критеріям комп'ютерні проблеми часто класифікують на P — ті, які можна швидко вирішити — та NP, які мають розв'язок, який можна швидко перевірити, але не обов'язково швидко знайти. Ізоморфізм графів відносять до NP, що містить низку проблем, які, як вірять, потребують багато часу для свого вирішення.
Найпростіший спосіб порівняти два графи — це просто поміняти назви їх вершин та шукати співпадіння. Це — дуже неефективна процедура. Однак завжди існувало переконання, що є простіший спосіб. Метод Лашло Бабая запроваджує алгоритм, який працює набагато швидше, ніж попередні підходи, хоча не настільки швидко, щоб ізоморфізм графів віднести до групи проблем Р.
В його основі лежить нова процедура успішного вирішення проблеми через сукупність послідовних стадій. Кожна стадія успішно спрощує проблему, не лише обмежуючи кількість вершин, які потрібно взяти до уваги через зменшення кількості перестановок, але й віднаходячи окремі симетричні ділянки, названі графом Джонсона, що ховаються всередині досліджуваних графів. Алгоритм працює рекурсивно: кожна стадія розпадається на один-три ходи. Він працює доти, доки графи не розпадаються на прості ділянки, які можна порівняти через просте співставлення.
Хоча результат викликав велике зацікавлення серед теоретиків, він навряд чи матиме значні практичні наслідки. Адже вже існують досить швидкі алгоритми, які можуть встановити, чи чимало графів є ізоморфними, хоча й немає математичного доказу, що вони такі ж швидкі, як і метод Бабая, для усіх пар графів.
Chris Cesare
Graph-theory breakthrough tantalizes mathematicians
Nature, 19/11/2015
Зреферував Євген Ланюк