300000
22772
11746
English | Français | فارسی | 中文 | Українська | Azerbaijani | ខ្មែរ | Tiếng Việt | Bahasa Melayu | Deutsch | O'zbek | Русский
11746
Knot Colouring
Agar siz bu muammoni qanday hal qilish kerakligi bilan qiziqsangiz va orqangizdagi nazariyani emas, unda "Sinov va xato yo'li bilan rangni topish uchun maslahatlar nima?"
Invariantlar haqida
Quyidagi uchta diagrammadan ikkitasi
knotline kesmasdan bir-biriga deformatsiya qilinishi mumkin.
Invariantga misol - cheksiz ko'p ekvivalent diagrammalardan har qanday biriga ega bo'lishi mumkin bo'lgan minimal o'tish soni. Bu invariantni topish qiyin, chunki cheksiz ko'p diagrammalarni tekshirish mumkin emas.
Ammo berilgan diagramma uchun hisoblash mumkin bo'lgan invariant nima bo'lishi mumkin? Diagrammani xohlagan tarzda deformatsiyalash mumkin bo'lsa, qaysi xususiyat deformatsiyada o'zgarmasligini tasavvur qilish qiyin.
Tri-ranglilik - bu invariant.
N-rangsozlik
ununus yechish
Tuzun Sikora
8_19
knotline kesmasdan bir-biriga deformatsiya qilinishi mumkin.
Sizningcha, ular qaysi?
Ikkita diagramma turli tugunlarga tegishli yoki yo'qligini aniqlash uchun rangni qanday ishlatishni quyida bilib olasiz. Uch ranglilikni tadqiq qilish orqali qaysi diagrammalar bir-biriga deformatsiyalanib bo'lmasligini ko'rish mumkin edi.
Aks holda, quyidagi ketma-ketlikda Tuzun-Sikora diagrammasini aylanaga qanday soddalashtirish mumkinligi ko'rsatilgan.
Tuzun-Sikora diagrammasi unknot ekanligini isbotlash.
Unknotting diagrammasi va Tuzun-Sikora boshqa cheksiz ko'plab deformatsiyalar bilan birgalikda bir xil matematik tugunga, bu holda untugega tegishli. Qanday qilib ikkita diagramma bir-biriga deformatsiyalanib bo'lmasligini qanday hal qilish mumkin? Diagramma deformatsiyalanganda o'zgarmaydigan xususiyat "invariant" (o'zgarmaydigan) deb ataladi.Aks holda, quyidagi ketma-ketlikda Tuzun-Sikora diagrammasini aylanaga qanday soddalashtirish mumkinligi ko'rsatilgan.
Tuzun-Sikora diagrammasi unknot ekanligini isbotlash.
Dastlabki proyeksiyaName
Reidemeister 3 harakati
Ko'chib o'tish va bir streç keyin
O'tish pasini kamaytirish harakati
Ko'chib o'tish va bir streç keyin
O'tish pasini kamaytirish harakati
Ko'chib o'tish va bir streç keyin
O'tish pasini kamaytirish harakati
Ko'chib o'tish va bir streç keyin
O'tish pasini kamaytirish harakati
Ko'chib o'tish va bir streç keyin
O'tish pasini kamaytirish harakati
Ko'chib o'tishdan keyin
O'tish pasini kamaytirish harakati
Ko'chib o'tishdan keyin
Reidemeister 2 harakati
Ko'chib o'tishdan keyin
Reidemeister 1 harakati
Ko'chib o'tishdan keyin
Reidemeister 1 harakati
Ko'chib o'tishdan keyin
Reidemeister 1 harakati
Ko'chib o'tishdan keyin
Reidemeister 1 harakati
Ko'chib o'tishdan keyin
Invariantga misol - cheksiz ko'p ekvivalent diagrammalardan har qanday biriga ega bo'lishi mumkin bo'lgan minimal o'tish soni. Bu invariantni topish qiyin, chunki cheksiz ko'p diagrammalarni tekshirish mumkin emas.
Ammo berilgan diagramma uchun hisoblash mumkin bo'lgan invariant nima bo'lishi mumkin? Diagrammani xohlagan tarzda deformatsiyalash mumkin bo'lsa, qaysi xususiyat deformatsiyada o'zgarmasligini tasavvur qilish qiyin.
Tri-ranglilik - bu invariant.
Buni tushuntirish uchun biz qalamni ko'tarmasdan chizilishi mumkin bo'lgan tugun chizig'ining bir qismi bo'lgan iplardan foydalanamiz. Har bir o'tishda 3 ta ipni uchrashadi, bittasi over-pass va har bir tomondan bitta. Agar har bir ipga 3 rangdan biri berilishi mumkin bo'lsa, tugun diagrammasi uch rangli bo'ladi, shunda har bir kesishmada biz 1 yoki 3 rangga ega bo'lamiz, 2 rang emas. Barchasini bitta rang bilan bo'yash har doim mumkin va hisobga olinmaydi. Kamida 2 rangni bir joyda ishlatish kerak.
3 diagrammalaridan qaysi biri uch rangli?
Untugun faqat bitta ipga ega va shuning uchun uch rangli emas. 2-tugun untugun uchun deformatsiyalanadi va shuning uchun ham ranglanmaydi. Buni keyinroq isbotlaymiz. Boshqa tugun uch rangli bo'lib, shuning uchun yuqorida ko'rsatilganidek untuge'ga hech qachon deformatsiyalanishi mumkin emas.
Tri-ranglilik zaif invariantdir, chunki u faqat eng kichik miqdordagi ma'lumotni o'z ichiga oladi, faqat "ha" / "yo'q". Bu invariant faqat barcha tugunlarni ikki guruhga ajrata oladi, uch rangli va bo'lmagan tugunlar.
N-rangsozlik
Kuchli invariant - bu N-ranglilik, bu erda N ranglar mavjud va har bir rang 0,1,2,3,...,N-1 raqamlaridan birini ifodalaydi. Har bir o'tishda qondirilishi kerak bo'lgan shart shundan iboratki, 2 pastki iplarning ranglari yig'indisi minus 2 marta ortiqcha ipning rangi N-ning ko'payishiga teng. Boshqacha qilib aytganda, agar ranglar a,b,c bo'lsa, u holda a + b-2c = kN bo'lgan ko'paytiruvchi k bo'lishi kerak. Matematik jihatdan ekvivalent, ammo ko'proq keng tarqalgan formula: a + b ≡ 2c mod N. Bu shuni anglatadiki, ≡ belgisining har ikki tomoni ham N orqali bo'linishda bir xil qoldiqni qoldiradi. Ishlash moduli (mod) ba'zi raqamlar modulli arifmetika deb ataladi va juda ko'p qiziqarli va foydali qoidalarga ega.
Ko'plab savollar paydo bo'ladi.
Ko'plab savollar paydo bo'ladi.
Modulli arifmetikaga kirish
Biz k ko'paytiruvchisini kiritish va ≡ tenglamani normal tenglama sifatida qayta shakllantirish orqali modulli arifmetikaning barcha bayonotlarini isbotlashimiz mumkin. Notatsiyani qisqartirish uchun biz quyidagilardan foydalanamiz:
'Butun son' uchun 'integer',
'p marta q' uchun 'pq',
'∃' uchun 'mavjud',
':' uchun 'mulk bilan' va
"A → B" uchun "A dan B ergashadi".
Isbotlash: agar ≡ b mod N va c ≡ d mod N bo'lsa, u holda (a+c) ≡ (b+d) mod N
Modulli tenglama a ≡ b mod N a va b faqat p-ning ko'paytmasi bilan farq qilishini aytadi.
ya'ni a = b + mp xususiyatiga ega bo'lgan m ko'paytiruvchisi bo'lishi kerak. Qisqacha notatsiya bilan bu
(a ≡ b mod N) → (∃ butun sonli m: a = b + mp)
(c ≡ d mod N) → (∃ butun son: n: c = d + np)
Ikkala tenglamani qo'shib, a + c = b + mp + d + np = b + d + (m + n) ni olamiz.
→ a + c ≡ (b + d) mod N
ya'ni a = b + mp xususiyatiga ega bo'lgan m ko'paytiruvchisi bo'lishi kerak. Qisqacha notatsiya bilan bu
(a ≡ b mod N) → (∃ butun sonli m: a = b + mp)
(c ≡ d mod N) → (∃ butun son: n: c = d + np)
Ikkala tenglamani qo'shib, a + c = b + mp + d + np = b + d + (m + n) ni olamiz.
→ a + c ≡ (b + d) mod N
Isbotlash: agar ≡ b mod N bo'lsa, u holda har qanday m butun qismi uchun biz ma ≡ mb mod N bor
(a ≡ b mod N) → (∃ butun sonli k: a = b + kN)
M bilan ko'paytirishdan so'ng biz olasiz
ma = MB + mkN
→ ma ≡ mb mod N
M bilan ko'paytirishdan so'ng biz olasiz
ma = MB + mkN
→ ma ≡ mb mod N
Isbotlash: agar ≡ b mod (PQ) bo'lsa, unda ≡ b mod P.
a ≡ b mod (PQ)
→ ∃ butun k: a = b + k(PQ)
→ a = b + (kQ)P
→ a ≡ b mod P
Qarama-qarshi yo'nalish haqida nima deyish mumkin?
Nima uchun teskari haqiqat emas?
→ ∃ butun k: a = b + k(PQ)
→ a = b + (kQ)P
→ a ≡ b mod P
Qarama-qarshi yo'nalish haqida nima deyish mumkin?
Mana qarshi misol:
6 ≡ 1 mod 5 lekin
6 ≢ 1 mod 15, chunki 6 va 1 15 ning ko'paytmasi bilan farq qilmaydi.
6 ≡ 1 mod 5 lekin
6 ≢ 1 mod 15, chunki 6 va 1 15 ning ko'paytmasi bilan farq qilmaydi.
Nima uchun teskari haqiqat emas?
Tenglama modida N ikkala tomoni ham N turli qiymatlarga ega bo≡lishi mumkin. Tenglama modida (NM) ≡ ikkala tomoni ham NM turli qiymatlarga ega bo'lishi mumkin. Shuning uchun munosabat modi (NM) munosabat modi N-ga qaraganda ko'proq ma'lumotni olib boradi. Mod (NM) dan mod N-ga o'tish orqali ma'lumotni tashlash oson, ammo hech narsadan ma'lumot yaratishning teskarisi mumkin emas. Taxminan aytganda, bu ma'noda = yordamida normal tenglik ≡ mod ∞(infinity) ga teng.
Yon izoh sifatida, bu echim butun sonlarni o'z ichiga olgan va '=' yordamida tenglama shaklida yechimni izlayotgan va yechimdagi sonlarning mutlaq qiymati uchun yuqori chegara borligini biladigan ilovalarda strategiya ba'zi kichik bosh son N uchun mod N yechimini topishdan boshlash va keyin hisoblash bo'lishi mumkin identifikatsiya mod N^2, keyin mod N^4 va hokazo N ning kuchi yuqori chegaradan kattaroq bo'lguncha echim uchun biladi va keyin modni tashlash mumkin va = yordamida aniq yechimga ega bo'ladi.
Hensel ko'tarish deb nomlangan bunday usul bir o'zgaruvchan polinomlarni avval ba'zi kichik bosh sonlarga nisbatan, so'ngra nihoyat to'liq butun sonlar ustidan faktorlashtirish uchun ishlatilishi mumkin.
Isbotlash: a + b ≡ ((a mod N) + (b mod N)) mod N
a va mod N N-ning ko'paytmasi bilan farq qiladi: a = (a mod N) + pN
b va b mod N Nning ko'paytmasi bilan farq qiladi: 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 va b mod N Nning ko'paytmasi bilan farq qiladi: 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
Isbotlash: ab ≡ ((a mod N) (b mod N)) mod N
a va mod N N-ning ko'paytmasi bilan farq qiladi: a = (a mod N) + pN
b va b mod N Nning ko'paytmasi bilan farq qiladi: 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 va b mod N Nning ko'paytmasi bilan farq qiladi: 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
Isbotlash: agar P(x,y,...) x,y o'zgaruvchilaridagi polinom bo'lsa,... keyin P(x,y,...) ≡ P((x mod N),(y mod N),...) mod N
Har bir polinom mahsulotlar yig'indisi sifatida yozilishi mumkin, shuning uchun yuqoridagi ikkita qoidani qo'llash bayonotni qayta-qayta tasdiqlaydi.
Isbotlash: Modulli arifmetik modulda bosh son, butun sonlarga bo'linish yana butun sonlarni beradi.
Biz bosh son p va har qanday butun sonli a ≢ 0 mod N uchun teskari 1/a mod N ham butun sondir. Biz ≢ 0 mod N talab qilamiz, chunki modulli arifmetikada ham nolga bo'lish mumkin emas.
U bo'lsin u ≡ 1/a mod N. siz modning teskarisi bo'lishingiz uchun N bu degan ma'noni anglatadi
ua ≡ 1 mod N
→ ∃ butun k: ua = 1 + kp
Bu Bézoutning identifikatsiyasi shakliga ega: ua + vp = GCD(a,p) bu erda GCD(a,p) a,p ning eng katta umumiy bo'linuvchisi va bu erda v=-k. Chunki p bosh son va a p ning ko'paytmasi emas, shuning uchun GCD(a,p)=1.
Bézout identifikatoridagi u,v ko'paytiruvchilari kengaytirilgan Yevklid algoritmi orqali hisoblanishi mumkin va ikkalasi, u,v, butun sondir.
agar u=1/a butun sonli mod N bo'lsa, u holda b/a = bu ham ko'rsatilishi kerak bo'lgan butun sonli mod N hisoblanadi.
Misol: 1/3 ≡ 5 mod 7, chunki 1 = 3 (1/3) ≡ 3 (5) = 15 = 2 (7) + 1 ≡ 1 mod 7.
Qachon ma ≡ mb mod N ≡ b mod N ga teng?
Biz ≡ b moddan N ma ≡ mb mod N dan kelib chiqqanini ko'rdik. Agar biz k ≡ 1/m mod N butun sonini ko'paytirishimiz mumkin bo'lsa, ekvivalentlik bor. Bu shuni anglatadiki, m bilan ko'paytirishdan keyin l butun soni mavjud, shunday mk = 1 + lN bo'lib, Bézoutning 1 = GCD(m,N) bilan identifikatsiyasi (m,N ning katta umumiy taqsimlovchisi), shuning uchun m va N ma ≡ mb mod N va a ≡ b mod N ekvivalenti uchun birgalikda bosh bo'lishi kerak.
Xitoy qolgan teoremasi.
Biz ilgari modulli tenglamadagi ma'lumot mazmuni haqida gapirgan edik mod N N-ga bog'liq. Kichik modulli sonlar bilan ikkita modulli tenglamani katta sonli biriga birlashtirish mumkin emasmi?
Xitoy eslatma teoremasi shunday deydi.
Agar ikki tenglama uchun bo'lsa
x ≡a 1 mod N1
x ≡a 2 mod N2
N1,N 2 bo'linuvchilari birgalikda prime, keyin x uchun p1p2 ning ko'paytmalarigacha aynan bitta qiymat mavjud bo'lib, bu ikkala modulli tenglamani ham qondiradi.
Yechimni olishning bir usuli - Besout identifikatsiyasini m 1,m2 hisoblash orqali m 1 N1 + m2N2 = 1 ni yechish uchun kengaytirilgan Yevklid algoritmini qo'llash va keyin formuladan foydalanish
x = a1m2N2 + a2m1M1
= a1 (1 - m1N1) + a2m1N1
= a1 + (a2 - a1)m1N1
qaysi x ≡ a1 mod N1 va ekvivalent x = a2 + (a1 - a2)m2N2 ko'rsatadi x ≡a 2 mod N2.
Agar ikkitadan ortiq modulli tenglamalar bo'lsa, unda bitta modulli tenglama shaklida yechimga ega bo'lmaguncha, ulardan ikkitasini qayta-qayta almashtirish mumkin. Har bir almashtirishda yangi bo'linuvchi son birlashtirilgan tenglamalarning ikki bo'linuvchisining mahsuli bo'lib o'sadi.
Xitoy eslatma teoremasi shunday deydi.
Agar ikki tenglama uchun bo'lsa
x ≡a 1 mod N1
x ≡a 2 mod N2
N1,N 2 bo'linuvchilari birgalikda prime, keyin x uchun p1p2 ning ko'paytmalarigacha aynan bitta qiymat mavjud bo'lib, bu ikkala modulli tenglamani ham qondiradi.
Yechimni olishning bir usuli - Besout identifikatsiyasini m 1,m2 hisoblash orqali m 1 N1 + m2N2 = 1 ni yechish uchun kengaytirilgan Yevklid algoritmini qo'llash va keyin formuladan foydalanish
x = a1m2N2 + a2m1M1
= a1 (1 - m1N1) + a2m1N1
= a1 + (a2 - a1)m1N1
qaysi x ≡ a1 mod N1 va ekvivalent x = a2 + (a1 - a2)m2N2 ko'rsatadi x ≡a 2 mod N2.
Agar ikkitadan ortiq modulli tenglamalar bo'lsa, unda bitta modulli tenglama shaklida yechimga ega bo'lmaguncha, ulardan ikkitasini qayta-qayta almashtirish mumkin. Har bir almashtirishda yangi bo'linuvchi son birlashtirilgan tenglamalarning ikki bo'linuvchisining mahsuli bo'lib o'sadi.
N-ranglanishi invariant ekanligini qanday isbotlash mumkin?
Yuqorida aytib o'tilganidek Fikr yuritish uchun ba'zi oziq-ovqatlarni ochish > Reidemeister harakatlari > ta'riflar bilan kirish, 3 Reidemeister harakatlari tugun diagrammasining har qanday deformatsiyasini amalga oshirish uchun etarli. Shuning uchun, invariant bo'lish uchun faqat xususiyat ushbu 3 harakati ostida o'zgarmasligini ko'rsatish kerak.
Men ko'chiradigan Reidemeister rangni o'zgartirmasligini qanday ko'rsatish mumkin?
Agar iplarning ranglari ko'rsatilgandek A va B bo'lsa, ranglash holati chap rasmda A + B ≡ 2B mod N va o'ng rasmda B + A ≡ 2A mod N talab qiladi. Ikkala holatda ham B = A yechim:
Ya'ni, Reidemeisterni ko'chirishni bajarish rangni o'zgartirmaydi.
Reidemeister II harakati rangni o'zgartirmasligini qanday ko'rsatish mumkin?
Agar iplarning ranglari ko'rsatilgandek A,B va C bo'lsa, C chap rasmda B + C ≡ 2A mod N shartidan noyob aniqlanadi, shuning uchun C ≡ (2A - B mod N) va o'ng rasmda A + C ≡ 2B mod N so C ≡ (2B - A mod N). Bu Reidemeister II harakatini amalga oshirishda yangi ipning rangini belgilaydi. Ranglanish ta'sir qilmaydi.
Reidemeister III harakati rangni o'zgartirmasligini qanday ko'rsatish mumkin?
Agar iplarning ranglari ko'rsatilgandek A,B,C,D,E,F va G bo'lsa, chapdagi uchta shart
A + D ≡ 2C mod N
E + F ≡ 2D mod N
F + B ≡ 2C mod N .
F ichki ipini yo'q qilish orqali tashqi iplardagi holat quyidagicha
2D - E ≡ 2C - B mod N yordamida A + D ≡ 2C mod N yordamida soddalashtiradi
2D - E ≡ A + D - B mod N va shuning uchun A - B - D + E ≡ 0 mod N.
O'ngdagi 3 shart quyidagilar
E + G ≡ 2C mod N
G + B ≡ 2A mod N
A + D ≡ 2C mod N
G ichki ipini yo'q qilish orqali tashqi iplardagi holat quyidagicha
2C - E ≡ 2A - B mod N 2C ≡ A + D mod N yordamida soddalashtiradi
A + D - E ≡ 2A - B mod N va shuning uchun 0 ≡ A - B - D + E mod N.
F va G ular paydo bo'lgan munosabatlarning har qanday biridan hisoblanadi.
Xulosa qilamizki, har ikkala diagramma uchun ham tashqi iplarning ranglaridagi sharoitlar bir xil: A + D ≡ 2C mod N va A - B - D + E ≡ 0 mod N.
Shuning uchun har ikkala diagramma ham rangga ega yoki hech biri rangga ega emas va shuning uchun ranglanish Reidemeister III harakatlari ostida invariantdir.
Men ko'chiradigan Reidemeister rangni o'zgartirmasligini qanday ko'rsatish mumkin?
Agar iplarning ranglari ko'rsatilgandek A va B bo'lsa, ranglash holati chap rasmda A + B ≡ 2B mod N va o'ng rasmda B + A ≡ 2A mod N talab qiladi. Ikkala holatda ham B = A yechim:
Ya'ni, Reidemeisterni ko'chirishni bajarish rangni o'zgartirmaydi.
Reidemeister II harakati rangni o'zgartirmasligini qanday ko'rsatish mumkin?
Agar iplarning ranglari ko'rsatilgandek A,B va C bo'lsa, C chap rasmda B + C ≡ 2A mod N shartidan noyob aniqlanadi, shuning uchun C ≡ (2A - B mod N) va o'ng rasmda A + C ≡ 2B mod N so C ≡ (2B - A mod N). Bu Reidemeister II harakatini amalga oshirishda yangi ipning rangini belgilaydi. Ranglanish ta'sir qilmaydi.
Reidemeister III harakati rangni o'zgartirmasligini qanday ko'rsatish mumkin?
Agar iplarning ranglari ko'rsatilgandek A,B,C,D,E,F va G bo'lsa, chapdagi uchta shart
A + D ≡ 2C mod N
E + F ≡ 2D mod N
F + B ≡ 2C mod N .
F ichki ipini yo'q qilish orqali tashqi iplardagi holat quyidagicha
2D - E ≡ 2C - B mod N yordamida A + D ≡ 2C mod N yordamida soddalashtiradi
2D - E ≡ A + D - B mod N va shuning uchun A - B - D + E ≡ 0 mod N.
O'ngdagi 3 shart quyidagilar
E + G ≡ 2C mod N
G + B ≡ 2A mod N
A + D ≡ 2C mod N
G ichki ipini yo'q qilish orqali tashqi iplardagi holat quyidagicha
2C - E ≡ 2A - B mod N 2C ≡ A + D mod N yordamida soddalashtiradi
A + D - E ≡ 2A - B mod N va shuning uchun 0 ≡ A - B - D + E mod N.
F va G ular paydo bo'lgan munosabatlarning har qanday biridan hisoblanadi.
Xulosa qilamizki, har ikkala diagramma uchun ham tashqi iplarning ranglaridagi sharoitlar bir xil: A + D ≡ 2C mod N va A - B - D + E ≡ 0 mod N.
Shuning uchun har ikkala diagramma ham rangga ega yoki hech biri rangga ega emas va shuning uchun ranglanish Reidemeister III harakatlari ostida invariantdir.
Rangning ahamiyatsizligi, ekvivalentligi va mustaqilligi
Agar bitta rang bo'lsa, har qanday tugun diagrammasi uchun undan boshqa qanday ranglarni olish mumkin?
Rang shartlarining har biri A + B ≡ 2C mod N shakliga ega. Keling, uni A - C ≡ C - B mod N deb yozaylik.
1) Bir xil doimiyni qo'shganda, har bir rangga S deylik, keyin farqlar o'zgarmaydi:
(A + S) - (C + S) = A - C + S - S = A - C va
(C + S) - (B+S) = C - B + S - S = C - B va
Shuning uchun shartlar hali ham qondirilgan.
2) Biz ilgari modulli arifmetikaning qoidasi sifatida ko'rdikki, biz ≡ ikkala tomonini N-ga ko'p bosh sonlar bilan ko'paytirishimiz va tenglamalar tizimining ekvivalent yechimini va shuning uchun ekvivalent rangni olishimiz mumkin.
1) Bir xil doimiyni qo'shganda, har bir rangga S deylik, keyin farqlar o'zgarmaydi:
(A + S) - (C + S) = A - C + S - S = A - C va
(C + S) - (B+S) = C - B + S - S = C - B va
Shuning uchun shartlar hali ham qondirilgan.
2) Biz ilgari modulli arifmetikaning qoidasi sifatida ko'rdikki, biz ≡ ikkala tomonini N-ga ko'p bosh sonlar bilan ko'paytirishimiz va tenglamalar tizimining ekvivalent yechimini va shuning uchun ekvivalent rangni olishimiz mumkin.
Ranglanish mod 2 mazmunlimi?
Yo'q, N = 2 uchun rang ahamiyatsiz.
Keling, C rangi bilan birinchi yo'l o'tkazgichi ostidan o'tgandan so'ng B ipi sifatida davom etadigan A rangli ipdan boshlaylik. Keyin A, B, C A + B ≡ 2C mod 2 orqali bog'lanadi va B qo'shilgandan keyin ikkala tomonga A ≡ B mod 2, chunki 2B ≡ 2C ≡ 0 mod 2. Barcha o'tish joylarida bu fikrni davom ettirsak, barcha iplar teng rangga (0) yoki to'q rangga (1) ega. Bu ahamiyatsiz rang beradi.
Keling, C rangi bilan birinchi yo'l o'tkazgichi ostidan o'tgandan so'ng B ipi sifatida davom etadigan A rangli ipdan boshlaylik. Keyin A, B, C A + B ≡ 2C mod 2 orqali bog'lanadi va B qo'shilgandan keyin ikkala tomonga A ≡ B mod 2, chunki 2B ≡ 2C ≡ 0 mod 2. Barcha o'tish joylarida bu fikrni davom ettirsak, barcha iplar teng rangga (0) yoki to'q rangga (1) ega. Bu ahamiyatsiz rang beradi.
Ranglanish modi (2N) haqida nima deyish mumkin, ya'ni teng sonni modulo?
Biz yuqorida barcha ranglar juft yoki toq ekanligini ko'rdik. Agar ular hatto bo'lsa, biz ularning barchasini 2 ga ajratamiz va ma'lumotni yo'qotmasdan bo'yash modiga ega bo'lamiz. Agar ularning barchasi to'g'ri bo'lsa, biz barcha ranglarga 1 qo'shishimiz va endi barcha ranglar teng bo'lgan ekvivalent rangni olishimiz mumkin, shuning uchun biz omil 2ni tushirib, teng rang modiga ega bo'lishimiz mumkin.
Natijada, har bir bo'yash modi (2N) kulouring mod N ga tengdir.
Natijada, har bir bo'yash modi (2N) kulouring mod N ga tengdir.
Qaysi N uchun N-ranglanishi foydali va arzimas emas?
Odd N>1 ranglari uchun mod N mazmunli.
P va Q barcha ranglarni bilish uchun mod P va mod Q bo'lgan barcha ranglarni bilish etarlimi?
Agar N murakkab son bo'lsa, ya'ni ikkala omil 1 bo'lmagan mahsulot bo'lsa, uni N = PQ sifatida yozish mumkin, P va Q birgalikda prime. Rang sharoitlarining echimiga ega bo'lish mod N bizga barcha rang qiymatlarini hisoblash orqali P rang modini beradi va u bizga barcha rang qiymatlarini hisoblash orqali Q rang modini beradi. Ammo boshqa yo'nalish haqida nima deyish mumkin? Agar tugun diagrammasi uchun rang shartlari tizimida eritma mod P va boshqa yechim mod Q bo'lsa, bu erda P va Q birgalikda prime bo'lsa, bu shartlar tizimi PQ echimiga ega bo'ladimi?
Javob: Ha.
Isbot:
A1, a2 mod P va mod Q ranglarida bir ipning ranglari bo'lsin.
Keyin Xitoy qoldiq teoremasi ikkala shartni qondiradigan bitta butun sonning mavjudligini va o'ziga xosligini kafolatlaydi A mod PQ
A ≡a 1 mod P
A ≡2 mod Q.
Bu A, B, C rang qiymatlarini beradigan har bir iplik uchun takrorlanishi mumkin,... mod PQ.
Har bir kesib o'tishda ikki rang shartlari
(A + B - 2C) mod P = a1 + b1 - 2c1 ≡ 0 mod P
(A + B - 2C) mod Q = a2 + b2 - 2c2 ≡ 0 mod Q
qoniqtirilgan. (A + B - 2C) mod PQning yagona qiymati, ya'ni nol mod P va nol mod Q A + B - 2C ≡ 0 mod PQ. Bu shuni ko'rsatadiki, A,B,C rang qiymatlari,... PQ bo'yash modini ta'minlash.
Barcha musbat butun sonlar bosh faktorizatsiyaga ega bo'lganligi sababli, ular bosh sonlarning kuchlarining mahsuli sifatida yozilishi mumkin. Shuning uchun barcha rangli sonlarni rangli sonlar sifatida barcha toq bosh sonlarning barcha kuchlarini tekshirish orqali topish mumkin. Biz ilgari ko'rgan edik, bosh raqam 2 va 2 ning kuchlari rangli sonlar mumkin emas.
Rangli modul mavjudligini tekshirishni boshlash va agar muvaffaqiyatli bo'lsa, u holda bu bosh sonning kuchayib borayotgan yuqori kuchlari bilan tekshiruvni takrorlash, toki endi bir coulouring mavjud bo'lmaguncha.
Javob: Ha.
Isbot:
A1, a2 mod P va mod Q ranglarida bir ipning ranglari bo'lsin.
Keyin Xitoy qoldiq teoremasi ikkala shartni qondiradigan bitta butun sonning mavjudligini va o'ziga xosligini kafolatlaydi A mod PQ
A ≡a 1 mod P
A ≡2 mod Q.
Bu A, B, C rang qiymatlarini beradigan har bir iplik uchun takrorlanishi mumkin,... mod PQ.
Har bir kesib o'tishda ikki rang shartlari
(A + B - 2C) mod P = a1 + b1 - 2c1 ≡ 0 mod P
(A + B - 2C) mod Q = a2 + b2 - 2c2 ≡ 0 mod Q
qoniqtirilgan. (A + B - 2C) mod PQning yagona qiymati, ya'ni nol mod P va nol mod Q A + B - 2C ≡ 0 mod PQ. Bu shuni ko'rsatadiki, A,B,C rang qiymatlari,... PQ bo'yash modini ta'minlash.
Barcha musbat butun sonlar bosh faktorizatsiyaga ega bo'lganligi sababli, ular bosh sonlarning kuchlarining mahsuli sifatida yozilishi mumkin. Shuning uchun barcha rangli sonlarni rangli sonlar sifatida barcha toq bosh sonlarning barcha kuchlarini tekshirish orqali topish mumkin. Biz ilgari ko'rgan edik, bosh raqam 2 va 2 ning kuchlari rangli sonlar mumkin emas.
Rangli modul mavjudligini tekshirishni boshlash va agar muvaffaqiyatli bo'lsa, u holda bu bosh sonning kuchayib borayotgan yuqori kuchlari bilan tekshiruvni takrorlash, toki endi bir coulouring mavjud bo'lmaguncha.
Sinov va xato yo'li bilan rangni topish uchun qanday maslahatlar bor?
Qaysi harfga qiymat berilishi kerak?
- Keyingi qaysi ipni ranglashni hal qilish uchun, tenglamalarni harflar soni bo'yicha, ya'ni shoshilinch ravishda saralash uchun Enter tugmasini bosing.
- Agar tenglamada bir necha harf bo'lsa, boshqa tenglamalarda uchraydigan harfni tanlang, shunda raqam tayinlanganda ko'proq tenglamalar soddalashadi. Teng ravishda, sichqonchani tenglama ustida harakatlantiring, aylanadagi kesishmani ko'ring va bu kesishmada eng ko'p o'tib ketgan rangsiz ipni bosing.
- ≡ o'ng tomonidagi harflarni chapdagi harflarga qaraganda tezroq hisoblash mumkin. Chapdagi harfni hisoblash uchun 2 ga bo'lish kerak, bu teng bo'lish uchun o'ngga N qo'shishni talab qilishi mumkin. Bu qiyin emas, lekin tanlovda vaqt qimmatlidir. Xuddi shu sababga ko'ra, harfning qiymatini taxmin qilayotganda ≡ chap tomondagi harfni olish mumkin.
- Vaqtni tejash uchun 0..N-1 oralig'idagi qiymatlarni hisoblashdan tashvishlanmang. Qiymatlar salbiy yoki o'zboshimchalik bilan katta bo'lishi mumkin. Agar ular to'g'ri bo'lsa, binafsha tenglama yashil rangga aylanadi va bu eng muhimi.
- Agar tenglamada faqat bitta harf qolgan bo'lsa, u holda fon binafsha rangda bo'ladi va keyin tanlov yo'q, tenglamani yashil qilish uchun qiymatni hisoblash kerak. Ko'rsatmalardagi misollarni ko'ring.
- Yuqorida ko'rsatilganidek Ushbu bo'lim > "Agar bitta rang bo'lsa..." bo'limida barcha harflarning qiymatlari bir xil doimiy qiymat bilan o'zgartirilishi mumkin. Shuning uchun tayinlamoqchi bo'lgan birinchi harfga umumiylikni yo'qotmasdan 0 qiymati berilishi mumkin. Bu harf uchun boshqa qiymatni sinab ko'rmaydi, chunki bu qiymatni har doim nolga o'tkazishi mumkin.
- 2-harfning rangi uchun faqat ikkita holatni ko'rib chiqish kerak: 1) u birinchi harf bilan bir xil qiymatga ega, ya'ni 0 va 2) u boshqa qiymatga ega. Bunday holda faqat 1ni ko'rib chiqish kerak, chunki biz barcha sonlarni 2 bilan ko'paytirish mumkinligini ko'rdik. (N-1) (bu erda N mavjud ranglarning asosiy soni) va hali ham ekvivalent yechimga ega. Iltimos havola Ushbu bo'lim > 'Agar bitta rang bo'lsa ...'. Misol uchun, agar N=5 va biri 2-tayinlangan harf uchun 3 kabi boshqa qiymatni sinab ko'rgan bo'lsa va yechimni olgan bo'lsa, unda bu qiymatni (va boshqa barcha qiymatlarni) 2 bilan ko'paytirish 3 dan 3×2 = 6 ≡ 1 mod 5ni 1 ga aylantiradi. Shuning uchun 2-harfni faqat 0 va 1 sifatida sinab ko'rish kerak.
- Sinovlar ham vaqt masalasidir. Musbat raqamlarga qaraganda tezroq hisoblash uchun salbiy raqamlarni kiritish orqali vaqtni tejash mumkin. Interfeys uchun 0..N-1 diapazonidagi raqamlar kerak emas.
- Tenglama qizil rangga aylanganda, ≡ sharti qondirilmaydi va kamida bitta raqamni o'zgartirish kerak. Keyin boshqa raqamni sinab ko'ring. Raqamlarni o'tkazib yubormaslik uchun 0,1,...,N-1 tartibidagi raqamlarni sinab ko'rish va rang topilganda to'xtash mumkin edi.
- Bekor qilish tugmasini bosish orqali orqaga qaytishda, agar binafsha tenglamani ko'rsa, unda o'ylamasdan bekor qilish tugmasini yana bosish mumkin. Buning sababi shundaki, binafsha tenglama faqat bitta harfga ega va bu harf uchun faqat bitta mumkin bo'lgan qiymat (mod N) mavjud, shuning uchun bu vaziyatda bu harf uchun boshqa qiymatni sinab ko'rish kerak emas.
- Muntazam ravishda qidirish va har qanday rang imkoniyatini o'tkazib yubormaslik uchun har bir o'zgaruvchiga 0 qiymatini tayinlashdan boshlash mumkin, bu arzimas yechimni beradi, so'ngra arzimas bo'lmagan yechimni olish uchun orqaga qaytishni boshlash mumkin.
- Ushbu o'yinda ishlatiladigan tugun diagrammalari allaqachon minimal miqdordagi o'tishlarga ega. Ammo diagrammalar minimal bo'lmasa, avval ularni soddalashtirish foydali bo'ladi. Tezlashtirish uchun yuqoridagi usullar bo'lmasa, N- ranglar soni va C - o'tish soni = iplar soni. O'tish sonini faqat 1 ga kamaytirish harakatni N omiliga kamaytiradi.
Rangsiz tugunlar bormi?
Ha. Rangi bo'lmagan 12 dan kam o'tish joylari bo'lgan tugunlar 10124, 10153, 11n34, 11n42, 11n49, 11n116 va, albatta, tugun. Rasmda tugun 10124 diagrammasi ko'rsatilgan.
Sahifaning yuqori qismidagi "Tuzun-Sikora" deb nomlangan diagramma untugunning cheksiz ko'plab diagrammalaridan biridir va shuning uchun ham rangli emas.
Sahifaning yuqori qismidagi "Tuzun-Sikora" deb nomlangan diagramma untugunning cheksiz ko'plab diagrammalaridan biridir va shuning uchun ham rangli emas.
Ranglarning o'zgarishlari ko'proq va ularni qanday hisoblash mumkin?
Ha, bu qo'shimcha invariantlar echimlarning ko'pligi, mavjud ranglarning har bir soni uchun bitta ko'plik. Quyidagi izohlarni tushunish uchun chiziqli algebra haqida ba'zi bilimlar foydalidir.
Agar tugun diagrammasi C kesishmalariga ega bo'lsa, unda u ham C iplariga ega va shuning uchun shartlar tizimi C×C koeffitsienti matritsasiga ega bo'lib, bu erda har bir qator kesishishni ifodalaydi va ikkita -1 va bitta 2 yoki +1 va -1 dan iborat (Reidemeister I loop kesishma). Har bir ustun bir ipga mos keladi va ipning over-pass va ikkita -1 yoki bitta -1 va bitta +1 kabi ko'p 2 ga ega.
Shartlar bir hil chiziqli tizimni hosil qiladi (o'ng tomonda faqat 0lar mavjud) va savol notrivial chiziqli mustaqil yechimlar (ranglar) mavjud bo'lgan rangli sonlarni modul qilib topishdir.
Chiziqli algebrada bo'lgani kabi, matritsa satrlarni almashtirish va boshqa satrlarga ko'paytirilgan satrlarni qo'shish orqali diagonal shaklga keltiriladi. Bundan tashqari, bu qadamlar ustunlar bilan ham amalga oshiriladi. Bu erda satrlar va ustunlarni raqam bilan ko'paytirishga yo'l qo'yilmaydi, chunki bu matritsa determinanti nolga teng bo'lgan rang raqamini modul qo'shadi va bu qo'shimcha rangni qo'shadi. Buning o'rniga nima qilinadi, bir ustun / satrning 2 nol bo'lmagan komponentlarini qayta-qayta tanlash, masalan A,B, pA + qB = GCD (A,B) ni qondirish uchun kengaytirilgan Yevklid algoritmini ishlatish. P,Q - ikki satr / ustunning ko'paytiruvchilari. Satrlar / ustunlarni almashtirgandan so'ng GCD (A,B) diagonal element bo'ladi. Natijada, Smit normal shakli deb nomlangan diagonal matritsa bo'lib, bu erda odatda yuqori chap burchak 1 bilan boshlanadi va diagonalizdagi keyingi sonning har bir omili bo'lgan raqamlar bilan boshlanadi. Oxirgi diagonal element nolga teng, chunki har bir tugun diagrammasi faqat bitta rangdan foydalanib arzimas rangga ega bo'lishga imkon beradi. Shuning uchun har qanday ustunni va har qanday satrni tashlab ketgandan so'ng Smit normal shaklini hisoblash kifoya.
C×C koeffitsienti matritsasining determinantini hisoblash nolni beradi, chunki ustunlar nolga qo'shiladi. Bir qator va bitta ustunni tashlab ketgandan keyin determinantni hisoblash bitta raqamni beradi, bu Smit normal shaklining diagonali bo'yicha raqamlarning ko'rinishidir. Shunday qilib, Smit normal formasi xuddi shu harakat uchun ko'proq ma'lumot beradi.
Misol: 83 kesishgan ushbu diagramma uchun koeffitsient matritsasi 83×83 o'lchamga ega.
Smit normal shakli yuqori chap burchakda 79 marta 1 bilan boshlangan diagonal ga ega bo'lib, keyin 3, 3, 85837301265 (= 3 x 5 x 5722486751), 0. Bu uchta mustaqil 3-rang va bitta 85837301265-rang mavjudligini anglatadi, bu shuningdek, 5-rangli, 15-rangli, 3x5722486751-rangli va 5x5722486751-rangga ega.
Agar diagrammada rang bo'lmasa, oxirgi holatdagi 0dan tashqari barcha diagonal sonlar 1 ga teng.
Quyidagi diagramma tugun 12a801ga tegishli.
Smit normal shakli (SNF) diagonal to'qqizta 1s, undan keyin 3,45,0. Ushbu shaklda har bir raqam keyingi diagonal sonning omili hisoblanadi. Va rangning ko'pligi - bu omil sifatida uchraydigan diagonal elementlar soni. Shuning uchun bu tugunning har bir diagrammasi ikkita mustaqil 3-rangga va bitta 45-rangga ega, bu esa bitta 5-,9-,15-rangga ega ekanligini anglatadi.
Agar tugun diagrammasi C kesishmalariga ega bo'lsa, unda u ham C iplariga ega va shuning uchun shartlar tizimi C×C koeffitsienti matritsasiga ega bo'lib, bu erda har bir qator kesishishni ifodalaydi va ikkita -1 va bitta 2 yoki +1 va -1 dan iborat (Reidemeister I loop kesishma). Har bir ustun bir ipga mos keladi va ipning over-pass va ikkita -1 yoki bitta -1 va bitta +1 kabi ko'p 2 ga ega.
Shartlar bir hil chiziqli tizimni hosil qiladi (o'ng tomonda faqat 0lar mavjud) va savol notrivial chiziqli mustaqil yechimlar (ranglar) mavjud bo'lgan rangli sonlarni modul qilib topishdir.
Chiziqli algebrada bo'lgani kabi, matritsa satrlarni almashtirish va boshqa satrlarga ko'paytirilgan satrlarni qo'shish orqali diagonal shaklga keltiriladi. Bundan tashqari, bu qadamlar ustunlar bilan ham amalga oshiriladi. Bu erda satrlar va ustunlarni raqam bilan ko'paytirishga yo'l qo'yilmaydi, chunki bu matritsa determinanti nolga teng bo'lgan rang raqamini modul qo'shadi va bu qo'shimcha rangni qo'shadi. Buning o'rniga nima qilinadi, bir ustun / satrning 2 nol bo'lmagan komponentlarini qayta-qayta tanlash, masalan A,B, pA + qB = GCD (A,B) ni qondirish uchun kengaytirilgan Yevklid algoritmini ishlatish. P,Q - ikki satr / ustunning ko'paytiruvchilari. Satrlar / ustunlarni almashtirgandan so'ng GCD (A,B) diagonal element bo'ladi. Natijada, Smit normal shakli deb nomlangan diagonal matritsa bo'lib, bu erda odatda yuqori chap burchak 1 bilan boshlanadi va diagonalizdagi keyingi sonning har bir omili bo'lgan raqamlar bilan boshlanadi. Oxirgi diagonal element nolga teng, chunki har bir tugun diagrammasi faqat bitta rangdan foydalanib arzimas rangga ega bo'lishga imkon beradi. Shuning uchun har qanday ustunni va har qanday satrni tashlab ketgandan so'ng Smit normal shaklini hisoblash kifoya.
C×C koeffitsienti matritsasining determinantini hisoblash nolni beradi, chunki ustunlar nolga qo'shiladi. Bir qator va bitta ustunni tashlab ketgandan keyin determinantni hisoblash bitta raqamni beradi, bu Smit normal shaklining diagonali bo'yicha raqamlarning ko'rinishidir. Shunday qilib, Smit normal formasi xuddi shu harakat uchun ko'proq ma'lumot beradi.
Misol: 83 kesishgan ushbu diagramma uchun koeffitsient matritsasi 83×83 o'lchamga ega.
Smit normal shakli yuqori chap burchakda 79 marta 1 bilan boshlangan diagonal ga ega bo'lib, keyin 3, 3, 85837301265 (= 3 x 5 x 5722486751), 0. Bu uchta mustaqil 3-rang va bitta 85837301265-rang mavjudligini anglatadi, bu shuningdek, 5-rangli, 15-rangli, 3x5722486751-rangli va 5x5722486751-rangga ega.
Agar diagrammada rang bo'lmasa, oxirgi holatdagi 0dan tashqari barcha diagonal sonlar 1 ga teng.
Quyidagi diagramma tugun 12a801ga tegishli.
Smit normal shakli (SNF) diagonal to'qqizta 1s, undan keyin 3,45,0. Ushbu shaklda har bir raqam keyingi diagonal sonning omili hisoblanadi. Va rangning ko'pligi - bu omil sifatida uchraydigan diagonal elementlar soni. Shuning uchun bu tugunning har bir diagrammasi ikkita mustaqil 3-rangga va bitta 45-rangga ega, bu esa bitta 5-,9-,15-rangga ega ekanligini anglatadi.
Tugunlarni bo'yash statistikasi
Qandaydir o'lchamga qadar bosh tugunlarning mumkin bo'lgan ranglari haqida umumiy ma'lumot bormi?
Matn faylida
https://cariboutests.com/qi/knots/colour3-15-N.txt o'tish raqami ≦ 15 bo'lgan har bir tugun uchun 0 yoki 1 bo'lmagan Smit normal shaklidagi barcha yozuvlar ro'yxati keltirilgan. Bu raqamlar bitta diagrammadan hisoblab chiqilgan, lekin ular o'zgaruvchan va shuning uchun ushbu tugunning har qanday diagrammasidan hisoblanganda bir xil. Agar siz rangli tugunlarning rasmlarini yoqtirsangiz, unda siz "Uy" > 'Plakatlar' https://cariboutests.com/images/posters/knot_colouring_portrait.pdfbosh sahifasini bosish orqali bizning poster to'plamimizdan plakatni yuklab olishingiz mumkin.
N-rangi invariant sifatida qanchalik kuchli?
Quyidagi jadvalda ko'proq rang invariantlaridan foydalanish tugunlarning invariant sinflari sonini ko'paytiradi va shu bilan har bir sinfda o'rtacha tugunlar sonini kamaytiradi. O'ng ustunda rangli invariant sinflar sonining (#cr - 3) ildizi qanday qilib taxminan doimiy bo'lib qolishini ko'rsatadi, bu erda #cr tugunlarning kesishmalari soni.
Jadval 1: Statistika rount rang o'zgarishlari
# of cr: # of crossings
# ning kn: # tugunlar
# of cl1: # of classes when consider only list of prime coloring numbers
# of cl2: # of classes when consider only list of multiplicities of prime coloring numbers
# of cl3: # of classes when consider list of Smith Normal Form Entries <> 1
ABS: EXP (LN(NOOFCL3 [cr]) / (cr-3))
= (cr-3)-chi ildiz (# of cl3)
Jadval 1: Statistika rount rang o'zgarishlari
# of cr: # of crossings
# ning kn: # tugunlar
# of cl1: # of classes when consider only list of prime coloring numbers
# of cl2: # of classes when consider only list of multiplicities of prime coloring numbers
# of cl3: # of classes when consider list of Smith Normal Form Entries <> 1
ABS: EXP (LN(NOOFCL3 [cr]) / (cr-3))
= (cr-3)-chi ildiz (# of cl3)
| # cr | # of kn | # of cl1 | kn/cl1 | # CL2 | kn/cl2 | # of cl3 | kn/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 |
Qanday qilib C kesishgan tugunlar uchun eng katta rang soni C ga bog'liq?
Agar C (<16) and finds from these knots the one with the highest colouring number Nmaks) raqamini kesib o'tgan barcha tugunlarni olsa, quyidagi jadval shuni ko'rsatadiki, C 1 ga ko'payganda Nmax taxminan 1,7 omilga o'sadi.
Jadval 2: B (C) = Nmax1 / (C-1) jadvali
Jadval 2: B (C) = Nmax1 / (C-1) jadvali
| C | Nmaks | Tugun | B(C) |
|---|---|---|---|
| 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 |
Ranglarni hisoblaydigan kompyuter dasturi bormi?
AsciiKnots koeffitsient matritsasining Smit normal shaklini hisoblash orqali berilgan tugun diagrammasi uchun barcha rangli sonlarni hisoblash uchun kompyuter dasturi. Agar tugun diagrammasida juda ko'p kesishmalar bo'lmasa, u shuningdek, ma'lum bir rang raqami uchun optimallashtirilgan sinov va xato qidirish yo'li bilan barcha ranglarni yoki barcha rang raqamlarini, shu jumladan ularning ranglarini hisoblaydi.Ranglardan tashqari, dastur ko'proq narsani hisoblashi mumkin. Uni yuklab olish mumkin
https://cariboutests.com/games/knots/AsciiKnots.tar.gz. AsciiKnots Linux ostida ishlaydi. Qat'iy Windows foydalanuvchilari Ubuntu linuxni Windows 10 ostida dastur sifatida bepul o'rnatishlari mumkin. Eski yuklab olingan versiyalarni olib tashlash, so'nggi versiyani yuklab olish, ochish va ishga tushirish uchun Linux buyruqlari mavjud
rm AsciiKnots.tar.gz
wget https://cariboutests.com/games/knots/AsciiKnots.tar.gz
tar xfz AsciiKnots.tar.gz
./AsciiKnots
"Asboblar" > "Rangli tugun" ni tanlagandan so'ng, https://cariboutests.com/games/knots/knoteditor/'da cheklangan bo'yash funksiyasi ham mavjud
Manbalar
[1] R. H. Fox, Metacyclic invariants of knots and links, Canadian Journal of Mathematics 22 (1970) 193−201.
[2] J. H. Przytycki, 3-rang va tugunlarning boshqa elementar invariantlari. Banach Center Publications, vol. 42, "Knot Theory", Warszawa, 1998, 275−295.
[3] D. Rolfsen, Tugunlar va havolalar jadvali. Ilova C tugunlar va havolalarda. Wilmington, DE: Publish or Perish Press, pp. 280-287, 1976.
[4] J. C. Cha va C. Livingston, KnotInfo: Knot Invariants jadvali, http://www. indiana.edu/~knotinfo
[5] "O'tish raqami 15 gacha bo'lgan tugunlarning ranglar tasnifi", https:// cariboutests.com/qi/knots/colour3-15.txt
[6] T. Wolf, "A Knot Workbench", https://cariboutests.com/games/knots/AsciiKnots.tar.gz
[2] J. H. Przytycki, 3-rang va tugunlarning boshqa elementar invariantlari. Banach Center Publications, vol. 42, "Knot Theory", Warszawa, 1998, 275−295.
[3] D. Rolfsen, Tugunlar va havolalar jadvali. Ilova C tugunlar va havolalarda. Wilmington, DE: Publish or Perish Press, pp. 280-287, 1976.
[4] J. C. Cha va C. Livingston, KnotInfo: Knot Invariants jadvali, http://www. indiana.edu/~knotinfo
[5] "O'tish raqami 15 gacha bo'lgan tugunlarning ranglar tasnifi", https:// cariboutests.com/qi/knots/colour3-15.txt
[6] T. Wolf, "A Knot Workbench", https://cariboutests.com/games/knots/AsciiKnots.tar.gz
Follow or subscribe for updates: