300000
22772
11746
English | Français | فارسی | 中文 | Українська | Azerbaijani | ខ្មែរ | Tiếng Việt | Bahasa Melayu | Deutsch | O'zbek | Русский
11746
Düyü Rəngləmə
Əgər siz sadəcə bu çətinliyin arxasında duran nəzəriyyəni yox, necə həll olunması ilə maraqlanırsınızsa, onda "Sınaq və xəta ilə rəng tapmaq üçün hansı göstərişlər var?"
İnvariantlar haqqında
Aşağıdakı üç diaqramdan ikisi
düyünü kəsmədən bir-birinə deformasiya oluna bilər.
İnvariant nümunəsi sonsuz sayda ekvivalent diaqramlardan hər hansı birinin malik ola biləcəyi minimum kəsişmə sayıdır. Bu invariantı tapmaq çətindir, çünki sonsuz sayda diaqramı yoxlamaq mümkün deyil.
Bəs verilmiş diaqram üçün hesablana bilən invariant nə ola bilər? Diaqramı istənilən şəkildə deformasiya edə bildiyi zaman deformasiyada hansı xüsusiyyətin dəyişmədiyini təsəvvür etmək çətindir.
Üçrənglilik invariantdır.
N-rəngkarlıq
düyünsüz
Tuzun-Sikora
8_19
düyünü kəsmədən bir-birinə deformasiya oluna bilər.
Səncə, onlar hansılardır?
İki diaqramın müxtəlif düyünlərə aid olub-olmadığını müəyyən etmək üçün rəng qabiliyyətindən necə istifadə edəcəyinizi aşağıda öyrənəcəksiniz. Üçrəngliliyi tədqiq etməklə hansı diaqramların bir-birinə deformasiya oluna bilməyəcəyini görmək olar.
Əks halda, aşağıdakı ardıcıllıq Tuzun-Sikora diaqramının dairəyə necə sadələşdirilməsini göstərir.
Tuzun-Sikora diaqramının düyünsüz olduğunu sübut edin.
Düyünsüz diaqram və Tuzun-Sikora sonsuz sayda başqa deformasiyalarla birlikdə eyni riyazi düyünə düyünə aiddir. İki diaqram arasında nə qədər böyük olsalar da, heç vaxt bir-birinə deformasiya oluna bilməyəcəyinə necə qərar vermək olar? Diaqram deformasiya edildikdə dəyişməyən xassə “invariant” (qeyri-dəyişən) adlanır.Əks halda, aşağıdakı ardıcıllıq Tuzun-Sikora diaqramının dairəyə necə sadələşdirilməsini göstərir.
Tuzun-Sikora diaqramının düyünsüz olduğunu sübut edin.
İlk proyeksiya
Reidemeister 3 hərəkət
Hərəkətdən sonra və uzandıqdan sonra
Keçməni azaldan ötürmə hərəkəti
Hərəkətdən sonra və uzandıqdan sonra
Keçməni azaldan ötürmə hərəkəti
Hərəkətdən sonra və uzandıqdan sonra
Keçməni azaldan ötürmə hərəkəti
Hərəkətdən sonra və uzandıqdan sonra
Keçməni azaldan ötürmə hərəkəti
Hərəkətdən sonra və uzandıqdan sonra
Keçməni azaldan ötürmə hərəkəti
Hərəkətdən sonra
Keçməni azaldan ötürmə hərəkəti
Hərəkətdən sonra
Ridemeister 2 hərəkət
Hərəkətdən sonra
Reidemeister 1 hərəkət
Hərəkətdən sonra
Reidemeister 1 hərəkət
Hərəkətdən sonra
Reidemeister 1 hərəkət
Hərəkətdən sonra
Reidemeister 1 hərəkət
Hərəkətdən sonra
İnvariant nümunəsi sonsuz sayda ekvivalent diaqramlardan hər hansı birinin malik ola biləcəyi minimum kəsişmə sayıdır. Bu invariantı tapmaq çətindir, çünki sonsuz sayda diaqramı yoxlamaq mümkün deyil.
Bəs verilmiş diaqram üçün hesablana bilən invariant nə ola bilər? Diaqramı istənilən şəkildə deformasiya edə bildiyi zaman deformasiyada hansı xüsusiyyətin dəyişmədiyini təsəvvür etmək çətindir.
Üçrənglilik invariantdır.
Bunu izah etmək üçün qələmi qaldırmadan çəkilə bilən düyün xəttinin hissələri olan iplərdən istifadə edirik. Hər kəsişmədə 3 tel qarşılaşır, biri aşırım, biri isə hər tərəfdəndir. Hər bir ipə 3 rəngdən birini vermək olarsa, düyün diaqramı üçrəngli olur ki, hər kəsişmədə 2 rəng deyil, 1 və ya 3 rəng olsun. Hamısını bir rənglə rəngləmək həmişə mümkündür və nəzərə alınmır. Bir yerdə ən azı 2 rəngdən istifadə etmək lazımdır.
3 diaqramdan hansı üçrənglidir?
Düyün yalnız bir ipdən ibarətdir və buna görə də üçrəngli deyil. 2-ci düyün düyünə görə deformasiya olunur və buna görə də rənglənmir. Bunu sonra sübut edəcəyik. Digər düyün üçrənglidir və buna görə də yuxarıda göstərildiyi kimi heç vaxt düyünlərə deformasiya edilə bilməz.
Üçrənglilik zəif invariantdır, çünki o, yalnız mümkün olan ən kiçik miqdarda məlumatı ehtiva edir, sadəcə bəli/xeyr. Bu invariant yalnız bütün düyünləri iki qrupa, üçrəngli olan və olmayan düyünlərə bölə bilir.
N-rəngkarlıq
Daha güclü invariant N rənglərinin mövcud olduğu və hər bir rəng 0,1,2,3,...,N-1 rəqəmlərindən birini təmsil edən N-Rəngi-dir. Hər kəsişmədə yerinə yetirilməli olan şərt odur ki, 2 alt ipin rənglərinin cəmi çıx 2 vur üst ipin rəngləri N-nin bölünənidir. Başqa sözlə, əgər rənglər a,b,c olarsa, onda k bölünəni belə olmalıdır ki, a+b-2c = kN. Riyazi ekvivalent, lakin daha geniş yayılmış formul a + b ≡ 2c mod N. Bu, o deməkdir ki, ≡ işarəsinin hər iki tərəfi N-ə bölünəndə qalıq eyni olur. İş modulu (mod) bəzi ədədlər Modul Arifmetik adlanır və bir çox maraqlı və faydalı qaydalara malikdir.
Bir çox suallar yaranır.
Bir çox suallar yaranır.
Modulyar arifmetika ilə tanışlıq
Modulyar arifmetikanın bütün ifadələrini k bölünənini təqdim edərək və ≡ tənliyini normal tənlik kimi yenidən düzəltməklə isbat edə bilərik. Qeydi qısaltmaq üçün istifadə edirik
'tam ədəd' üçün 'tam ədəd',
'p vur q' üçün 'pq',
∃ var,
':' 'xassə ' üçün və
'A → B 'A-nın B-ni izləməsi' üçün istifadə edilir
Sübut: əgər a ≡ b mod N və c ≡ d mod N olarsa, onda (a+c) ≡ (b+d) mod N
Modulyar tənlik a ≡ b mod N deyilir ki, a və b yalnız p çoxluğu ilə fərqlənir.
yəni a = b + mp xassəsinə malik m bölünəni olmalıdır. Qısa olaraq bu, belədir
(a ≡ b mod N) → (∃ tam ədəd m: a = b + mp)
c ≡ d mod N) → (∃ tam ədəd n: c = d + np)
Hər iki bərabərliyi əlavə etməklə a + c = b + mp + d + np = b + d + (m+n)p
→ a + c ≡ (b + d) mod N
yəni a = b + mp xassəsinə malik m bölünəni olmalıdır. Qısa olaraq bu, belədir
(a ≡ b mod N) → (∃ tam ədəd m: a = b + mp)
c ≡ d mod N) → (∃ tam ədəd n: c = d + np)
Hər iki bərabərliyi əlavə etməklə a + c = b + mp + d + np = b + d + (m+n)p
→ a + c ≡ (b + d) mod N
İsbat edin: əgər bir ≡ b mod N sonra hər hansı bir tam m ədədi üçün bizdə ma ≡ mb mod N var
(a ≡ b mod N) → (∃ tam ədəd k: a = b + kN)
m-ə vurduqdan sonra alırıq ki,
ma = mb + mkN
→ ma ≡ mb mod N
m-ə vurduqdan sonra alırıq ki,
ma = mb + mkN
→ ma ≡ mb mod N
İsbat edin: əgər ≡ b mod (PQ) , a ≡ b mod P.
a ≡ b mod (PQ)
→ ∃ tam ədəd k: a = b + k(PQ)
→ a = b + (kQ)P
→ ≡ b mod P
Bəs əks istiqamət haqqında nə demək olar?
Nəyə görə tərsinin doğru olmadığı inandırıcıdır?
→ ∃ tam ədəd k: a = b + k(PQ)
→ a = b + (kQ)P
→ ≡ b mod P
Bəs əks istiqamət haqqında nə demək olar?
Əks nümunə budur.
6 ≡ 1 mod 5, ancaq
6 ≢ 1 mod 15, çünki 6 və 1 15-in bölünəni qədər fərqlənmir.
6 ≡ 1 mod 5, ancaq
6 ≢ 1 mod 15, çünki 6 və 1 15-in bölünəni qədər fərqlənmir.
Nəyə görə tərsinin doğru olmadığı inandırıcıdır?
Bir tənlikdə mod N ≡ hər iki tərəfi N müxtəlif dəyərlərə malik ola bilər. Bir tənlik modunda (NM) ≡ hər iki tərəfi NM fərqli dəyərlərə sahib ola bilər. Buna görə də bir əlaqə mod (NM) mod N əlaqəsindən daha çox məlumat daşıyır. Moddan (NM) N-i dəyişdirmək üçün gedərək məlumatı atmaq asandır, lakin heç nədən informasiya yaratmağın əksi qeyri-mümkündür. Kobud desək, bu mənada = istifadə edilən normal bərabərlik ≡ mod ∞(sonsuzluğa) bərabərdir.
Şərh kimi, bu, belə bir ehtimal açır ki, həllin tam ədədlərlə bağlı olduğu və bir nəfərin '=' istifadə edərək tənlik şəklində həll axtardığı və həlldə ədədlərin mütləq dəyəri üçün yuxarı bir sərhəd olduğunu bilən tətbiqlərdə, strategiya bəzi kiçik sadə N ədədi üçün həllə mod N tapmaqla başlamaq və sonra hesablamaq ola bilər , mod N^2, sonra mod N^4 və s. nə qədər ki, N-in qüvvəti həll üçün yuxarı hədddən böyük olana qədər modu buraxmaq olar və sonra = istifadə edərək dəqiq həll əldə edə bilərsiniz.
Hensel qaldırma adlı belə bir üsul birdəyişənli çoxhədləri əvvəlcə bəzi kiçik sadə ədədlərə, sonra isə tam ədədlər üzərində vuruqlara ayırmaq üçün istifadə edilə bilər.
İsbat: a + b ≡ ((a mod N) + (b mod N)) mod N
a və a mod N-nin bölünəni qədər fərqlənir: a = (a mod N) + pN
b və b mod N-nin bölünəni qədər fərqlənir: 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 və b mod N-nin bölünəni qədər fərqlənir: 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
İsbat edin: ab ≡ ((a mod N)(b mod N)) mod N
a və a mod N N-in bölünəni qədər fərqlənir: a = (a mod N) + pN
b və b mod N N-in bölünəni qədər fərqlənir: 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 və b mod N N-in bölünəni qədər fərqlənir: 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
İsbat: əgər P(x,y,...) dəyişənlərdə çoxhədli x,y,... sonra P(x,y,...) ≡ P((x mod N),(y mod N),...) mod N
Hər bir çoxhədli hasil kimi yazıla bilər, buna görə də yuxarıdakı iki qaydanı tətbiq etmək bunu dəfələrlə isbat edir.
Sübut edin: Arifmetik modulda sadə ədəd, tam ədədlərə bölməklə yenidən tam ədədlər verir.
Biz bir prime sayı p və hər hansı bir integer üçün ≢ 0 mod N üçün inverse 1/a mod N də integer olduğunu göstərməklə başlayır. Biz ≢ 0 mod N tələb edirik, çünki modulyar arifmetikada da sıfıra görə bölünmə mümkün deyil.
Qoy u ≡ 1/a mod N olsun. U üçün N modunun tərsi olması o deməkdir ki,
ua ≡ 1 mod N
→ ∃ tam ədəd k: ua = 1 + kp
Bu, Bézout's identityformasına malikdir: ua + vp = ƏBOB(a,p) burada GCD(a,p) a,p-nin Ən Böyük Ortaq Bölənidir və burada v=-k. Çünki p sadə ədəddir və a p-nin bölünəni deyil, buna görə də ƏBOB(a,p)=1.
Bézout's identity' də u,v bölünənləri genişləndirilmiş Evklid alqoritmi ilə hesablana bilər və hər ikisi, u,v, tam ədədlərdir.
Əgər u=1/a N tam ədədidirsə, b/a = bu da göstərilməli olan N tam ədədi moddur.
Nümunə: 1/3 ≡ 5 mod 7 çünki 1 = 3(1/3) ≡ 3(5) = 15 = 2(7) + 1 ≡ 1 mod 7.
ma ≡ mb mod N nə vaxt a ≡ b mod N ilə ekvivalentdir?
Gördük ki, a ≡ b mod N-dən ma ≡ mb mod N-ni izləyir. k ≡ 1/m mod N tam ədədi ilə vursaq, eynilik alarıq. Bu o deməkdir ki, m-ə vurduqdan sonra elə l tam ədədi yaranır kiki, mk = 1 + lN, hansı ki Bézout's identity'nin 1 = ƏBOB(m,N) ilə eyniliyi (m,N-nin Ən Böyük Ortaq Böləni), buna görə də m və N ma ≡ mb mod N və a ≡ b mod N eyniliyin üçün qarşılıqlı sadə ədədlər olmalıdırlar.
Çin Qalığı Teoremi.
N-dan asılı olmaq üçün modulyar tənlik mod N-də informasiya məzmunu haqqında daha əvvəl danışmışdıq. İki modulyar tənliyi daha kiçik modul ədədlərlə daha böyük ədədlə birinə birləşdirmək mümkündürmü?
Çin Qalıq Teoremi belə qeyd edir.
Əgər iki tənlik üçün
x ≡ a1 mod N1
x ≡a 2 mod N2
Bölənlər N1,N 2 qarşılıqlı sadədirsə, burada x üçün p1p2 bölünənlərinə qədər sadəcə tək qiymət mövcuddur, hansı ki hər iki modulyar tənliyi ödəyir.
Həlli əldə etməyin yollarından biri genişləndirilmiş Euclidean alqoritmindən istifadə edərək Bézout-un şəxsiyyət m1N1 + m2N2 = 1 hesablama ilə m1,m 2 və sonra formuldan istifadə edirik
x = a1m2N2 + a2m1M1
= a1(1 - m1N1) + a2m1N1
= a1 + (a2 - a1)m1N1
x ≡1 mod N1 və ekvivalent x = a2 + (a1 - a2)m2N2 göstərilir ki, bu da x ≡2 mod N2 göstərir.
Əgər birinin ikidən çox modulyar tənlikləri varsa, onda biri bir modulyar tənlik şəklində həll olana qədər onlardan ikisini dəfələrlə bir-bir əvəz edə bilər. Hər bir əvəzetmədə yeni bölən sayı birləşdirilmiş tənliklərin iki bölünəninin hasilinə çevrilərək artır.
Çin Qalıq Teoremi belə qeyd edir.
Əgər iki tənlik üçün
x ≡ a1 mod N1
x ≡a 2 mod N2
Bölənlər N1,N 2 qarşılıqlı sadədirsə, burada x üçün p1p2 bölünənlərinə qədər sadəcə tək qiymət mövcuddur, hansı ki hər iki modulyar tənliyi ödəyir.
Həlli əldə etməyin yollarından biri genişləndirilmiş Euclidean alqoritmindən istifadə edərək Bézout-un şəxsiyyət m1N1 + m2N2 = 1 hesablama ilə m1,m 2 və sonra formuldan istifadə edirik
x = a1m2N2 + a2m1M1
= a1(1 - m1N1) + a2m1N1
= a1 + (a2 - a1)m1N1
x ≡1 mod N1 və ekvivalent x = a2 + (a1 - a2)m2N2 göstərilir ki, bu da x ≡2 mod N2 göstərir.
Əgər birinin ikidən çox modulyar tənlikləri varsa, onda biri bir modulyar tənlik şəklində həll olana qədər onlardan ikisini dəfələrlə bir-bir əvəz edə bilər. Hər bir əvəzetmədə yeni bölən sayı birləşdirilmiş tənliklərin iki bölünəninin hasilinə çevrilərək artır.
N-rəngliliyin invariant olduğunu necə sübut etmək olar?
Daha əvvəl izah edildiyi kimi Bəzi Düşündürücü Məqamlar > Təriflər > Reidemeister hərəkətləri ilə giriş, 3 Ridemeister hərəkətləri bir düyün diaqramının hər hansı bir deformasiyası yerinə yetirmək üçün kifayətdir. Buna görə də invariant olmaq üçün yalnız bu 3 hərəkətin altında xassənin dəyişmədiyini göstərmək lazımdır.
Necə göstərə bilərik ki, mənim hərəkət etdiyim Reidemeister rənglənməni dəyişmir?
Əgər iplərin rəngləri göstərildiyi kimi A və B olarsa, onda rəngləmə vəziyyəti sol şəkil A + B ≡ 2B mod N və sağ şəkil B + A ≡ 2A mod N tələb edir. Hər iki halda B = A həlldir:
Bu o deməkdir ki, Reidemeister I gedişi yerinə yetirməklə rəngi dəyişmir.
Reidemeisterin II gedişin rəngini dəyişmədiyini necə göstərmək olar?
Əgər iplərin rəngləri göstərildiyi kimi A,B və C olarsa, onda C sol şəkildə B + C ≡ 2A mod N vəziyyətindən unikal olaraq müəyyən edilir ki, C ≡ (2A - B mod N) və sağ şəkildə A + C ≡ 2B mod N so C ≡ (2B - A mod N). Bu, Reidemeister II gedişini yerinə yetirərkən yeni ipin rəngini müəyyən edir. Rənglənmə təsir etmir.
Reidemeisterin III gedişin rəngini dəyişmədiyini necə göstərə bilərik?
Əgər iplərin rəngləri göstərildiyi kimi A,B,C,D,E,F və G olarsa, onda sol tərəfdəki üç şərt
A + D ≡ 2C mod N
E + F ≡ 2D mod N
F + B ≡ 2C mod N .
Daxili F ipini aradan qaldırmaqla xarici iplərdə vəziyyət yaranır
2D - E ≡ 2C - B mod N istifadə etməklə A + D ≡ 2C mod N sadələşdirir
2D - E ≡ A + D - B mod N və beləliklə A - B - D + E ≡ 0 mod N.
Sağ tərəfdəki 3 şərt
E + G ≡ 2C mod N
G + B ≡ 2A mod N
A + D ≡ 2C mod N
Daxili G ipini aradan qaldırmaqla xarici iplərdə vəziyyət yaranır
2C - E ≡ 2A - B mod N istifadə etməklə 2C ≡ A + D mod N sadələşdirir
A + D - E ≡ 2A - B mod N və beləliklə 0 ≡ A - B - D + E mod N.
F və G göründükləri əlaqələrin hər hansı birindən hesablanır.
Belə qənaətə gəlirik ki, hər iki diaqram üçün xarici iplərin rənglərində olan şərait eynidir: A + D ≡ 2C mod N və A - B - D + E ≡ 0 mod N.
Buna görə də ya hər iki diaqramın rəngi var, ya da heç birinin rəngi yoxdur və buna görə də III Ridemeister =gedişləri altında rəngləmə dəyişkəndir.
Necə göstərə bilərik ki, mənim hərəkət etdiyim Reidemeister rənglənməni dəyişmir?
Əgər iplərin rəngləri göstərildiyi kimi A və B olarsa, onda rəngləmə vəziyyəti sol şəkil A + B ≡ 2B mod N və sağ şəkil B + A ≡ 2A mod N tələb edir. Hər iki halda B = A həlldir:
Bu o deməkdir ki, Reidemeister I gedişi yerinə yetirməklə rəngi dəyişmir.
Reidemeisterin II gedişin rəngini dəyişmədiyini necə göstərmək olar?
Əgər iplərin rəngləri göstərildiyi kimi A,B və C olarsa, onda C sol şəkildə B + C ≡ 2A mod N vəziyyətindən unikal olaraq müəyyən edilir ki, C ≡ (2A - B mod N) və sağ şəkildə A + C ≡ 2B mod N so C ≡ (2B - A mod N). Bu, Reidemeister II gedişini yerinə yetirərkən yeni ipin rəngini müəyyən edir. Rənglənmə təsir etmir.
Reidemeisterin III gedişin rəngini dəyişmədiyini necə göstərə bilərik?
Əgər iplərin rəngləri göstərildiyi kimi A,B,C,D,E,F və G olarsa, onda sol tərəfdəki üç şərt
A + D ≡ 2C mod N
E + F ≡ 2D mod N
F + B ≡ 2C mod N .
Daxili F ipini aradan qaldırmaqla xarici iplərdə vəziyyət yaranır
2D - E ≡ 2C - B mod N istifadə etməklə A + D ≡ 2C mod N sadələşdirir
2D - E ≡ A + D - B mod N və beləliklə A - B - D + E ≡ 0 mod N.
Sağ tərəfdəki 3 şərt
E + G ≡ 2C mod N
G + B ≡ 2A mod N
A + D ≡ 2C mod N
Daxili G ipini aradan qaldırmaqla xarici iplərdə vəziyyət yaranır
2C - E ≡ 2A - B mod N istifadə etməklə 2C ≡ A + D mod N sadələşdirir
A + D - E ≡ 2A - B mod N və beləliklə 0 ≡ A - B - D + E mod N.
F və G göründükləri əlaqələrin hər hansı birindən hesablanır.
Belə qənaətə gəlirik ki, hər iki diaqram üçün xarici iplərin rənglərində olan şərait eynidir: A + D ≡ 2C mod N və A - B - D + E ≡ 0 mod N.
Buna görə də ya hər iki diaqramın rəngi var, ya da heç birinin rəngi yoxdur və buna görə də III Ridemeister =gedişləri altında rəngləmə dəyişkəndir.
Rəngləmənin triviallığı, ekvivalentliyi və sərbəstliyi
Əgər birinin bir rənglənməsi varsa, ondan istənilən düyün diaqramı üçün daha hansı rəngləri əldə etmək olar?
Rəngləmə şərtlərinin hər birində A + B ≡ 2C mod N forması var. A - C ≡ C - B mod N kimi yazaq.
1) Eyni S sabitini əlavə edərkən, rəngdəki fərqlər dəyişmir
(A+S) - (C+S) = A - C + S - S = A - C və
(C+S) - (B+S) = C - B + S - S = C - B və
buna görə də şərtlər hələ də ödəyir.
2) Əvvəllər modul arifmetikanın bir qaydası olaraq gördük ki, biz ≡-nin hər iki tərəfini N-lə qarşılıqlı sadə olan ədədlə vura bilərik və tənliklər sisteminin ekvivalent həllini ekvivalent rəngləmə əldə edə bilərik.
1) Eyni S sabitini əlavə edərkən, rəngdəki fərqlər dəyişmir
(A+S) - (C+S) = A - C + S - S = A - C və
(C+S) - (B+S) = C - B + S - S = C - B və
buna görə də şərtlər hələ də ödəyir.
2) Əvvəllər modul arifmetikanın bir qaydası olaraq gördük ki, biz ≡-nin hər iki tərəfini N-lə qarşılıqlı sadə olan ədədlə vura bilərik və tənliklər sisteminin ekvivalent həllini ekvivalent rəngləmə əldə edə bilərik.
Rəng mod 2-ninmənası varmı?
Xeyr, N=2 üçün rəngləmə əhəmiyyətsizdir.
C rəngi ilə birincinin altından keçdikdən sonra B kimi davam edən A rəngli ipdən başlayaq. Sonra A, B, C A + B ≡ 2C mod 2 vasitəsilə və hər iki tərəfə B əlavə etdikdən sonra A ≡ B ilə əlaqələndirilir. mod 2, çünki 2B ≡ 2C ≡ 0 mod 2. Bütün kəsişmələrdə bu mülahizəni davam etdirməkdən belə nəticə çıxır ki, bütün iplər ya cüt rəngə (0), ya da tək rəngə (1) malikdir. Bu, əhəmiyyətsiz bir rəng verir.
C rəngi ilə birincinin altından keçdikdən sonra B kimi davam edən A rəngli ipdən başlayaq. Sonra A, B, C A + B ≡ 2C mod 2 vasitəsilə və hər iki tərəfə B əlavə etdikdən sonra A ≡ B ilə əlaqələndirilir. mod 2, çünki 2B ≡ 2C ≡ 0 mod 2. Bütün kəsişmələrdə bu mülahizəni davam etdirməkdən belə nəticə çıxır ki, bütün iplər ya cüt rəngə (0), ya da tək rəngə (1) malikdir. Bu, əhəmiyyətsiz bir rəng verir.
Rəng mod (2N), yəni cüt ədədin modu haqqında nə demək olar?
Yuxarıda gördük ki, ya bütün rənglər ya cüt, ya da təkdir. Əgər onlar cütdürsə, onların hamısını rəng mod N məlumat itkisi olmadan 2 -yə bölə bilərik.Əgər onların hamısı təkdirsə, bütün rənglərə 1 əlavə edə və bütün rənglərin bərabər olduğu ekvivalent rəng və 2 vuruğunu çıxardaraq ekvivalent rəngləmə mod N əldə edə bilək.
Nəticədə, hər bir rəngləmə mod (2N) rəngləmə mod N-ə bərabərdir.
Nəticədə, hər bir rəngləmə mod (2N) rəngləmə mod N-ə bərabərdir.
Hansı N üçün N-rəngi faydalıdır və əhəmiyyətsiz deyil?
N>1 tək ədədi üçün rəngləmə mod N mənalıdır.
Bütün rəngləmələri mod P bilmək və P və Q-nin bütün rənglənmə modlarını (PQ) bilmək üçün P və Q-nin birgə olduğu yerləri dəyişdirmək kifayətdirmi?
Əgər N mürəkkəb ədəddirsə, yəni hər iki vuruğu 1 deyilsə, onda P və Q-nün qarşılıqlı sadə ədəd olamsı ilə olması ilə N=PQ kimi yazmaq olar. Rəngləmə şərtlərinin həllinə malik mod N bütün rəng qiymətləri mod P hesablayaraq bizə rəngləmə mod P verir və bütün rəng qiymətlərini hesablayaraq rəngləmə mod Q verir. Bəs digər istiqamət haqqında nə demək? Əgər düyün diaqramı üçün rəngləmə şərtləri sistemi həll mod P və başqa bir həll mod Q varsa, burada P və Q birgədir, bu şərtlər sisteminin mod PQ həlli varmı?
Cavab: Bəli.
İsbat:
Bir1, a2 rəngli bir ipin rəngləri olsun mod P və mod Q.
Sonra Çin Qalıq Teoremi hər iki şərti ödəyən bir tam ədəd A mod PQ-nin mövcudluğuna və unikallığına zəmanət verir
A ≡1 mod P
A ≡2 mod Q.
Rəng dəyərləri verən hər ip üçün bu təkrarlana bilər A,B,C,... mod PQ.
Hər bir keçiddə iki rəngləmə şəraitində
(A + B - 2C) mod P = a1 + b1 - 2c1 ≡ 0 mod P
(A + B - 2C) mod Q = a2 + b2 - 2c2 ≡ 0 mod Q
ödəyir. Sıfır mod P olan və sıfır mod Q olan (A + B - 2C) mod PQ-nün yeganə qiyməti A + B - 2C ≡ 0 mod PQ-dür. Bu, onu göstərir ki, rəng dəyərləri A,B,C,... rəngləmə mod PQ-nü təmin edir.
Bütün müsbət tam ədədlərin sadə vuruqlarına ayrılması ilə onları sadə ədədlərin qüvvətlərinin hasili kimi yazmaq olar. Buna görə də, bütün sadə ədədlərin qüvvətini araşdırmaqla rəngləmə ədədlərini tapmq olar. Əvvəl gördük ki, 2 sadə ədədi və qüvvətləri mümkün rəngləmə ədədləri deyil.
Kimsə rəngləmə modulunun mövcudluğunu yoxlamağa başlasa və əgər uğurlu olsa, daha sonra rəngləmə mövcud olmayana bunu sadə ədədin getdikcə daha yüksək qüvvətlərini yoxlamaqla təkrarlama etmək olar.
Cavab: Bəli.
İsbat:
Bir1, a2 rəngli bir ipin rəngləri olsun mod P və mod Q.
Sonra Çin Qalıq Teoremi hər iki şərti ödəyən bir tam ədəd A mod PQ-nin mövcudluğuna və unikallığına zəmanət verir
A ≡1 mod P
A ≡2 mod Q.
Rəng dəyərləri verən hər ip üçün bu təkrarlana bilər A,B,C,... mod PQ.
Hər bir keçiddə iki rəngləmə şəraitində
(A + B - 2C) mod P = a1 + b1 - 2c1 ≡ 0 mod P
(A + B - 2C) mod Q = a2 + b2 - 2c2 ≡ 0 mod Q
ödəyir. Sıfır mod P olan və sıfır mod Q olan (A + B - 2C) mod PQ-nün yeganə qiyməti A + B - 2C ≡ 0 mod PQ-dür. Bu, onu göstərir ki, rəng dəyərləri A,B,C,... rəngləmə mod PQ-nü təmin edir.
Bütün müsbət tam ədədlərin sadə vuruqlarına ayrılması ilə onları sadə ədədlərin qüvvətlərinin hasili kimi yazmaq olar. Buna görə də, bütün sadə ədədlərin qüvvətini araşdırmaqla rəngləmə ədədlərini tapmq olar. Əvvəl gördük ki, 2 sadə ədədi və qüvvətləri mümkün rəngləmə ədədləri deyil.
Kimsə rəngləmə modulunun mövcudluğunu yoxlamağa başlasa və əgər uğurlu olsa, daha sonra rəngləmə mövcud olmayana bunu sadə ədədin getdikcə daha yüksək qüvvətlərini yoxlamaqla təkrarlama etmək olar.
Sınaq və xəta ilə rəng tapmaq üçün hansı göstərişlər var?
Hansı hərflə qiymət vermək lazımdır?
- Növbəti dəfə hansı ipin rənglənəcəyini müəyyən etmək üçün Enter düyməsini sıxın ki, tənlikləri onların hərf sayına görə, yəni təcili olaraq sıralasınlar.
- Əgər tənliyin bir neçə hərfi varsa, onda ən çox digər tənliklərdə baş verən birini seçin ki, rəqəm təyin edildikdə daha çox tənliklər sadələşsin. Ekvivalent olaraq, siçanı tənliyin üzərində hərəkət etdir, dairəli keçidə baxın və bu keçiddə ən çox keçidə malik olan o yanmamış ipi basın.
- ≡ sağ tərəfindəki hərflər soldakı hərflərdən daha sürətli hesablanır. Soldakı hərfi hesablamaq üçün 2-yə bölmək lazımdır ki, bu da bərabər olmaq üçün sağa N əlavə etməyi tələb edə bilər. Bu çətin deyil, lakin yarışda vaxt dəyərlidir. Eyni səbəbdən, hərfin dəyərini təxmin edərkən ≡ hərfinin solunda bir hərf götürülə bilər.
- Vaxta qənaət etmək üçün 0..N−1 intervalında dəyərləri hesablamaq narahat etməsin. Dəyərlər mənfi və ya özbaşına böyük ola bilər. Əgər onlar düzdürlərsə, onda bənövşəyi tənlik yaşıl rəngə çevrilir və bütün bunlar vacibdir.
- Əgər tənliyin yalnız bir hərfi qalıbsa, onda arxa fon bənövşəyidir, sonra isə başqa çarə yoxdur, tənliyi yaşıl etmək üçün qiyməti hesablamaq lazımdır. Təlimatdakı nümunələrə bax.
- Yuxarıda göstərildiyi kimi bu bölmə > ''Əgər birinin bir rəngi varsa ...'' bölməsi, bütün hərflərin qiymətləri eyni sabit qiymətlə dəyişə bilər. Buna görə də təyin etmək istədiyi ilk məktubu ümumilik itkisi olmadan 0 qiymətini vermək olar. Bu hərf üçün başqa heç bir dəyər sınanmayacaq, çünki hər zaman bu dəyəri sıfıra qədər dəyişə bilər.
- Bir rəngə 2-ci hərf üçün yalnız iki halı nəzərdən keçirmək lazımdır: 1) Birinci hərflə eyni qiymətə malikdir, yəni 0, və 2) fərqli dəyərə malikdir. Bu halda yalnız 1-i nəzərə almaq lazımdır, çünki gördük ki, bütün rəqəmləri 2 ilə çoxaltmaq olar. (N-1) (burada N mövcud olan rənglərin əsas sayıdır) və hələ də ekvivalent həllə malikdirlər. Zəhmət olmasa, əsaslandırın bu bölmə > 'Əgər birinin bir rəngi varsa ...'. Məsələn, əgər N=5 və biri 2-ci təyin olunmuş hərf üçün fərqli bir dəyər yoxlayırsa, 3 kimi və həll əldə etsəydilər, onda bu dəyəri (və bütün digər dəyərləri) 2 dəfə çoxaltmaq 3-ü 3×2 = 6 ≡ 1 mod 5-ə çevirərdi. Buna görə də 2-ci hərfi yalnız 0 və 1 kimi sınaqdan keçirmək lazımdır.
- Testlər də zaman məsələsidir. Müsbət ədədlərdən daha sürətli hesablandıqda mənfi ədədləri daxil etməklə vaxta qənaət etmək olar. İnterface 0..N-1 diapazonunda ədədlərə ehtiyac yoxdur.
- Tənlik qırmızıya çevrildikdə ≡ şərti ödəmir və ən azı bir ədəd dəyişdirilməlidir. Sonra başqa ədədi yoxlayın. Ədədləri buraxmamaq üçün 0,1,...,N-1 ardıcıllığında ədədləri sınaya və rənglənmə tapıldıqda dayana bilərdi.
- Geri qaytar düyməsini basaraq geri dönərkən, əgər biri bənövşəyi tənliyi görürsə, onda düşünmədən yenidən geri düyməsini basmaq olar. Səbəb bənövşəyi tənliyin yalnız bir hərfinin olmasıdır və bu hərf üçün yalnız bir mümkün dəyər (mod N) var. Buna görə də bu vəziyyətdə bu hərf üçün başqa heç bir dəyər sınaqdan keçirilməlidir.
- Sistematik olaraq axtarış aparmaq və heç bir rəngləmə imkanını buraxmamaq üçün, hər dəyişəni əhəmiyyətsiz həll verən 0 qiymətini təyin etməklə başlaya bilər və sonra qeyri-trivial həll əldə etmək üçün geri dönməyə başlaya bilər.
- Bu oyunda istifadə edilən düyün diaqramlarında artıq minimum sayda keçid var. Ancaq diaqramlar minimal olmasaydı, əvvəlcə onları sadələşdirmək faydalı olardı. Sürətləndirmək üçün yuxarıda göstərilən üsullar olmadan NC rəngini sınamaq lazımdır, burada N rənglərin sayı, C isə kəsişmələrin sayı = iplərin sayıdır. Keçidlərin sayını cəmi 1 azaltmaq səyi N-nin VURUĞUNU azaldır.
Rənglənə bilməyəcək düyünlər varmı?
Bəli. Rəngi olmayan 12 keçiddən az olan düyünlər 10124, 10 153, 11n34, 11n42, 11n49, 11n116 və əlbəttə ki, düyünsüzdür. Bu rəqəm 10124 düyün diaqramı göstərir.
Səhifənin yuxarı hissəsindəki 'Tuzun-Sikora' yazılmış diaqram düyünsüz sonsuz çox diaqramlarından yalnız biridir və buna görə də rənglənməzdir.
Səhifənin yuxarı hissəsindəki 'Tuzun-Sikora' yazılmış diaqram düyünsüz sonsuz çox diaqramlarından yalnız biridir və buna görə də rənglənməzdir.
Daha çox rəng invariantları varmı və onları necə hesablamaq olar?
Bəli, bu əlavə invariantlar həllərin çoxluqlarıdır, mövcud rənglərin hər bir ədədi üçün bir çoxluqdur. Aşağıdakı şərhləri başa düşmək üçün xətti cəbrin bəzi bilikləri faydalı.
Əgər bir düyün diaqramının C keçidləri varsa, onda onun C ipləri də var və beləliklə, şərtlər sistemi C×C əmsal matrisə malikdir ki, burada hər sətir bir keçidi təmsil edir və ya iki -1 və bir 2 və ya +1 və -1 (Reidemeister I loop crossing) təşkil edir. Hər sütun bir ipə uyğun gəlir və 2'lərin sayı qədərdir, nə qədər ki, strand over-passes və ya iki -1's və ya bir -1 və bir +1.
Şərtlər eynicinsli xətti sistem təşkil edir (sağ tərəfdə yalnız 0 var) və sual qeyri-trivial xətti müstəqil həllərin (rənglərin) mövcud olduğu modullarla rəngləmə ədədlərini tapmaqdır.
Sətirli cəbrdə olduğu kimi, matris də sətirləri dəyişdirərək diaqonal formaya gətirilir və digər sətirlərə çoxlu sətir əlavə olunur. Bundan əlavə, bu addımlar sütunlarla da yerinə yetirilir. Burada icazə verilməyən məqam səttirləri və sütunları ədədlə çoxaltmaqdır, çünki bu matrisin determinantının sıfır olacağı və əlavə rəng əlavə edəcəyi rəng sayı modulu əlavə edəcəkdi. Bunun əvəzinə görülən iş, bir sütun/sətrin təkrarlanan 2 sıfır olmayan komponentini seçməkdir. A,B deyərkən, genişləndirilmiş Evklid alqoritmini istifadə edərək p,q, qaneedici pA + qB = ƏBOB(A,B) tapmaqdır. p,q – iki sətir/sütunun bölünənləridir. Sətir/sütunları dəyişdikdən sonra ƏBOB(A,B) diaqonal elementə çevrilir. Nəticədə Smit Normal Form adlanan diaqonal matris yaranır. Adətən yuxarı sol künc 1'dən sonra 1'dən başlayır. Diaqonaldakı növbəti ədədin hər bir vuruğudur. Sonuncu diaqonal element sıfırdır, çünki hər düyün diaqramı cəmi bir rəngdən istifadə edərək trivial rəngləməni imkan verir. Buna görə də hər hansı bir sütunu və hər hansı bir sətri buraxdıqdan sonra Smit Normal Formasını hesablamaq kifayətdir.
C×C əmsal matrisinin determinantının hesablanması sıfır verir, çünki sütunlara sıfıra əlavə olunur. Bir sətir və bir sütunu buraxdqıdan sonra determinantın hesablanması bir ədəd verir ki, bu da Smitin normal formasının diaqonaldakı ədədlərin hasilidir. Beləliklə, Smit Normal Forması təxminən eyni səy üçün daha çox məlumat verir.
Məsələn: 83 keçidli bu diaqram üçün əmsal matrisinin ölçüsü 83×83-dür.
Smit Normal Formu 79 dəfə 1 ilə yuxarı sol küncdən başlayan diaqonal var. Sonrakı 3, 3, 85837301265 (= 3 x 5 x 5722486751), 0. Bu, o deməkdir ki, üç müstəqil 3 rəngləmə və bir 85837301265-rəngləmə var ki, bu da onun 5-rəngli, 15-rəngli, 3x5722486751-rənglənməsi və 5x5722486751 rənglənməsini nəzərdə tutur.
Əgər diaqramın rənglənməsi yoxdursa, onda diaqonal ədədlərin hamısı sonuncu mövqedəki 0-dan başqa 1-dir.
Aşağıdakı diaqram 12a801 düyünlərinə aiddir.
Smith Normal Forması (SNF) diaqonalda doqquz 1-ə malikdir və ondan sonra 3,45,0-dır. Bu formada hər nömrə növbəti diaqonal ədədin vuruğudur. Rənglənmənin çoxluğu isə onun vuruq kimi meydana çıxdığı diaqonal elementlərin sayıdır. Buna görə də bu düyünün hər bir diaqramında iki müstəqil 3 rəng və tək 45 rəng var, bu da onun tək 5-, 9-, 15 rəngə sahib olduğunu göstərir.
Əgər bir düyün diaqramının C keçidləri varsa, onda onun C ipləri də var və beləliklə, şərtlər sistemi C×C əmsal matrisə malikdir ki, burada hər sətir bir keçidi təmsil edir və ya iki -1 və bir 2 və ya +1 və -1 (Reidemeister I loop crossing) təşkil edir. Hər sütun bir ipə uyğun gəlir və 2'lərin sayı qədərdir, nə qədər ki, strand over-passes və ya iki -1's və ya bir -1 və bir +1.
Şərtlər eynicinsli xətti sistem təşkil edir (sağ tərəfdə yalnız 0 var) və sual qeyri-trivial xətti müstəqil həllərin (rənglərin) mövcud olduğu modullarla rəngləmə ədədlərini tapmaqdır.
Sətirli cəbrdə olduğu kimi, matris də sətirləri dəyişdirərək diaqonal formaya gətirilir və digər sətirlərə çoxlu sətir əlavə olunur. Bundan əlavə, bu addımlar sütunlarla da yerinə yetirilir. Burada icazə verilməyən məqam səttirləri və sütunları ədədlə çoxaltmaqdır, çünki bu matrisin determinantının sıfır olacağı və əlavə rəng əlavə edəcəyi rəng sayı modulu əlavə edəcəkdi. Bunun əvəzinə görülən iş, bir sütun/sətrin təkrarlanan 2 sıfır olmayan komponentini seçməkdir. A,B deyərkən, genişləndirilmiş Evklid alqoritmini istifadə edərək p,q, qaneedici pA + qB = ƏBOB(A,B) tapmaqdır. p,q – iki sətir/sütunun bölünənləridir. Sətir/sütunları dəyişdikdən sonra ƏBOB(A,B) diaqonal elementə çevrilir. Nəticədə Smit Normal Form adlanan diaqonal matris yaranır. Adətən yuxarı sol künc 1'dən sonra 1'dən başlayır. Diaqonaldakı növbəti ədədin hər bir vuruğudur. Sonuncu diaqonal element sıfırdır, çünki hər düyün diaqramı cəmi bir rəngdən istifadə edərək trivial rəngləməni imkan verir. Buna görə də hər hansı bir sütunu və hər hansı bir sətri buraxdıqdan sonra Smit Normal Formasını hesablamaq kifayətdir.
C×C əmsal matrisinin determinantının hesablanması sıfır verir, çünki sütunlara sıfıra əlavə olunur. Bir sətir və bir sütunu buraxdqıdan sonra determinantın hesablanması bir ədəd verir ki, bu da Smitin normal formasının diaqonaldakı ədədlərin hasilidir. Beləliklə, Smit Normal Forması təxminən eyni səy üçün daha çox məlumat verir.
Məsələn: 83 keçidli bu diaqram üçün əmsal matrisinin ölçüsü 83×83-dür.
Smit Normal Formu 79 dəfə 1 ilə yuxarı sol küncdən başlayan diaqonal var. Sonrakı 3, 3, 85837301265 (= 3 x 5 x 5722486751), 0. Bu, o deməkdir ki, üç müstəqil 3 rəngləmə və bir 85837301265-rəngləmə var ki, bu da onun 5-rəngli, 15-rəngli, 3x5722486751-rənglənməsi və 5x5722486751 rənglənməsini nəzərdə tutur.
Əgər diaqramın rənglənməsi yoxdursa, onda diaqonal ədədlərin hamısı sonuncu mövqedəki 0-dan başqa 1-dir.
Aşağıdakı diaqram 12a801 düyünlərinə aiddir.
Smith Normal Forması (SNF) diaqonalda doqquz 1-ə malikdir və ondan sonra 3,45,0-dır. Bu formada hər nömrə növbəti diaqonal ədədin vuruğudur. Rənglənmənin çoxluğu isə onun vuruq kimi meydana çıxdığı diaqonal elementlərin sayıdır. Buna görə də bu düyünün hər bir diaqramında iki müstəqil 3 rəng və tək 45 rəng var, bu da onun tək 5-, 9-, 15 rəngə sahib olduğunu göstərir.
Düyün rəngləmələrinin statistikası
Əsas düyünlərin mümkün rəngləmələri haqqında ümumi məlumat varmı?
Mətn faylı
https://cariboutests.com/qi/knots/colour3-15-N.txt 0 və ya 1 olmayan Smit Normal Formasının bütün girişləri ≦ 15 keçid nömrəsi ilə hər düyün üçün siyahıları var. Bu ədədlər bir diaqramdan hesablansa da, onlar invariantdır və buna görə də həmin düyünün hər hansı bir diaqramından hesablanarkən eynidir. Əgər rəngli düyünlərin şəkillərini bəyənirsinizsə, onda "Ev" > "Posterlər" ana səhifəsinə basaraq poster kolleksiyamızdan poster yükləyə https://cariboutests.com/images/posters/knot_colouring_portrait.pdf.
N-rəngləmə invariant kimi nə dərəcədə güclüdür?
Aşağıdakı cədvəldə daha çox rəngləmə invariantlarından istifadənin düyünlərin invariant siniflərinin sayını necə artırdığını və bununla da hər sinif üçün orta düyünsayını necə azaltdığını göstərir. Sağ sütun göstərir ki, rəngləmə invariant siniflərin sayının (#cr - 3)-cü dərəcədən kökü sabit qalır. Burada #cr düyünlərin keçidlərinin sayıdır.
Cədvəl 1: Rəng invariantları ilə bağlı statistika
# cr: # keçidlər
# of kn: # düyünlər
# of cl1: # siniflər yalnız sadə rəngləmə ədədlərinin siyahısını nəzərdən keçirərkən
# of cl2: # sadə rəngləmə ədədlərinin yalnız çoxluqlar siyahısını nəzərdən keçirərkən siniflərin
# of cl3: Smith Normal Forma Girişlərinin siyahısını nəzərdən keçirərkən siniflərin sayı <> 1
abs: exp(ln(noofcl3[cr])/(cr-3))
= (cr-3)-cü dərəcədən (# of cl3)-ün kökü
Cədvəl 1: Rəng invariantları ilə bağlı statistika
# cr: # keçidlər
# of kn: # düyünlər
# of cl1: # siniflər yalnız sadə rəngləmə ədədlərinin siyahısını nəzərdən keçirərkən
# of cl2: # sadə rəngləmə ədədlərinin yalnız çoxluqlar siyahısını nəzərdən keçirərkən siniflərin
# of cl3: Smith Normal Forma Girişlərinin siyahısını nəzərdən keçirərkən siniflərin sayı <> 1
abs: exp(ln(noofcl3[cr])/(cr-3))
= (cr-3)-cü dərəcədən (# of cl3)-ün kökü
| # cr | # kn | # cl1 | kn/cl1 | # cl2 | kn/cl2 | # 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 |
C keçidləri olan düyünlər üçün ən böyük rəngləmə nömrəsi C-dən necə asılıdır?
Əgər biri keçid nömrəsi C (<16) ilə bütün düyünləri götürürsə və bu düyünlərdən ən yüksək rəngləmə sayı Nmax olan birini tapırsa, onda aşağıdakı cədvəldə göstərilir ki, Nmax C-ni 1-ə artırarkən, təqribən, 1.7-nin vuruğu qədər böyüyür.
Cədvəl 2: B(C) = Nmax1/(C−1) cədvəli
Cədvəl 2: B(C) = Nmax1/(C−1) cədvəli
| C | Nmax | düyün | 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 |
Rəngləri hesablamaq üçün kompüter proqramı varmı?
AsciiKnots əmsal matrisinin Smith Normal Formasını hesablamaqla verilmiş düyün diaqramı üçün bütün rəngləmə nömrələrini hesablamaq üçün kompüter proqramıdır. Düyün diaqramında çox sayda keçid yoxdursa, o, həmçinin verilmiş rəngləmə nömrəsi üçün optimallaşdırılmış sınaq və səhv axtarışı ilə bütün rəngləri və ya rəngləri daxil olmaqla bütün rəngləmə nömrələrini hesablayır.Rəngləmələrdən savayı proqram daha çox hesablama apara bilər.
https://cariboutests.com/games/knots/AsciiKnots.tar.gz yüklənə bilər. AsciiKnots linux altında işləyir. Strict windows istifadəçiləri Windows 10 altında Ubuntu linux-nu proqram kimi pulsuz quraşdıra bilərlər. Köhnə yüklənmiş versiyaları aradan qaldırmaq, ən son versiyanı yükləmək, onu açmaq və başlamaq üçün Linux əmrləri
rm AsciiKnots.tar.gz
wget https://cariboutests.com/games/knots/AsciiKnots.tar.gz
tar xfz AsciiKnots.tar.gz
./AsciiKnots
"Tools" > "Colour Knot" seçdikdən sonra https://cariboutests.com/games/knots/knoteditor/-də məhdud rəngləmə funksiyası da mövcuddur
Referatlar
[1] R. H. Fox, Metacyclic invariants of knots and links, Canadian Journal of Mathematics 22 (1970) 193−201.
[2] C. H. Przytycki, 3-rəngləmə və düyünlərin digər elementar invariantları. Bakı: "Yazıçı", 2008, 275 səh.
[3] D. Rolfsen, Table of Knots and Links. Knots və Linklərdə C əlavəsi. Bakı, "Azərbaycan" nəşriyyatı, 280-287, 1976.
[4] J. C. Cha və C. Livingston, KnotInfo: Table of Knot Invariants, http://www. indiana.edu/~knotinfo
[5] "15-ə qədər Kəsişən Düyünlərin Rəng Təsnifatı", https:// cariboutests.com/qi/knots/colour3-15.txt
[6] T.Volff, "A Knot Workbench", https://cariboutests.com/games/knots/AsciiKnots.tar.gz
[2] C. H. Przytycki, 3-rəngləmə və düyünlərin digər elementar invariantları. Bakı: "Yazıçı", 2008, 275 səh.
[3] D. Rolfsen, Table of Knots and Links. Knots və Linklərdə C əlavəsi. Bakı, "Azərbaycan" nəşriyyatı, 280-287, 1976.
[4] J. C. Cha və C. Livingston, KnotInfo: Table of Knot Invariants, http://www. indiana.edu/~knotinfo
[5] "15-ə qədər Kəsişən Düyünlərin Rəng Təsnifatı", https:// cariboutests.com/qi/knots/colour3-15.txt
[6] T.Volff, "A Knot Workbench", https://cariboutests.com/games/knots/AsciiKnots.tar.gz
Yeniliklər üçün izləyin və ya abunə olun: