Задача Люка: відмінності між версіями

Причина, яка спонукала Тета вивчати завдання про подружні пари, прийшла зі спроб знайти повний список [[Вузол (математика)|математичних вузлів]] із заданим {{нп|[[Число перетинів (теорія вузлів)|числом перетинів|en|Crossing number (knot theory)}}]], скажімо, ''n''. У позначеннях Довкера для діаграм вузлів, ранню форму яких використовував Тет, ''2·n'' точок були перетинами вузла, які пронумеровані уздовж вузла числами від ''1'' до ''2·n''. У скороченій діаграмі дві мітки перетину не можуть бути послідовними числами, так що безліч пар міток на кожному перетині, використаних в позначеннях Довкера для позначення вузла, можна розуміти як зроблене парування в графі, що має в якості вершин числа від ''1'' до ''2·n'' і ребра між кожною парою чисел, що мають різну парність і не йдуть підряд по модулю ''2n''. Цей граф утворюється видаленням [[Гамільтонів цикл|Гамільтонового циклу]] (який з'єднує послідовні числа) з повного [[Двочастковий граф|дводольного графа]] (який з'єднує пари чисел з різною парністю). Таким чином, число парувань в такому графі дорівнює числу розсаджування. Для вузлів які чергуються цього парування досить для опису діаграми вузла. Для інших вузлів необхідно вказувати плюс або мінус для кожного перетину, щоб описати, яка з двох ниток перетину лежить зверху.