300000
29238
14067
English | Français | فارسی | 中文 | Українська | Azerbaijani | ខ្មែរ | Tiếng Việt | Bahasa Melayu | Deutsch | O'zbek | Русский
14067
Забарвлення вузлів
Якщо вас тільки цікавить, як вирішити цю проблему, а не теорія, що стоїть за нею, перейдіть до «Які підказки для пошуку забарвлення методом проб і помилок?»
Про інваріанти
Дві з наступних трьох діаграм
можуть деформуватися один в одного, не розрізаючи лінію вузла.
Прикладом інваріанта є мінімальна кількість перетинів, яке може мати будь-яка з нескінченно багатьох еквівалентних діаграм. Цей інваріант важко знайти, тому що не можна перевіряти нескінченно багато діаграм.
Але яким може бути інваріант, який можна обчислити для даної діаграми? Складно уявити, яка властивість не змінюється при деформації, коли деформувати діаграму можна будь-яким способом.
Триколірність є інваріантною.
N-колірність
розв'язаний вузол
Тузун-Сікора
8_19
можуть деформуватися один в одного, не розрізаючи лінію вузла.
Як ви думаєте, які вони?
Нижче ви дізнаєтеся, як використовувати колiрність, щоб визначити, чи належать дві діаграми різним вузлам. Досліджуючи триколiрність, можна було побачити, які діаграми точно не можуть перетворитися одна в одну.
В іншому випадку наступна послідовність показує, як спростити діаграму Тузун-Сікори до кола.
Доказ того, що діаграма Тузун-Сікора є розв'язаним вузлом.
Діаграма розв'язування вузлів і Тузун-Сікора разом з нескінченною безліччю інших деформацій відносяться до одного і того ж математичного вузла, в даному випадку нерозв‘язанного вузла. Як можна вирішити, чи дві діаграми не зможуть ніколи бути деформо
вані одна в одну, незалежно від того, якими б великими вони не виростали між собою ? Властивість, яка не змінюється при деформації діаграми, називається 'інваріант' (незмінний).В іншому випадку наступна послідовність показує, як спростити діаграму Тузун-Сікори до кола.
Доказ того, що діаграма Тузун-Сікора є розв'язаним вузлом.
Початкова проекція
Хід Reidemeister 3
Після ходу і розтяжки
Хід перехресного скорочувального пасу
Після ходу і розтяжки
Хід перехресного скорочувального пасу
Після ходу і розтяжки
Хід перехресного скорочувального пасу
Після ходу і розтяжки
Хід перехресного скорочувального пасу
Після ходу і розтяжки
Хід перехресного скорочувального пасу
Після ходу
Хід перехресного скорочувального пасу
Після ходу
Хід Reidemeister 2
Після ходу
Хід Reidemeister 1
Після ходу
Хід Reidemeister 1
Після ходу
Хід Reidemeister 1
Після ходу
Хід Reidemeister 1
Після ходу
Прикладом інваріанта є мінімальна кількість перетинів, яке може мати будь-яка з нескінченно багатьох еквівалентних діаграм. Цей інваріант важко знайти, тому що не можна перевіряти нескінченно багато діаграм.
Але яким може бути інваріант, який можна обчислити для даної діаграми? Складно уявити, яка властивість не змінюється при деформації, коли деформувати діаграму можна будь-яким способом.
Триколірність є інваріантною.
Щоб пояснити це, ми використовуємо пасма, які є частинами вузлової лінії, які можна намалювати, не піднімаючи ручку. На кожному переході зустрічаються 3 пасма, одне це є шляхопровід і по однoму з кожного боку. Діаграма вузлів є триколірною, якщо кожному пасму можна надати один з 3 кольорів, так що на кожному перетині ми маємо або 1, або 3 кольори, а не 2 кольори. Розфарбувати все одним кольором завжди можливо, але не береться до уваги. Хоча б 2 кольори необхідно буде десь використати.
Яка з 3 діаграм є триколірною?
Розв’язаний вузол має лише одне пасмо і тому не є триколірним. 2-й вузол деформується у розв’язаний вузол і тому також не піддається розфарбуванню. Ми доведемо це пізніше. Інший вузол триколірний і тому ніколи не може бути деформований у розв’язаний вузол, як показано вище.
Триколірність є слабким інваріантом, оскільки містить лише найменшу можливу кількість інформації, просто так/ні. Цей інваріант здатний об'єднати всі вузли тільки в дві групи: вузли, які є триколірними, і ті, які ні.
N-колірність
Сильнішим інваріантом є N-колірність, де доступні кольори 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 і переформулювавши рівняння ≡ як нормальне рівняння. Для скорочення позначень використовуємо:
'ціле число' для 'цілого числа',
'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 = мб + мкН
→ ма ≡ мб мод N
Після множення з m отримуємо:
ma = мб + мкН
→ ма ≡ мб мод N
Доведіть: якщо a ≡ b mod (PQ), то a ≡ b mod P.
мод ≡ b (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.
Чому правдоподібно, що зворотне не вірно?
У моді рівняння N обидві частини ≡ можуть мати N різних значень. У моді рівняння (NM) обидві частини ≡ можуть мати різні значення NM. Тому мод відношення (NM) несе більше інформації, ніж мод відношення N. Відкинути інформацію шляхом переходу від моду (NM) до моду N легко, але зворотне створення інформації з нічого неможливо. Грубо кажучи, в цьому сенсі нормальна рівність з використанням = еквівалентно ≡моду ∞(нескінченність).
Як побічний коментар, це відкриває можливість того, що в додатках, де розв'язок включає цілі числа і де шукають рішення у вигляді рівняння за допомогою '=' і де відомо, що існує верхня межа абсолютної величини чисел у розв'язку, тоді стратегія може полягати в тому, щоб почати з пошуку розв'язку mod N для деякого малого простого числа N, а потім обчислити мод ідентичності N^2, потім mod N^4 і так далі, поки степінь N не буде більшою за верхню межу, відому для розв'язку, і тоді можна відкинути мод і отримати точний розв'язок за допомогою = .
Такий метод, званий підйомом Хенсела, може бути використаний для розкладання одновимірних багаточленів спочатку відносно деякого малого простого числа, а потім, нарешті, точно над цілими числами.
Доведіть: a + b ≡ ((a mod N) + (b mod N)) mod N
a і mod N відрізняються кратно N: a = (a mod 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 і mod N відрізняються кратно N: a = (a mod 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. Для u бути оберненим модом N, це означає:
ua ≡ 1 mod 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?
Ми побачили, що з a ≡ b mod N слідує ma ≡ mb mod N. Ми маємо еквівалентність, якщо можемо помножити на ціле число k ≡ 1/m mod N. Це означає, що після множення з m існує ціле число l таке, що mk = 1 + lN, iдентичність якого Безу з 1 = GCD(m,N) (великий спільний дільник m,N), тому m і N повинні бути взаємно простими для еквівалентності ma ≡ mb mod N і a ≡ b mod N.
Китайська теорема залишку.
Раніше ми говорили про те, що інформативність в модульному рівнянні mod N залежить від N. Чи не повинно бути можливим об'єднати два модульних рівняння з меншими модульними числами в одне з більшим числом?
Це те, що стверджує китайська теорема залишку.
Якщо для двох рівнянь
x ≡a 1 mod N1
x ≡a 2 mod N2
дільники N 1,N2 є взаємно простими, тоді існує рівно одне значення для x до кратних p1p2, яке задовольняє обидва модульних рівняння.
Одним зі способів отримати розв'язок є використання розширеного алгоритму Евкліда для розв'язання ідентичності Безу m1N1+ m 2N2= 1 шляхом обчислення m1,1,m2, а потім використовувати формулу
х =a1m2N2+a2m 1M1
=a1(1 - m1N1) + a2м1N1
=a1 + (a2 - a1)m1N1
який показує x ≡ a1 mod N 1 та еквівалентно x =a2 +(a1 - a 2)m2N2, який показує x ≡ a2mod N2.
Якщо є більше двох модульних рівнянь, то можна багаторазово заміняти два з них одним, поки не отримаємо рішення у вигляді одного модульного рівняння. При кожній заміні нове число дільника зростає, стаючи добутком двох дільників об'єднаних рівнянь.
Це те, що стверджує китайська теорема залишку.
Якщо для двох рівнянь
x ≡a 1 mod N1
x ≡a 2 mod N2
дільники N 1,N2 є взаємно простими, тоді існує рівно одне значення для x до кратних p1p2, яке задовольняє обидва модульних рівняння.
Одним зі способів отримати розв'язок є використання розширеного алгоритму Евкліда для розв'язання ідентичності Безу m1N1+ m 2N2= 1 шляхом обчислення m1,1,m2, а потім використовувати формулу
х =a1m2N2+a2m 1M1
=a1(1 - m1N1) + a2м1N1
=a1 + (a2 - a1)m1N1
який показує x ≡ a1 mod N 1 та еквівалентно x =a2 +(a1 - a 2)m2N2, який показує x ≡ a2mod N2.
Якщо є більше двох модульних рівнянь, то можна багаторазово заміняти два з них одним, поки не отримаємо рішення у вигляді одного модульного рівняння. При кожній заміні нове число дільника зростає, стаючи добутком двох дільників об'єднаних рівнянь.
Як довести, що N-забарвлення є інваріантним?
Як пояснювалося раніше в Розв'язування їжі для роздумів > Вступ з визначеннями > ходів Рейдемейстера, 3 ходів Рейдемейстера достатньо для виконання будь-якої деформації діаграми вузла. Тому, щоб бути інваріантом, потрібно лише показати, що властивість не змінюється при цих 3 ходах.
Як можна показати, що Рейдемейстер, який я переміщую, не змінює колірність?
Якщо кольори пасом A і B, як зазначено, то умова забарвлення вимагає на лівому малюнку A + B ≡ 2B mod N і на правому малюнку B + A ≡ 2A mod N. В обох випадках B = A є рішенням:
Це означає, що виконання ходу Рейдемейстра I не змінює колірність.
Як показати, що хід Рейдемейстра 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). Це визначає колір нового пасма при виконанні ходу Рейдемейстра II. На кольоровість це не впливає.
Як можна показати, що хід Рейдемейстра III не змінює колірність?
Якщо кольори пасом A, B, C, D, E, F та G, як зазначено, тоді трьома умовами ліворуч є:
A + D ≡ 2C mod N
E + F ≡ 2D mod 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, як зазначено, то умова забарвлення вимагає на лівому малюнку A + B ≡ 2B mod N і на правому малюнку B + A ≡ 2A mod N. В обох випадках B = A є рішенням:
Це означає, що виконання ходу Рейдемейстра I не змінює колірність.
Як показати, що хід Рейдемейстра 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). Це визначає колір нового пасма при виконанні ходу Рейдемейстра II. На кольоровість це не впливає.
Як можна показати, що хід Рейдемейстра III не змінює колірність?
Якщо кольори пасом A, B, C, D, E, F та G, як зазначено, тоді трьома умовами ліворуч є:
A + D ≡ 2C mod N
E + F ≡ 2D mod 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, до кожного кольору, відмінності не змінюються:
(A+S) - (C+S) = A - C + S - S = A - C і
(C+S) - (B+S) = C - B + S - S = C - B і
тому умови все ще виконуються.
2) Ми бачили раніше як правило модульної арифметики, що ми можемо помножити обидві частини ≡ на число, взаємне просте до N і отримати еквівалентний розв'язок системи рівнянь і, таким чином, еквівалентне забарвлення.
1) При додаванні однієї і тієї ж константи, скажімо S, до кожного кольору, відмінності не змінюються:
(A+S) - (C+S) = A - C + S - S = A - C і
(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, ми отримуємо забарвлення mod P, обчислюючи всі значення кольорів mod P, і це дає нам забарвлення mod Q, обчислюючи всі значення кольорів mod Q. А як же інший напрямок? Якщо система умов забарвлення для діаграми вузлів має розв'язок mod P і інший розв'язок mod Q, де P і Q є взаємно простими, чи має ця система умов тоді розв'язок mod PQ?
Відповідь: Так.
Доказ:
Нехай1,2 це є кольори одного пасма в забарленнях mod P і mod Q.
Тоді Китайська теорема залишку гарантує існування та унікальність одного цілого числа A mod PQ, що і задовольняє обидві умови.
A ≡a1 mod P
A ≡a2 mod Q.
Це можна повторити для кожного пасма, даючи значення кольорів A, B, C,... мод PQ.
На кожному перетині дві умови забарвлення
(A + B - 2C) mod P =a1+ b11≡ 0 mod P
(A + B - 2C) mod Q =a 2 +b2-2c 2 =0 mod Q
є задовільними. Єдине значення (A + B - 2C) mod PQ, яке дорівнює нулю mod P і нулю mod Q це A + B - 2C ≡ 0 mod PQ. Це показує, що значення кольорів A, B, C,... надає забарвлення mod PQ.
Оскільки всі натуральні числа мають просту розкладку на множники, їх можна записати як добуток степенів простих чисел. Тому можна знайти всі числа забарвлень, досліджуючи лише всі степені всіх непарних простих чисел як числа забарвлень. Раніше ми бачили, що просте число 2 і степінь 2 є не можливими числами забарвлення.
Можна було б почати перевіряти наявність розфарбовування по модулю деякого простого числа і, якщо успішно, то повторювати перевірку з все більш високими степенями цього простого числа, поки більше не існує кулінгу.
Відповідь: Так.
Доказ:
Нехай1,2 це є кольори одного пасма в забарленнях mod P і mod Q.
Тоді Китайська теорема залишку гарантує існування та унікальність одного цілого числа A mod PQ, що і задовольняє обидві умови.
A ≡a1 mod P
A ≡a2 mod Q.
Це можна повторити для кожного пасма, даючи значення кольорів A, B, C,... мод PQ.
На кожному перетині дві умови забарвлення
(A + B - 2C) mod P =a1+ b11≡ 0 mod P
(A + B - 2C) mod Q =a 2 +b2-2c 2 =0 mod Q
є задовільними. Єдине значення (A + B - 2C) mod PQ, яке дорівнює нулю mod P і нулю mod Q це A + B - 2C ≡ 0 mod PQ. Це показує, що значення кольорів A, B, C,... надає забарвлення mod 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 mod 5 таким чином до a 1. Тому 2-у букву потрібно спробувати лише як 0 і 1.
- Тести - це теж питання часу. Можна заощадити час, вводячи від'ємні числа, коли їх обчислюється швидше, ніж додатні. Інтерфейсу не потрібні числа в діапазоні 0..N-1.
- Коли рівняння стає червоним, то умова ≡ нe виконується, і хоча б одне число потрібно змінити. Потім спробуйте інше число. Щоб не пропустити числа, можна спробувати числа порядку 0,1,...,N-1 і зупинитися при знаходженні забарвлення.
- Під час зворотного відстеження, натиснувши кнопку скасування, якщо ви бачите фіолетове рівняння, можна знову натиснути кнопку скасування, не замислюючись. Причина в тому, що фіолетове рівняння має тільки одну літеру, і для цієї літери існує тільки одне можливе значення (mod N), тому ніякого іншого значення для цієї літери в даній ситуації пробувати не потрібно.
- Щоб систематично шукати і не упускати жодної можливості забарвлення, можна було б почати з призначення кожній змінній значення 0, яке дає тривіальне рішення, а потім почати відступати, щоб отримати нетривіальне рішення.
- Діаграми вузлів, які використовуються в цій грі, мають вже мінімальну кількість перетинів. Але якщо діаграми не будуть мінімальними, то вигідно буде спочатку їх спростити. Без вищевказаних методів прискорення довелося б спробувати забарвлення NC, де N - кількість кольорів, а C це кількість перетинів = кількісті пасом. Зменшення кількості перетинів лише на 1 знижує зусилля на КОЕФІЦІЄНТ N.
Чи є вузли, які не можна зафарбувати?
Так. Вузли з менш ніж 12 перетинами, які не мають забарвлення, - це 10124, 10153, 11n34, 11n42, 11n49, 11n116 та звичайно ж, розв’язаний вузол. На малюнку представлена схема вузла 10124.
Діаграма з написом «Тузун-Сікора» у верхній частині сторінки є лише однією з нескінченно багатьох діаграм вузла і тому також не розфарбовується.
Діаграма з написом «Тузун-Сікора» у верхній частині сторінки є лише однією з нескінченно багатьох діаграм вузла і тому також не розфарбовується.
Чи існує ще більше колірних інваріантів і як їх можна обчислити?
Так, ці додаткові інваріанти є кратністю рішень, по одній кратності на кожну кількість доступних кольорів. Для розуміння наступних коментарів знадобляться деякі знання лінійної алгебри.
Якщо діаграма вузлів має перетини C, то вона також має пасма C і, таким чином, система умов має матрицю коефіцієнта C×C, де кожен ряд представляє перетин і складається або з двох -1 і одного 2, або з +1 і а -1 (петльовий перетин Reidemeister I). Кожен стовпчик відповідає пасму і має стільки ж 2, скільки пасмо має шляхопроводів: або два -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 в останньому положенні.
Наступна діаграма належить вузлу 12a801.
Нормальна форма Сміта (SNF) має по діагоналі дев'ять 1, за якими слідує 3,45,0. У цій формі кожне число є множником наступного діагонального числа. А кратність забарвлення - це кількість діагональних елементів, в яких воно зустрічається як множник. Таким чином, кожна діаграма цього вузла має два незалежних 3-забарвлення і одне 45-забарвлення, що означає, що цей вузол також має одне 5-,9-,15-забарвлення.
Якщо діаграма вузлів має перетини C, то вона також має пасма C і, таким чином, система умов має матрицю коефіцієнта C×C, де кожен ряд представляє перетин і складається або з двох -1 і одного 2, або з +1 і а -1 (петльовий перетин Reidemeister I). Кожен стовпчик відповідає пасму і має стільки ж 2, скільки пасмо має шляхопроводів: або два -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 в останньому положенні.
Наступна діаграма належить вузлу 12a801.
Нормальна форма Сміта (SNF) має по діагоналі дев'ять 1, за якими слідує 3,45,0. У цій формі кожне число є множником наступного діагонального числа. А кратність забарвлення - це кількість діагональних елементів, в яких воно зустрічається як множник. Таким чином, кожна діаграма цього вузла має два незалежних 3-забарвлення і одне 45-забарвлення, що означає, що цей вузол також має одне 5-,9-,15-забарвлення.
Статистика забарвлення вузлів
Чи є огляд можливoго забарвлення простих вузлів до певного розміру?
Текстовий файл
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: # класів при розгляді списку записів нормальної форми Сміта <> 1
ABS: exp(ln(noofcl3[cr])/(cr-3))
= (cr-3)-й корінь з (# з cl3)
Таблиця 1: Статистика інваріантів кольорів
# cr: # переходів
# kn: # вузлів
# cl1: # класів коли розглядається тільки список забарвлення простих чисел.
# cl2: # класів при розгляді тільки списку кратностей забарвлення простих .
# з cl3: # класів при розгляді списку записів нормальної форми Сміта <> 1
ABS: exp(ln(noofcl3[cr])/(cr-3))
= (cr-3)-й корінь з (# з cl3)
| # з cr | # з kn | # з cl1 | kn/cl1 | # з cl2 | kn/cl2 | # з cl3 | on/cl3 | abs↑ |
|---|---|---|---|---|---|---|---|---|
| 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 (<16) і знайти з цих вузлів той, що має найбільше число забарвлення N max, то наступна таблиця показує, що Nmax зростає приблизно в 1,7 рази при збільшенні C на 1.
Таблиця 2: Таблиця B(C) = Nmax1/(C−1)
Таблиця 2: Таблиця B(C) = Nmax1/(C−1)
| C | Nmax | вузол | BС) |
|---|---|---|---|
| 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 працює під 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] J. H. Przytycki, 3-х колірне забарвлення та інші елементарні інваріанти вузлів. Публікації Банахового центру, т. 42, "Теорія вузлів", Варшава, 1998, 275−295.
[3] Рольфсен Д., Таблиця вузлів і посилань. Додаток С у вузлах і посиланнях. Wilmington, DE: Publish or Perish Press, pp. 280-287, 1976.
[4] J. C. Cha і C. Livingston, 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] J. H. Przytycki, 3-х колірне забарвлення та інші елементарні інваріанти вузлів. Публікації Банахового центру, т. 42, "Теорія вузлів", Варшава, 1998, 275−295.
[3] Рольфсен Д., Таблиця вузлів і посилань. Додаток С у вузлах і посиланнях. Wilmington, DE: Publish or Perish Press, pp. 280-287, 1976.
[4] J. C. Cha і C. Livingston, 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
Слідкуйте за оновленнями або підписуйтесь на них: