300000
22772
11746
English | Français | فارسی | 中文 | Українська | Azerbaijani | ខ្មែរ | Tiếng Việt | Bahasa Melayu | Deutsch | O'zbek | Русский
11746
Окраска узлов
Если вас интересует только то, как решить эту задачу, а не теория, лежащая в ее основе, то перейдите к разделу «Какие подсказки для поиска расцветки методом проб и ошибок?»
Об инвариантах
Две из следующих трех диаграмм
могут деформироваться друг в друга, не разрезая линию узла.
Примером инварианта является минимальное число пересечений, которое может иметь любая из бесконечно многих эквивалентных диаграмм. Этот инвариант трудно найти, потому что невозможно проверить бесконечное количество диаграмм.
Но каким может быть инвариант, который может быть вычислен для данной диаграммы? Трудно представить, какое свойство не изменяется при деформации, когда диаграмму можно деформировать как угодно.
Трехцветность является инвариантом.
N-окрашиваемость
Развязать узел
Тузун-Сикора
8_19
могут деформироваться друг в друга, не разрезая линию узла.
Как вы думаете, какие они?
Ниже вы узнаете, как использовать цветовость, чтобы определить, принадлежат ли две диаграммы к разным узлам. Исследуя трехцветность, можно было увидеть, какие диаграммы точно нельзя деформировать друг в друга.
В противном случае следующая последовательность показывает, как упростить диаграмму Тузуна-Сикоры до круга.
Доказательство того, что диаграмма Тузуна-Сикоры является развязываемым узлом.
Диаграмма развязывания и диаграмма Тузуна-Сикоры вместе с бесконечно многими другими деформациями принадлежат к одному и тому же математическому узлу, в данном случае к узлу. Как можно решить, что две диаграммы никогда не могут быть деформированы друг в друга, независимо от того, насколько большими они становятся между ними? Свойство, которое не изменяется при деформации диаграммы, называется «инвариантным» (неизменяющимся).В противном случае следующая последовательность показывает, как упростить диаграмму Тузуна-Сикоры до круга.
Доказательство того, что диаграмма Тузуна-Сикоры является развязываемым узлом.
Первоначальная проекция
Ход Reidemeister 3
После переезда и растяжки
Переход с уменьшением прохода
После переезда и растяжки
Переход с уменьшением прохода
После переезда и растяжки
Переход с уменьшением прохода
После переезда и растяжки
Переход с уменьшением прохода
После переезда и растяжки
Переход с уменьшением прохода
После переезда
Переход с уменьшением прохода
После переезда
Ход Reidemeister 2
После переезда
A Reidemeister 1 ход
После переезда
A Reidemeister 1 ход
После переезда
A Reidemeister 1 ход
После переезда
A Reidemeister 1 ход
После переезда
Примером инварианта является минимальное число пересечений, которое может иметь любая из бесконечно многих эквивалентных диаграмм. Этот инвариант трудно найти, потому что невозможно проверить бесконечное количество диаграмм.
Но каким может быть инвариант, который может быть вычислен для данной диаграммы? Трудно представить, какое свойство не изменяется при деформации, когда диаграмму можно деформировать как угодно.
Трехцветность является инвариантом.
Чтобы объяснить это, мы используем нити, которые являются частями линии узла, которые можно нарисовать, не поднимая пера. На каждом переправе встречаются 3 нити, по одной эстакада и по одной с каждой стороны. Диаграмма узлов является трехцветной, если каждой пряди можно придать один из 3 цветов, так что при каждом скрещивании у нас будет либо 1, либо 3 цвета, а не 2 цвета. Раскрашивание всех одним цветом всегда возможно и не считается. Как минимум 2 цвета должны быть где-то использованы.
Какая из 3 диаграмм является трехцветной?
Распущенный узел имеет только одну прядь и поэтому не поддается тройному окрашиванию. 2-й узел поддается деформации до развязывания и поэтому также не поддается окрашиванию. Мы докажем это позже. Другой узел является трехцветным и поэтому никогда не может быть деформирован до развязывания, как показано выше.
Триокрашиваемость является слабым инвариантом, потому что она содержит лишь минимально возможное количество информации, только «да/нет». Этот инвариант способен только разделить все узлы на две группы: узлы трехцветные и неразноцветные.
N-окрашиваемость
Более сильным инвариантом является N-Colorability, при котором доступно N цветов, и каждый цвет представляет одно из чисел 0,1,2,3,...,N-1. Условие, которое должно выполняться при каждом скрещивании, состоит в том, что сумма цветов 2 нижних прядей минус в 2 раза больше цвета верхней нити, кратна N. Другими словами, если цветами являются a,b,c, то должен существовать множитель k, такой, что a+b-2c = kN. Математически эквивалентная, но более распространенная формулировка — a + b ≡ 2c mod N. Это означает, что обе стороны знака ≡ оставляют одинаковый остаток при делении через N. Работая по модулю (mod) некоторое число называется Модулярной Арифметикой и имеет массу интересных и полезных правил.
Возникает много вопросов.
Возникает много вопросов.
Введение в модулярную арифметику
Мы можем доказать все утверждения модулярной арифметики, введя множитель k и переформулировав ≡ уравнение как обычное уравнение. Для сокращения нотации мы используем
'integer' для 'целого числа',
'pq' для 'p умножить на q',
«∃» вместо «Существуют»,
':' для 'со свойством', и
«A → B» вместо «из A следует B».
Докажите: если a ≡ b mod N и c ≡ d mod N, то (a+c) ≡ (b+d) mod N
Модульное уравнение a ≡ b mod N говорит, что a и b различаются только на кратное p.
Т.е. должен существовать множитель m со свойством, что a = B + MP. В краткой нотации это
(a ≡ b mod N) → (∃ целое число m: a = b + mp)
(c ≡ d mod N) → (∃ целое число n: c = d + np)
Сложив оба уравнения, мы получим a + c = b + mp + d + np = b + d + (m+n)p
→ a + c ≡ (b + d) mod N
Т.е. должен существовать множитель m со свойством, что a = B + MP. В краткой нотации это
(a ≡ b mod N) → (∃ целое число m: a = b + mp)
(c ≡ d mod N) → (∃ целое число n: c = d + np)
Сложив оба уравнения, мы получим a + c = b + mp + d + np = b + d + (m+n)p
→ a + c ≡ (b + d) mod N
Докажем: если a ≡ b mod N, то для любого целого m у нас есть ma ≡ mb mod N
(a ≡ b mod N) → (∃ целое число k: a = b + kN)
После умножения на m получаем
ma = mb + mkN
→ ma ≡ mb mod N
После умножения на m получаем
ma = mb + mkN
→ ma ≡ mb mod N
Доказательство: если a ≡ b mod (PQ), то a ≡ b mod P.
a ≡ b mod (PQ)
→ ∃ целое число k: a = b + k(PQ)
→ a = b + (kQ)P
→ a ≡ b mod P
А как насчет обратного направления?
Почему правдоподобно, что обратное не верно?
→ ∃ целое число k: a = b + k(PQ)
→ a = b + (kQ)P
→ a ≡ b mod P
А как насчет обратного направления?
Вот контрпример:
6 ≡ 1 mod 5 но
6 ≢ 1 mod 15, потому что 6 и 1 не отличаются кратно 15.
6 ≡ 1 mod 5 но
6 ≢ 1 mod 15, потому что 6 и 1 не отличаются кратно 15.
Почему правдоподобно, что обратное не верно?
В уравнении mod N обе стороны от ≡ могут иметь N разных значений. В уравнении mod (NM) обе стороны от ≡ могут иметь разные значения NM. Следовательно, отношение mod (NM) несет больше информации, чем отношение mod N. Отбросить информацию, перейдя от mod (NM) к mod N, легко, но обратное создание информации из ничего невозможно. Грубо говоря, в этом смысле нормальное равенство с использованием = эквивалентно ≡ mod ∞(бесконечность).
В качестве побочного комментария, это открывает возможность того, что в приложениях, где решение включает целые числа и где кто-то ищет решение в форме уравнения с использованием '=' и где известно, что существует верхняя граница для абсолютного значения чисел в решении, стратегия может заключаться в том, чтобы начать с поиска решения mod N для некоторого малого простого числа N, а затем вычислить тождество mod N^2, затем mod N^4 и так далее, пока степень N не станет больше верхней границы, известной для решения, и тогда можно отбросить mod и получить точное решение, используя = .
Такой метод, называемый подъемом Гензеля , может быть использован для разложения одномерных многочленов сначала относительно некоторого малого простого числа, а затем, наконец, точно над целыми числами.
Доказать: a + b ≡ ((a mod N) + (b mod N)) mod N
a и мод N отличаются кратностью N: a = (мод N) + pN
b и b mod N отличаются кратно N: b = (b mod N) + qN
→ a + b = (a mod N) + (b mod N) + (p + q)N
→ a + b ≡ ((a mod N) + (b mod N)) mod N
b и b mod N отличаются кратно N: b = (b mod N) + qN
→ a + b = (a mod N) + (b mod N) + (p + q)N
→ a + b ≡ ((a mod N) + (b mod N)) mod N
Доказать: ab ≡ ((a mod N)(b mod N)) mod N
a и мод N отличаются кратностью N: a = (мод N) + pN
b и b mod N отличаются кратно N: b = (b mod N) + qN
→ ab = ((a mod N) + pN)((b mod N) + qN)
= (a mod N)(b mod N) + [(a mod N)q + (b mod N)p + pqN]N
→ ab ≡ (a mod N)(b mod N) mod N
b и b mod N отличаются кратно N: b = (b mod N) + qN
→ ab = ((a mod N) + pN)((b mod N) + qN)
= (a mod N)(b mod N) + [(a mod N)q + (b mod N)p + pqN]N
→ ab ≡ (a mod N)(b mod N) mod N
Докажите: если P(x,y,...) является многочленом в переменных x,y,... тогда P(x,y,...) ≡ P((x mod N),(y mod N),...) mod N
Каждый полином может быть записан как сумма произведений, поэтому применение двух вышеприведенных правил многократно доказывает это утверждение.
Докажите: В модулярной арифметике по модулю простое число, деление на целые дает снова целые числа.
Начнем с того, что покажем, что для простого числа p и любого целого числа a ≢ 0 mod N, обратное 1/a mod N также является целым числом. Нам требуется ≢ 0 mod N, потому что и в модулярной арифметике деление на ноль невозможно.
Пусть u будет u ≡ 1/a mod N. для вас быть инверсией мода N это значит
ua ≡ 1 мод N
→ ∃ целое число k: ua = 1 + kp
Это имеет форму тождества Безу: ua + vp = GCD(a,p), где GCD(a,p) — Наибольший общий делитель a,p, а где v=-k. Поскольку p является простым числом, а a не кратным p, следовательно GCD(a,p)=1.
Множители u,v в тождестве Безу могут быть вычислены с помощью расширенного алгоритма Евклида, и оба, u,v, являются целыми числами.
если you=1/a — целочисленный mod N, то b/a = bu — это также целочисленный mod N, который должен был быть показан.
Пример: 1/3 ≡ 5 mod 7, потому что 1 = 3(1/3) ≡ 3(5) = 15 = 2(7) + 1 ≡ 1 mod 7.
Когда ma ≡ mb mod N эквивалентен a ≡ b mod N?
Мы видели, что из ≡ b mod N следует ma ≡ mb mod N. Мы имеем эквивалентность, если можем умножить на целое число k ≡ 1/m mod N. Это означает, что после умножения на m существует целое число l, такое, что mk = 1 + lN, которое тождество Безу с 1 = GCD(m,N) (Большой общий делитель m,N), поэтому m и N должны быть взаимно простыми для эквивалента ma ≡ mb mod N и a ≡ b mod N.
Китайская теорема об остатке.
Ранее мы говорили об информационном наполнении модульного уравнения модификацией N для зависимости от N. Не следует ли объединить два модулярных уравнения с меньшими модульными числами в одно с большим числом?
Об этом говорится в китайской теореме о напоминаниях.
Если для двух уравнений
x ≡мод N1
x ≡мод 2 N2
делители N1,N 2 являются взаимно простыми, тогда существует ровно одно значение для x с точностью до кратных p1p2 , которое удовлетворяет обоим модулярным уравнениям.
Один из способов получить решение состоит в том, чтобы использовать расширенный евклидов алгоритм для решения тождества Безу m1N1 + m2N2 = 1 путем вычисления m1,m 2 , а затем использовать формулу
x =a 1m2N2 + a2m1M1
a1(1 - m1N1) + a2m1N1
=a 1 + (a2 - a1)m1N1
который показывает x ≡a 1 mod N1 и эквивалентно x = a2 + (a1 - a2)m2N2 , который показывает x ≡a 2 modN 2.
Если имеется более двух модулярных уравнений, то можно многократно заменять два из них одним, пока не будет получено решение в виде одного модулярного уравнения. При каждой замене новое число делителя увеличивается, становясь произведением двух делителей объединенных уравнений.
Об этом говорится в китайской теореме о напоминаниях.
Если для двух уравнений
x ≡мод N1
x ≡мод 2 N2
делители N1,N 2 являются взаимно простыми, тогда существует ровно одно значение для x с точностью до кратных p1p2 , которое удовлетворяет обоим модулярным уравнениям.
Один из способов получить решение состоит в том, чтобы использовать расширенный евклидов алгоритм для решения тождества Безу m1N1 + m2N2 = 1 путем вычисления m1,m 2 , а затем использовать формулу
x =a 1m2N2 + a2m1M1
a1(1 - m1N1) + a2m1N1
=a 1 + (a2 - a1)m1N1
который показывает x ≡a 1 mod N1 и эквивалентно x = a2 + (a1 - a2)m2N2 , который показывает x ≡a 2 modN 2.
Если имеется более двух модулярных уравнений, то можно многократно заменять два из них одним, пока не будет получено решение в виде одного модулярного уравнения. При каждой замене новое число делителя увеличивается, становясь произведением двух делителей объединенных уравнений.
Как можно доказать, что N-окрашиваемость является инвариантом?
Как объяснялось ранее в разделе Развязываем пищу для размышлений > Введение с определениями > ходов Рейдемейстера, 3 ходов Рейдемейстера достаточно для выполнения любой деформации диаграммы узла. Следовательно, чтобы быть инвариантным, нужно только показать, что свойство не изменяется под этими 3 ходами.
Как можно показать, что Reidemeister, который я перемещаю, не меняет окраску?
Если цвета прядей A и B, как указано, то условие окрашивания требует на левом рисунке A + B ≡ 2B mod N, а на правом рисунке B + A ≡ 2A mod N. В обоих случаях B = A является решением:
Это означает, что выполнение Reidemeister, которое я перемещаю, не изменяет цветовость.
Как можно показать, что ход Reidemeister II не меняет цветовость?
Если цвета прядей являются A, B и C, как указано, то C однозначно определяется из условия B + C ≡ 2A mod N на левом рисунке так C ≡ (2A - B mod N) и на правом рисунке A + C ≡ 2B mod N so C ≡ (2B - A mod N). Это определяет цвет новой пряди при выполнении движения Reidemeister II. На окрашиваемость это не влияет.
Как можно показать, что ход Reidemeister III не меняет цветовость?
Если цвета прядей A, B, C, D, E, F и G, как указано, то три условия слева следующие:
A + D ≡ 2C mod N
E + F ≡ 2D мод N
F + B ≡ 2C mod N .
При устранении внутренней нити F состояние на наружных прядях равно
2D - E ≡ 2C - B mod N, который с помощью A + D ≡ 2C mod N упрощает до
2D - E ≡ A + D - B mod N и, таким образом, A - B - D + E ≡ 0 mod N.
3 условия справа:
E + G ≡ 2C mod N
G + B ≡ 2A mod N
A + D ≡ 2C mod N
При устранении внутренней пряди G состояние наружных прядей равно
2C - E ≡ 2A - B mod N, который с помощью 2C ≡ A + D mod N упрощает до
A + D - E ≡ 2A - B mod N и, таким образом, 0 ≡ A - B - D + E mod N.
F и G вычисляются из любого из соотношений, в которых они появляются.
Сделан вывод, что для обеих диаграмм условия по цветам наружных прядей одинаковы: A + D ≡ 2C mod N и A - B - D + E ≡ 0 mod N.
Следовательно, либо обе диаграммы имеют раскраску, либо ни одна из них не имеет раскраски, и, следовательно, раскрашиваемость инвариантна при движениях Рейдемейстера III.
Как можно показать, что Reidemeister, который я перемещаю, не меняет окраску?
Если цвета прядей A и B, как указано, то условие окрашивания требует на левом рисунке A + B ≡ 2B mod N, а на правом рисунке B + A ≡ 2A mod N. В обоих случаях B = A является решением:
Это означает, что выполнение Reidemeister, которое я перемещаю, не изменяет цветовость.
Как можно показать, что ход Reidemeister II не меняет цветовость?
Если цвета прядей являются A, B и C, как указано, то C однозначно определяется из условия B + C ≡ 2A mod N на левом рисунке так C ≡ (2A - B mod N) и на правом рисунке A + C ≡ 2B mod N so C ≡ (2B - A mod N). Это определяет цвет новой пряди при выполнении движения Reidemeister II. На окрашиваемость это не влияет.
Как можно показать, что ход Reidemeister III не меняет цветовость?
Если цвета прядей A, B, C, D, E, F и G, как указано, то три условия слева следующие:
A + D ≡ 2C mod N
E + F ≡ 2D мод N
F + B ≡ 2C mod N .
При устранении внутренней нити F состояние на наружных прядях равно
2D - E ≡ 2C - B mod N, который с помощью A + D ≡ 2C mod N упрощает до
2D - E ≡ A + D - B mod N и, таким образом, A - B - D + E ≡ 0 mod N.
3 условия справа:
E + G ≡ 2C mod N
G + B ≡ 2A mod N
A + D ≡ 2C mod N
При устранении внутренней пряди G состояние наружных прядей равно
2C - E ≡ 2A - B mod N, который с помощью 2C ≡ A + D mod N упрощает до
A + D - E ≡ 2A - B mod N и, таким образом, 0 ≡ A - B - D + E mod N.
F и G вычисляются из любого из соотношений, в которых они появляются.
Сделан вывод, что для обеих диаграмм условия по цветам наружных прядей одинаковы: A + D ≡ 2C mod N и A - B - D + E ≡ 0 mod N.
Следовательно, либо обе диаграммы имеют раскраску, либо ни одна из них не имеет раскраски, и, следовательно, раскрашиваемость инвариантна при движениях Рейдемейстера III.
Тривиальность, эквивалентность и независимость колорита
Если у нас есть одна расцветка, то какие другие раскраски можно получить из нее для любой диаграммы узлов?
Каждое из условий окраски имеет вид A + B ≡ 2C mod N. Запишем это как A - C ≡ C - B mod N.
1) При добавлении к каждому цвету одной и той же константы, скажем, S, то различия не меняются:
(А+С) - (С+С) = А - С + С - С = А - С и
(C+S) - (B+S) = C - B + S - S = C - B и
Таким образом, условия по-прежнему соблюдаются.
2) Ранее мы видели как правило модулярной арифметики, что мы можем умножить обе части ≡ с числом, совместным с N и получить эквивалентное решение системы уравнений и, таким образом, эквивалентную раскраску.
1) При добавлении к каждому цвету одной и той же константы, скажем, S, то различия не меняются:
(А+С) - (С+С) = А - С + С - С = А - С и
(C+S) - (B+S) = C - B + S - S = C - B и
Таким образом, условия по-прежнему соблюдаются.
2) Ранее мы видели как правило модулярной арифметики, что мы можем умножить обе части ≡ с числом, совместным с N и получить эквивалентное решение системы уравнений и, таким образом, эквивалентную раскраску.
Имеет ли смысл мод на цветостойкость 2?
Нет, для N=2 раскраска тривиальна.
Начнем с нити цвета А, которая продолжается как цепь В после пересечения под первой эстакадой цвета С. Затем A,B,C связаны через A + B ≡ 2C mod 2 и после добавления B к обеим сторонам A ≡ B mod 2, потому что 2B ≡ 2C ≡ 0 mod 2. Продолжая это рассуждение на всех скрещиваниях, следует, что все нити имеют либо четный цвет (0), либо нечетный цвет (1). Это дает тривиальную раскраску.
Начнем с нити цвета А, которая продолжается как цепь В после пересечения под первой эстакадой цвета С. Затем A,B,C связаны через A + B ≡ 2C mod 2 и после добавления B к обеим сторонам A ≡ B mod 2, потому что 2B ≡ 2C ≡ 0 mod 2. Продолжая это рассуждение на всех скрещиваниях, следует, что все нити имеют либо четный цвет (0), либо нечетный цвет (1). Это дает тривиальную раскраску.
А как насчет мода цветности (2N), т.е. по модулю четного числа?
Выше мы видели, что либо все цвета четные, либо нечетные. Если они четные, то мы можем разделить их все на 2 и получить без потери информации мод раскраски N. Если они все нечетные, то мы можем добавить 1 ко всем цветам и получить эквивалентную раскраску, где теперь все цвета четные, поэтому мы можем отбросить коэффициент 2 и получить эквивалентный мод раскраски N.
Как следствие, каждый мод раскраски (2N) эквивалентен моду цвета N.
Как следствие, каждый мод раскраски (2N) эквивалентен моду цвета N.
Для какого N N-окрашиваемость полезна и не тривиальна?
Для нечетных N>1 имеет значение мод цветучести N.
Достаточно ли знать все раскраски mod P и mod Q, где P и Q являются совместными, чтобы знать все раскраски mod (PQ)?
Если N является составным числом, т.е. произведением, в котором оба делителя не равны 1, то можно записать его как N=PQ, где P и Q являются сопростыми. Имея решение условий окрашивания mod N, мы получаем цветовую модификацию P путем вычисления всех цветовых значений mod P, и она дает нам цветовую модификацию Q, вычисляя все цветовые значения mod Q. Но как насчет другого направления? Если система условий раскрашивания для диаграммы узлов имеет решение mod P и другое решение mod Q, где P и Q являются совместными, имеет ли эта система условий решение mod PQ?
Ответ: Да.
Доказательство:
Пустьa 1, a2 — цвета одной нити в расцветках mod P и mod Q.
Таким образом, китайская теорема об остатке гарантирует существование и единственность одного целого числа A mod PQ, удовлетворяющего обоим условиям
A ≡ a1 mod P
A ≡ a2 mod Q.
Это можно повторить для каждой нити, задав значения цвета A,B,C,... mod PQ.
При каждом скрещивании два условия окраски
(A + B - 2C) mod P = a1 + b1 - 2c1 ≡ 0 mod P
(A + B - 2C) mod Q = a2 + b2 - 2c2 ≡ 0 mod Q
остались довольны. Единственное значение (A + B - 2C) mod PQ, которое равно нулю mod P и равно нулю mod Q, - это A + B - 2C ≡ 0 mod PQ. Это показывает, что цветовые значения A,B,C,... предусмотреть раскрашивание мода PQ.
Поскольку все положительные целые числа имеют разложение на простые множители, они могут быть записаны как произведения степеней простых чисел. Таким образом, можно найти все раскрашивающие числа, исследуя только все степени всех нечетных простых чисел как раскрашивающие числа. Ранее мы видели, что простое число 2 и степени 2 не являются возможными раскрашивающими числами.
Кто-то начинает проверять существование раскраски по модулю некоторого простого числа, а в случае успеха повторяет проверку с все более высокими степенями этого простого числа до тех пор, пока кулуринг больше не существует.
Ответ: Да.
Доказательство:
Пустьa 1, a2 — цвета одной нити в расцветках mod P и mod Q.
Таким образом, китайская теорема об остатке гарантирует существование и единственность одного целого числа A mod PQ, удовлетворяющего обоим условиям
A ≡ a1 mod P
A ≡ a2 mod Q.
Это можно повторить для каждой нити, задав значения цвета A,B,C,... mod PQ.
При каждом скрещивании два условия окраски
(A + B - 2C) mod P = a1 + b1 - 2c1 ≡ 0 mod P
(A + B - 2C) mod Q = a2 + b2 - 2c2 ≡ 0 mod Q
остались довольны. Единственное значение (A + B - 2C) mod PQ, которое равно нулю mod P и равно нулю mod Q, - это A + B - 2C ≡ 0 mod PQ. Это показывает, что цветовые значения A,B,C,... предусмотреть раскрашивание мода PQ.
Поскольку все положительные целые числа имеют разложение на простые множители, они могут быть записаны как произведения степеней простых чисел. Таким образом, можно найти все раскрашивающие числа, исследуя только все степени всех нечетных простых чисел как раскрашивающие числа. Ранее мы видели, что простое число 2 и степени 2 не являются возможными раскрашивающими числами.
Кто-то начинает проверять существование раскраски по модулю некоторого простого числа, а в случае успеха повторяет проверку с все более высокими степенями этого простого числа до тех пор, пока кулуринг больше не существует.
Какие есть подсказки по поиску окраски методом проб и ошибок?
Какой букве следует присвоить значение?
- Чтобы решить, какую прядь раскрасить следующей, нажмите клавишу Enter, чтобы отсортировать уравнения по количеству букв, т.е. по срочности.
- Если уравнение состоит из нескольких букв, то выберите одну, которая встречается в большинстве других уравнений, чтобы большее количество уравнений упрощалось при назначении числа. Аналогично, наведите курсор мыши на уравнение, посмотрите на обведенный перекресток и на этом пересечении кликните на той неокрашенной нити, которая имеет больше всего эстакад.
- Буквы справа от ≡ вычисляются быстрее, чем буквы слева. Чтобы вычислить букву слева, нужно разделить на 2, что может потребовать прибавления N справа, чтобы стать четным. Это не сложно, но в конкурсе время дорого. По той же причине, угадывая значение буквы, можно взять букву слева от ≡.
- Для экономии времени не беспокойтесь о вычислении значений в интервале 0..N−1. Значения могут быть отрицательными или произвольно большими. Если они верны, то фиолетовое уравнение становится зеленым, и это все, что имеет значение.
- Если в уравнении осталась только одна буква, то фон фиолетовый, и тогда выбора нет, значение нужно вычислить, чтобы уравнение стало зеленым. Примеры смотрите в инструкции.
- Как показано выше в Этот раздел > «Если у кого-то одна окраска...» , значения всех букв могут быть сдвинуты на одно и то же постоянное значение. Следовательно, самой первой букве, которую нужно присвоить, можно присвоить значение 0 без потери общности. Никто не будет пытаться использовать какое-либо другое значение для этой буквы, потому что всегда можно сдвинуть это значение в ноль.
- Для того, чтобы 2-я буква стала цветной, нужно рассмотреть только два случая: 1) она имеет то же значение, что и первая буква, т.е. 0, и 2) она имеет другое значение. В этом случае нужно учитывать только 1, потому что мы видели, что все числа можно умножить на 2. (Н-1) (где N — простое число доступных цветов) и все еще имеют эквивалентное решение. Пожалуйста, справьтесь с этой задачей Этот раздел > «Если у кого-то одна окраска...». Например, если N=5 и кто-то попробовал бы другое значение для 2-й присвоенной буквы, например, 3, и получил решение, то умножение этого значения (и всех остальных значений) на 2 дало бы 3 к 3×2 = 6 ≡ 1 мод 5 до 1. Следовательно, 2-ю букву нужно только попробовать как 0 и 1.
- Испытания – это тоже вопрос времени. Можно сэкономить время, вводя отрицательные числа, когда их вычисления выполняются быстрее, чем положительные. Интерфейсу не нужны цифры в диапазоне 0..N-1.
- Когда уравнение становится красным, то условие ≡ не выполняется и необходимо изменить хотя бы одно число. Затем попробуйте другое число. Чтобы не пропустить числа, можно было попробовать номера в порядке 0,1,...,N-1 и остановиться при обнаружении раскраски.
- При возврате назад нажатием кнопки отмены, если вы видите фиолетовое уравнение, вы можете нажать кнопку отмены снова, не задумываясь. Причина в том, что фиолетовое уравнение имеет только одну букву, и для этой буквы существует только одно возможное значение (mod N), поэтому для этой буквы в данной ситуации не нужно пробовать другое значение.
- Чтобы систематически искать и не упустить ни одной возможности раскраски, можно начать с присвоения каждой переменной значения 0, которое дает тривиальное решение, а затем начать возвращаться назад, чтобы получить нетривиальное решение.
- Диаграммы узлов, используемые в этой игре, имеют уже минимальное количество пересечений. Но если диаграммы не будут минимальными, то было бы выгодно сначала их упростить. Без описанных выше методов ускорения пришлось бы попробовать раскраски NC , где N - количество цветов, а C - количество скрещиваний = количество прядей. Уменьшение числа пересечений всего на 1 снижает усилие в РАЗЫ N.
Есть ли узлы, которые нельзя окрашивать?
Да. Узлы с менее чем 12 пересечениями, которые не имеют окраски, это 10124, 10153, 11н34, 11н42, 11н49, 11н116 и, конечно же, узел. На рисунке представлена схема узла 10124.
Диаграмма с надписью «Тузун-Сикора» в верхней части страницы является лишь одной из бесконечного множества диаграмм развязывания, поэтому ее также нельзя раскрасить.
Диаграмма с надписью «Тузун-Сикора» в верхней части страницы является лишь одной из бесконечного множества диаграмм развязывания, поэтому ее также нельзя раскрасить.
Существуют ли еще больше цветовых инвариантов и как их можно вычислить?
Да, эти дополнительные инварианты представляют собой кратности решений, одну кратность для каждого количества доступных цветов. Чтобы понять следующие комментарии, полезно знание линейной алгебры.
Если диаграмма узлов имеет пересечения C, то она также имеет нити C, и, таким образом, система условий имеет матрицу коэффициентов C×C, где каждая строка представляет собой пересечение и состоит либо из двух -1 и одного 2, либо из +1 и -1 (пересечение петли Рейдемейстера I). Каждый столбец соответствует нити и имеет столько двойок, сколько у нити эстакад и либо два -1, либо один -1 и один +1.
Условия образуют однородную линейную систему (правая часть содержит только 0) и вопрос состоит в том, чтобы найти раскраски чисел по модулю, какие существуют нетривиальные линейные независимые решения (раскраски).
Как и в линейной алгебре, матрица приводится в диагональную форму путем перестановки строк и добавления кратных строк к другим строкам. Кроме того, эти действия также выполняются с помощью столбцов. Что здесь не разрешено, так это умножение строк и столбцов на число, потому что это добавило бы цветовое число по модулю, где определитель матрицы был бы равен нулю, и это добавило бы дополнительную раскраску. Вместо этого мы постоянно выбираем 2 ненулевые компоненты столбца/строки, скажем, A,B, чтобы использовать расширенный алгоритм Евклида для нахождения p,q, удовлетворяющего pA + qB = GCD(A,B). p,q — множители двух строк/столбцов. После перестановки строк/столбцов GCD(A,B) становится диагональным элементом. В результате получается диагональная матрица, называемая нормальной формой Смита, где обычно верхний левый угол начинается с 1, за которыми следуют числа, каждое из которых является делителем следующего числа в диагонали. Последний диагональный элемент равен нулю, так как диаграмма каждого узла позволяет тривиально раскрасить одним цветом. Следовательно, достаточно вычислить нормальную форму Смита после отбрасывания любого столбца и любой строки.
Вычисление определителя матрицы коэффициентов C×C дает ноль, потому что сумма столбцов равна нулю. Вычисление определителя после отбрасывания одной строки и одного столбца дает одно число, которое является произведением чисел по диагонали нормальной формы Смита. Таким образом, нормальная форма Смита дает больше информации примерно при тех же усилиях.
Пример: Для этой диаграммы с 83 пересечениями матрица коэффициентов имеет размер 83×83.
Нормальная форма Смита имеет диагональ, начинающуюся в верхнем левом углу с 79 умноженными на 1, за которыми следуют 3, 3, 85837301265 (= 3 x 5 x 5722486751), 0. Это означает, что есть три независимых 3-раскраски и одна 85837301265-раскраска, что означает, что у нее также есть 5-расцветка, 15-расцветка, 3x5722486751-раскраска и 5x5722486751-раскраска.
Если диаграмма не имеет раскраски, то все диагональные номера равны 1, за исключением 0 в последней позиции.
Следующая схема относится к узлу 12а801.
Нормальная форма Смита (SNF) имеет в диагонали девять 1, за которыми следует 3,45,0. В этом виде каждое число является делителем на следующее диагональное число. А кратность раскраски — это количество диагональных элементов, в которых она встречается как фактор. Таким образом, каждая диаграмма этого узла имеет две независимые 3-расцветки и одну 45-расцветку, что подразумевает, что она также имеет одну 5-,9-,15-расцветку.
Если диаграмма узлов имеет пересечения C, то она также имеет нити C, и, таким образом, система условий имеет матрицу коэффициентов C×C, где каждая строка представляет собой пересечение и состоит либо из двух -1 и одного 2, либо из +1 и -1 (пересечение петли Рейдемейстера I). Каждый столбец соответствует нити и имеет столько двойок, сколько у нити эстакад и либо два -1, либо один -1 и один +1.
Условия образуют однородную линейную систему (правая часть содержит только 0) и вопрос состоит в том, чтобы найти раскраски чисел по модулю, какие существуют нетривиальные линейные независимые решения (раскраски).
Как и в линейной алгебре, матрица приводится в диагональную форму путем перестановки строк и добавления кратных строк к другим строкам. Кроме того, эти действия также выполняются с помощью столбцов. Что здесь не разрешено, так это умножение строк и столбцов на число, потому что это добавило бы цветовое число по модулю, где определитель матрицы был бы равен нулю, и это добавило бы дополнительную раскраску. Вместо этого мы постоянно выбираем 2 ненулевые компоненты столбца/строки, скажем, A,B, чтобы использовать расширенный алгоритм Евклида для нахождения p,q, удовлетворяющего pA + qB = GCD(A,B). p,q — множители двух строк/столбцов. После перестановки строк/столбцов GCD(A,B) становится диагональным элементом. В результате получается диагональная матрица, называемая нормальной формой Смита, где обычно верхний левый угол начинается с 1, за которыми следуют числа, каждое из которых является делителем следующего числа в диагонали. Последний диагональный элемент равен нулю, так как диаграмма каждого узла позволяет тривиально раскрасить одним цветом. Следовательно, достаточно вычислить нормальную форму Смита после отбрасывания любого столбца и любой строки.
Вычисление определителя матрицы коэффициентов C×C дает ноль, потому что сумма столбцов равна нулю. Вычисление определителя после отбрасывания одной строки и одного столбца дает одно число, которое является произведением чисел по диагонали нормальной формы Смита. Таким образом, нормальная форма Смита дает больше информации примерно при тех же усилиях.
Пример: Для этой диаграммы с 83 пересечениями матрица коэффициентов имеет размер 83×83.
Нормальная форма Смита имеет диагональ, начинающуюся в верхнем левом углу с 79 умноженными на 1, за которыми следуют 3, 3, 85837301265 (= 3 x 5 x 5722486751), 0. Это означает, что есть три независимых 3-раскраски и одна 85837301265-раскраска, что означает, что у нее также есть 5-расцветка, 15-расцветка, 3x5722486751-раскраска и 5x5722486751-раскраска.
Если диаграмма не имеет раскраски, то все диагональные номера равны 1, за исключением 0 в последней позиции.
Следующая схема относится к узлу 12а801.
Нормальная форма Смита (SNF) имеет в диагонали девять 1, за которыми следует 3,45,0. В этом виде каждое число является делителем на следующее диагональное число. А кратность раскраски — это количество диагональных элементов, в которых она встречается как фактор. Таким образом, каждая диаграмма этого узла имеет две независимые 3-расцветки и одну 45-расцветку, что подразумевает, что она также имеет одну 5-,9-,15-расцветку.
Статистика окраски узлов
Есть ли обзор возможных расцветок простых узлов до определенного размера?
В текстовом файле
https://cariboutests.com/qi/knots/colour3-15-N.txt для каждого узла с номером пересечения ≦ 15 перечислены все записи нормальной формы Смита, которые не равны 0 или 1. Эти числа были вычислены по одной диаграмме, но они инвариантны и, следовательно, одинаковы при вычислении по любой диаграмме этого узла. Если вам нравятся изображения цветных узлов, то вы можете скачать плакат из нашей коллекции плакатов, нажав на главную страницу «Главная» > «Плакаты», ведущие к https://cariboutests.com/images/posters/knot_colouring_portrait.pdf.
Насколько сильна N-раскраска как инвариант?
В следующей таблице показано, как использование большего количества инвариантов раскраски увеличивает количество инвариантов классов узлов и, таким образом, уменьшает среднее количество узлов в классе. Правый столбец показывает, как (#cr - 3)'й корень из числа инвариантных классов окраски остается примерно постоянным, где #cr - количество пересечений узлов.
Таблица 1: Статистика по цветовым инвариантам
# из cr: # из пересечений
# из kn: # из узлов
# из cl1: # классов при рассмотрении только списка простых раскрасок чисел
# из cl2: # классов при рассмотрении только списка кратностей простых раскрасочных чисел
# из cl3: # классов при рассмотрении списка записей Smith Normal Form Entry <> 1
ABS: exp(ln(noofcl3[cr])/(cr-3))
= (cr-3)-й корень из (# из cl3)
Таблица 1: Статистика по цветовым инвариантам
# из cr: # из пересечений
# из kn: # из узлов
# из cl1: # классов при рассмотрении только списка простых раскрасок чисел
# из cl2: # классов при рассмотрении только списка кратностей простых раскрасочных чисел
# из cl3: # классов при рассмотрении списка записей Smith Normal Form Entry <> 1
ABS: exp(ln(noofcl3[cr])/(cr-3))
= (cr-3)-й корень из (# из cl3)
| # из cr | # из kn | # из cl1 | кн/кл1 | # из cl2 | кн/кл2 | # из cl3 | КН/КЛ3 | АБС ↑ |
|---|---|---|---|---|---|---|---|---|
| 3 | 1 | 1 | 1.00 | 1 | 1.00 | 1 | 1.00 | |
| 4 | 1 | 1 | 1.00 | 1 | 1.00 | 1 | 1.00 | 1.000 |
| 5 | 2 | 2 | 1.00 | 2 | 1.00 | 2 | 1.00 | 1.414 |
| 6 | 3 | 3 | 1.00 | 3 | 1.00 | 3 | 1.00 | 1.442 |
| 7 | 7 | 7 | 1.00 | 7 | 1.00 | 7 | 1.00 | 1.627 |
| 8 | 21 | 13 | 1.62 | 14 | 1.50 | 16 | 1.31 | 1.741 |
| 9 | 49 | 25 | 1.96 | 29 | 1.69 | 33 | 1.48 | 1.791 |
| 10 | 165 | 47 | 3.51 | 53 | 3.11 | 62 | 2.66 | 1.803 |
| 11 | 552 | 81 | 6.81 | 93 | 5.94 | 116 | 4.76 | 1.812 |
| 12 | 2176 | 136 | 16.00 | 162 | 13.43 | 203 | 10.72 | 1.805 |
| 13 | 9988 | 234 | 42.68 | 271 | 36.86 | 342 | 29.20 | 1.792 |
| 14 | 46972 | 409 | 114.85 | 488 | 96.25 | 623 | 75.40 | 1.795 |
| 15 | 253293 | 722 | 350.82 | 855 | 296.25 | 1100 | 230.27 | 1.792 |
Как наибольшее число окраски для узлов с пересечением C зависит от C?
Если взять все узлы с числом пересечения C (max),<16) and finds from these knots the one with the highest colouring number N то из следующей таблицы видно, что Nmax увеличивается примерно в 1,7 раза при увеличении C на 1.
Таблица 2: Таблица B(C) = Nmax1/(C−1)
Таблица 2: Таблица B(C) = Nmax1/(C−1)
| C | Nмакс. | узел | В(С) |
|---|---|---|---|
| 3 | 3 | 31 | 1.732 |
| 4 | 5 | 41 | 1.710 |
| 5 | 7 | 52 | 1.627 |
| 6 | 13 | 63 | 1.670 |
| 7 | 19 | 76 | 1.634 |
| 8 | 37 | 817 | 1.675 |
| 9 | 61 | 933 | 1.672 |
| 10 | 109 | 10115 | 1.684 |
| 11 | 199 | 11a301 | 1.698 |
| 12 | 353 | 12a1188 | 1.705 |
| 13 | 593 | 13a4620 | 1.703 |
| 14 | 1103 | 14a16476 | 1.714 |
| 15 | 1823 | 15a65606 | 1.710 |
Существует ли компьютерная программа, которая может вычислять раскраски?
AsciiKnots — компьютерная программа для вычисления всех раскрашиваемых чисел для заданного узла путем вычисления нормальной формы Смита матрицы коэффициентов. Если диаграмма узлов не имеет слишком большого количества пересечений, то она также вычисляет путем оптимизированного метода проб и ошибок поиск для заданного числа раскраски всех раскрасок или всех номеров раскраски, включая их расцветки.Помимо раскрашивания, программа может вычислить гораздо больше. Его можно скачать с сайта
https://cariboutests.com/games/knots/AsciiKnots.tar.gz. AsciiKnots runs под linux. Строгие пользователи Windows могут бесплатно установить Ubuntu linux в качестве приложения под Windows 10. Команды Linux для удаления старых загруженных версий, для скачивания последней версии, для ее распаковки и запуска
rm AsciiKnots.tar.gz
wget https://cariboutests.com/games/knots/AsciiKnots.tar.gz
tar xfz AsciiKnots.tar.gz
./AsciiKnots
Ограниченная функциональность раскрашивания также доступна на https://cariboutests.com/games/knots/knoteditor/ после выбора «Инструменты» > «Цветной узел»
Ссылки
[1] Р. Х. Фокс, Метациклические инварианты узлов и связей, Canadian Journal of Mathematics 22 (1970) 193−201.
[2] Я. Х. Пшитыцкий, 3-раскраска и другие элементарные инварианты узлов. Banach Center Publications, Vol. 42, "Knot Theory", Warszawa, 1998, 275−295.
[3] Д. Рольфсен, Таблица узлов и звеньев. Приложение С в узлах и звеньях. Уилмингтон, Германия: Публикуй или погибай Пресс, стр. 280-287, 1976.
[4] Д. К. Ча и К. Ливингстон, KnotInfo: Таблица инвариантов узлов, http://www. indiana.edu/~knotinfo
[5] "Классификация по окраске узлов с числом перекрещивания до 15", https:// cariboutests.com/qi/knots/colour3-15.txt
[6] Т. Вольф, «Верстак с узлом», https://cariboutests.com/games/knots/AsciiKnots.tar.gz
[2] Я. Х. Пшитыцкий, 3-раскраска и другие элементарные инварианты узлов. Banach Center Publications, Vol. 42, "Knot Theory", Warszawa, 1998, 275−295.
[3] Д. Рольфсен, Таблица узлов и звеньев. Приложение С в узлах и звеньях. Уилмингтон, Германия: Публикуй или погибай Пресс, стр. 280-287, 1976.
[4] Д. К. Ча и К. Ливингстон, KnotInfo: Таблица инвариантов узлов, http://www. indiana.edu/~knotinfo
[5] "Классификация по окраске узлов с числом перекрещивания до 15", https:// cariboutests.com/qi/knots/colour3-15.txt
[6] Т. Вольф, «Верстак с узлом», https://cariboutests.com/games/knots/AsciiKnots.tar.gz
Следите за обновлениями или подписывайтесь на них: