300000
29390
14214
English | Français | فارسی | 中文 | Українська | Azerbaijani | ខ្មែរ | Tiếng Việt | Bahasa Melayu | Deutsch | O'zbek | Русский
14214
Màu nút thắt
Nếu bạn chỉ quan tâm đến cách giải bài toán này và không quan tâm đến lý thuyết đằng sau nó, thì hãy đi tới phần 'Các gợi ý để tìm màu bằng cách thử các biện pháp khác nhau cho đến khi tìm được biện pháp đúng là gì?'
Về các lượng bất biến
Hai trong ba biểu đồ sau
có thể bị làm biến dạng vào nhau mà không cần cắt dây nút.
Một ví dụ của một bất biến là số lượng điểm bắt chéo tối thiểu mà bất kỳ biểu đồ nào trong vô số đồ thị có thể có. Bất biến này khó tìm bởi vì một người không thể kiểm tra hết vô số biểu đồ.
Nhưng cái gì có thể là một bất biến mà có thể tính được cho một biểu đồ đã cho? Rất khó để tưởng tượng tính chất nào không bị thay đổi trong quá trình biến dạng do một người có thể biến dạng một biểu đồ theo bất kỳ cách nào họ mong muốn.
Khả năng tô ba màu là một bất biến
N-khả năng tô màu
nút không thắt
Tuzun-Sikora
8_19
có thể bị làm biến dạng vào nhau mà không cần cắt dây nút.
Bạn nghĩ chúng là những cái nào?
Bạn có thể học ở bên dưới về cách sử dụng khả năng nhuộm màu để phân biệt liệu hai biểu đồ sau có thuộc các nút thắt khác nhau hay không. Bằng cách điều tra tri-colourability (là khả năng của một nút được tô màu bằng ba màu tuân theo các quy tắc nhất định), ta có thể thấy biểu đồ nào chắc chắn không biến dạng vào nhau.
Nói theo cách khác, trình tự sau đây thể hiện cách đơn giản hoá biểu đồ Tazun-Sikora thành một hình tròn.
Minh chứng rằng sơ đồ Tuzun-Sikora là nút không thắt.
Biểu đồ nút không thắt và Tuzun-Sikora cùng với vô số sự biến dạng khác thuộc về cùng một nút toán học, hay trong trường hợp này là một nút không được thắt. Làm sao để một người có thể xác định liệu hai biểu đồ không bao giờ có thể biến dạng vào nhau, bất kể chúng có phát triển lớn như nào ở giữa? Một tính chất không đổi khi biểu đồ bị biến dạng được gọi là 'bất biến' (không thay đổi).Nói theo cách khác, trình tự sau đây thể hiện cách đơn giản hoá biểu đồ Tazun-Sikora thành một hình tròn.
Minh chứng rằng sơ đồ Tuzun-Sikora là nút không thắt.
Phép chiếu ban đầu
Một nước đi Reidemeister 3
Sau khi di chuyển và kéo dài
Sự giao nhau làm giảm nước đi ngang qua.
Sau khi di chuyển và kéo dài
Sự giao nhau làm giảm nước đi ngang qua.
Sau khi di chuyển và kéo dài
Sự giao nhau làm giảm nước đi ngang qua.
Sau khi di chuyển và kéo dài
Sự giao nhau làm giảm nước đi ngang qua.
Sau khi di chuyển và kéo dài
Sự giao nhau làm giảm nước đi ngang qua.
Sau nước đi
Sự giao nhau làm giảm nước đi ngang qua.
Sau nước đi
Một nước đi Reidemeister 2
Sau nước đi
Một nước đi Reidemeister 1
Sau nước đi
Một nước đi Reidemeister 1
Sau nước đi
Một nước đi Reidemeister 1
Sau nước đi
Một nước đi Reidemeister 1
Sau nước đi
Một ví dụ của một bất biến là số lượng điểm bắt chéo tối thiểu mà bất kỳ biểu đồ nào trong vô số đồ thị có thể có. Bất biến này khó tìm bởi vì một người không thể kiểm tra hết vô số biểu đồ.
Nhưng cái gì có thể là một bất biến mà có thể tính được cho một biểu đồ đã cho? Rất khó để tưởng tượng tính chất nào không bị thay đổi trong quá trình biến dạng do một người có thể biến dạng một biểu đồ theo bất kỳ cách nào họ mong muốn.
Khả năng tô ba màu là một bất biến
Để giải thích, ta dùng các sợi là các bộ phận của một đường nút thắt có thể được vẽ mà không nhấc bút lên. Ở mỗi giao điểm của 3 sợi, một giao điểm là điểm vượt và một điểm ở mỗi bên. Một biểu đồ nút thắt là một biểu đồ tô được ba màu nếu mỗi sợi có thể được chỉ định một trong 3 màu, từ đó ở mỗi điểm giao ta có 1 hoặc 3, không phải 2 màu. Luôn luôn có thể tô tất cả các sợi một màu và điều này không được tính. Cần có ít nhất 2 màu được sử dụng.
Biểu đồ nào trong 3 biểu đồ là biểu đồ có thể tô ba màu?
Nút không được thắt chỉ có một sợi và do đó không thể tô được ba màu. Nút thứ 2 có thể biến dạng thành nút không được thắt và do đó cũng không thể tô màu được. Ta sẽ chứng minh điều này sau. Nút sắt còn lại có thể tô được ba màu và do đó không bao giờ có thể bị biến dạng thành nút không được thắt như đã được cho thấy phía trên.
Khả năng tô ba màu là một bất biến yếu bởi vì nó chứa lượng thông tin có thể có ít nhất, chỉ là có/không. Bất biến này chỉ có thể đặt tất cả các nút thắt vào hai nhóm, các nút có thể tô được ba màu và các nút không thể.
N-khả năng tô màu
Một bất biến mạnh hơn là N-khả năng tô màu, trong đó tồn tại N màu và mỗi màu được đại diện một số 0, 1, 2, 3,...,N-1. Điều kiện cần được thoả mãn ở mỗi điểm giao nhau là tổng các màu của 2 sợi dưới trừ 2 lần màu của sợi trên là bội số của N. Nói theo cách khác, nếu các màu là a,b,c thì phải có một bội số k sao cho a+b-2c = kN. Công thức toán học tương đương nhưng phổ biến hơn là a + b ≡ 2c mod N. Điều này có nghĩa là cả hai vế của dấu ≡ đều để lại cùng một số dư trong phép chia qua N. Làm việc với modulo (mod) một số số được gọi là Số học Mô đun và có nhiều quy tắc thú vị và hữu dụng.
Nhiều câu hỏi được đưa ra.
Nhiều câu hỏi được đưa ra.
Giới thiệu về số học mô-đun
Ta có thể chứng minh tất cả các phát biểu của số học mô-đun bằng cách đưa ra một cấp số nhân k và lập lại công thức = phương trình dưới dạng một phương trình bình thường. Để rút gọn ký hiệu ta sử dụng
'integer' đại diện cho 'số nguyên',
'pq' đại diện cho 'p lầm q',
'∃' đại diện cho 'Có tồn tại',
':' đại diện cho 'tính chất', và
'A → B' đại diện cho 'từ A theo B'.
Chứng minh: nếu a ≡ b mod N và c ≡ d mod N thì (a+c) ≡ (b+d) mod N
Phương trình mô-đun a ≡ b mod N diễn đạt rằng a và b chỉ khác nhau theo bội số của p.
tức là phải tồn tại một số nhân m với tính chất là a = b + mp. Theo ký hiệu ngắn gọn điều này là
(a ≡ b mod N) → (∃ integer m: a = b + mp)
(c ≡ d mod N) → (∃ integer n: c = d + np)
Bằng cách cộng cả hai phương trình, ta được a + c = b + mp + d + np = b + d + (m+n)p
→ a + c ≡ (b + d) mod N
tức là phải tồn tại một số nhân m với tính chất là a = b + mp. Theo ký hiệu ngắn gọn điều này là
(a ≡ b mod N) → (∃ integer m: a = b + mp)
(c ≡ d mod N) → (∃ integer n: c = d + np)
Bằng cách cộng cả hai phương trình, ta được a + c = b + mp + d + np = b + d + (m+n)p
→ a + c ≡ (b + d) mod N
Chứng minh: nếu if a ≡ b mod N thì với bất kỳ số nguyên m nào ta có ma ≡ mb mod N
(a ≡ b mod N) → (∃ integer k: a = b + kN)
Sau khi thực hiện phép nhân với m ta được
ma = mb + mkN
→ ma ≡ mb mod N
Sau khi thực hiện phép nhân với m ta được
ma = mb + mkN
→ ma ≡ mb mod N
Chứng minh: nếu a ≡ b mod (PQ) thì a ≡ b mod P.
a ≡ b mod (PQ)
→ ∃ integer k: a = b + k(PQ)
→ a = b + (kQ)P
→ a ≡ b mod P
Vậy hướng ngược lại thì sao?
Tại sao có thể điều ngược lại là không đúng?
→ ∃ integer k: a = b + k(PQ)
→ a = b + (kQ)P
→ a ≡ b mod P
Vậy hướng ngược lại thì sao?
Đây là một phản ví dụ:
6 ≡ 1 mod 5 nhưng
6 ≢ 1 mod 15 vì 6 và 1 không khác nhau theo bội số của 15.
6 ≡ 1 mod 5 nhưng
6 ≢ 1 mod 15 vì 6 và 1 không khác nhau theo bội số của 15.
Tại sao có thể điều ngược lại là không đúng?
Trong một phương trình mod N cả hai vế của ≡ có thể có N giá trị khác nhau. Trong một phương trình mod (NM) cả hai vế của ≡ có thể có NM giá trị khác nhau. Do đó quan hệ của mod (NM) mang nhiều thông tin hơn một quan hệ mod N. Thật dễ dàng để loại bỏ bất kỳ thông tin nào bằng cách chuyển từ mod (NM) sang mod N nhưng ngược lại, tạo ra thông tin từ hư vô là điều không thể. Nói một cách đại khái, theo nghĩa này một đẳng thức thông thường sử dụng = là tương đương với ≡ mod ∞(infinity).
Một nhận xét phụ, điều này mở ra khả năng rằng trên thực tế khi cách giải liên quan tới các số nguyên và khi ta đang tìm một giải pháp dưới dạng một phương trình sử dụng dấu '=' và trong đó ta biết rằng có một giới hạn trần cho giá trị tuyệt đối của các số trong giải pháp và sau đó thì một chiến lược có thể là bắt đầu với việc tìm cách giải mod N với một số ít số nguyên tố N và sau đó tính đồng nhất thức mod N^2, sau đó mod N^4 và cứ thế cho đến khi luỹ thừa của N lớn hơn giới hạn trần mà ta biết với lời giải và sau đó ta có thể bỏ mod và có giải pháp chính xác bằng cách sử dụng =.
Cách thức gọi là Hensel lifting có thể được dùng để nhân tử hoá các đa thức đơn biến, đầu tiên, với một số ít số nguyên tố và sau đó chính xác với các số nguyên.
Chứng minh: a + b ≡ ((a mod N) + (b mod N)) mod N
a và a mod N khác nhau theo bội số của N: a = (a mod N) + pN
b và b mod N khác nhau theo bội số của 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 và b mod N khác nhau theo bội số của 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
Chứng minh: ab ≡ ((a mod N)(b mod N)) mod N
a và a mod N khác nhau theo bội số của N: a = (a mod N) + pN
b và b mod N khác nhau theo bội số của 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 và b mod N khác nhau theo bội số của 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
Chứng minh: nếu P (x,y,...) là một đa thức trong biến số x, y,... thì P(x,y,...) ≡ P((x mod N),(y mod N),...) mod N
Mỗi đa thức có thể được viết dưới dạng tổng của các tích, vì vậy việc áp dụng lặp lại hai quy tắc trên sẽ chứng minh cho mệnh đề.
Chứng minh: Trong số học mô-đun modulo một số nguyên tố, các phép chia cho số nguyên sẽ cho lại các số nguyên.
Chúng ta bắt đầu bằng việc hiển thị rằng với một số nguyên tố p và bất kỳ số nguyên a ≢ 0 mod N nào, nghịch đảo 1/a mod N cũng là một số nguyên. Ta yêu cầu a ≢ 0 mod N vì cũng ở trong một số học mô-đun, phép chia cho 0 là không thể thực hiện được.
Giả sử u là u ≡ 1/a mod N. Để u là nghịch đảo của mod N, điều đó có nghĩa là
ua ≡ 1 mod N
→ ∃ integer k: ua = 1 + kp
Điều này có dạng của một bổ đề Bézout: ua + vp = GCD(a,p) trong đó GCD (a,p) là Ước chung lớn nhất của a,p và v=-k. Vì p là một số nguyên tố và a không phải là bội số của p do đó GCD(a,p)=1.
Các bội số u, v trong Bổ đề Bézout có thể được tính thông qua thuật toán Euclid mở rộng và cả hai, u,v, đều là số nguyên.
Nếu u=1/a là một số nguyên mod N thì b/a = bu cũng là một số nguyên mod N sẽ được hiển thị
Ví dụ: 1/3 ≡ 5 mod 7 vì 1 = 3(1/3) ≡ 3(5) = 15 = 2(7) + 1 ≡ 1 mod 7.
Khi nào ma ≡ mb mod N tương đương với a ≡ b mod N?
Ta đã thấy rằng từ a ≡ b mod N theo sau ma ≡ mb mod N. Ta có sự tương đương nếu ta có thể làm phép nhân với một số nguyên k ≡ 1/m mod N. Điều này có nghĩa là sau khi nhân với m, có tồn tại một số nguyên I sao cho mk = 1 + lN mà bổ đề Bézout với 1 = GCD(m,N) (Ước chung lớn hơn của m,N), do đó m và N phải cùng nguyên tố để giá trị tương đương của ma ≡ mb mod N và a ≡ b mod N.
Định lý số dư Trung Hoa
Chúng ta đã nói ở phần trước về thông tin trong một phương trình mô đun mod N phụ thuộc vào N. Có khả năng ta có thể kết hợp hai phương trình mô đun với các số mô đun nhỏ hơn thành một phương trình với số lớn hơn hay không?
Đây là nội dung của Định lý số dư Trung Hoa
Nếu với hai phương trình
x ≡ a1 mod N1
x ≡ a2 mod N2
các số chia N1,N2 có cùng nguyên tố, do đó tồn tại chính xác một giá trị của x lên đến bội số của p1p2 thoả mãn cả hai phương trình mô đun.
Một cách để tìm được lời giải là sử dụng thuật toán Euclid mở rộng để giải bổ đề Bézout m1N1 + m2N2 = 1 bằng cách tính m1,m2 và sau đó dùng công thức
x = a1m2N2 + a2m1M1
= a1(1 - m1N1) + a2m1N1
= a1 + (a2 - a1)m1N1
cho thấy x ≡ a1 mod N1 và tương đương x = a2 + (a1 - a2)m2N2 which shows x ≡ a2 mod N2
Nếu ta có nhiều hơn hai phương trình mô đun thì có thể thay thế lần lượt hai trong số đó bằng một phương trình cho đến khi một phương trình có lời giải dưới dạng một phương trình mô đun. Ở mỗi phương trình thay thế, ước số mới tăng lên bằng cách trở thành tích của hai ước số của các phương trình được hợp nhất.
Đây là nội dung của Định lý số dư Trung Hoa
Nếu với hai phương trình
x ≡ a1 mod N1
x ≡ a2 mod N2
các số chia N1,N2 có cùng nguyên tố, do đó tồn tại chính xác một giá trị của x lên đến bội số của p1p2 thoả mãn cả hai phương trình mô đun.
Một cách để tìm được lời giải là sử dụng thuật toán Euclid mở rộng để giải bổ đề Bézout m1N1 + m2N2 = 1 bằng cách tính m1,m2 và sau đó dùng công thức
x = a1m2N2 + a2m1M1
= a1(1 - m1N1) + a2m1N1
= a1 + (a2 - a1)m1N1
cho thấy x ≡ a1 mod N1 và tương đương x = a2 + (a1 - a2)m2N2 which shows x ≡ a2 mod N2
Nếu ta có nhiều hơn hai phương trình mô đun thì có thể thay thế lần lượt hai trong số đó bằng một phương trình cho đến khi một phương trình có lời giải dưới dạng một phương trình mô đun. Ở mỗi phương trình thay thế, ước số mới tăng lên bằng cách trở thành tích của hai ước số của các phương trình được hợp nhất.
Làm sao để chứng minh được N-khả năng tô màu là một bất biến?
Như được giải thích phía trên ở phần Cởi nút tháo một số điều cần suy nghĩ > Giới thiệu với Định nghĩa > Các nước đi Reidemeister, 3 nước đi Reidemeister là đủ để thực hiện bất kỳ sự biến dạng nào của một biểu đồ nút thắt. Do đó, để có thể là một bất biến, ta chỉ cần chứng minh rằng tính chất không đổi theo 3 nước đi này.
Làm sao để ta có thể chứng minh rằng một nước đi Reidemeister I không làm thay đổi khả năng tô màu?
Nếu màu của các sợi A và B như đã được chỉ ra, khi đó điều kiện tô màu yêu cầu ở hình bên trái A + B ≡ 2B mod N và ở hình bên phải B + A ≡ 2A mod N. Ở cả hai trường hợp B = A là một giải pháp:
Điều này có nghĩa rằng, thực hiện một nước đi Reidemeister I không làm thay đổi khả năng tô màu.
Làm sao để ta có thể chứng minh rằng một nước đi Reidemeister II không làm thay đổi khả năng tô màu?
Nếu màu của các sợi là A, B và C như đã chỉ ra thì C được xác định duy nhất từ điều kiện B + C ≡ 2A mod N ở hình bên trái nên C ≡ (2A - B mod N) và ở hình bên phải A + C ≡ 2B mod N nên C ≡ (2B - A mod N). Điều này xác định màu của sợi mới khi thực hiện một nước đi Reidemeister II. Khả năng tô màu không bị ảnh hưởng.
Làm sao để ta có thể chứng minh rằng một nước đi Reidemeister III không làm thay đổi khả năng tô màu?
Nếu màu sắc của các sợi là A,B,C,D,E,F và G như đã được chỉ ra, thì ba điều kiện bên trái là
A + D ≡ 2C mod N
E + F ≡ 2D mod N
F + B ≡ 2C mod N .
Bằng cách loại bỏ sợi bên trong F, điều kiện trên các sợi bên ngoài là
2D - E ≡ 2C - B mod N mà bằng cách sử dụng A + D ≡ 2C mod N được rút gọn thành
2D - E ≡ A + D - B mod N và do đó A - B - D + E ≡ 0 mod N.
Ba điều kiện bên phải là
E + G ≡ 2C mod N
G + B ≡ 2A mod N
A + D ≡ 2C mod N
Bằng cách loại bỏ đoạn cáp bên trong G, điều kiện trên các đoạn cáp bên ngoài là
2C - E ≡ 2A - B mod N mà bằng cách sử dụng 2C ≡ A + D mod N được rút gọn thành
A + D - E ≡ 2A - B mod N và do đó 0 ≡ A - B - D + E mod N.
F và G được tính từ bất kỳ quan hệ nào mà chúng xuất hiện trong đó.
Ta kết luận rằng với cả hai biểu đồ, điều kiện về màu sắc của các sợi bên ngoài là giống nhau: A + D ≡ 2C mod N và A - B - D + E ≡ 0 mod N.
Do đó, một là cả hai biểu đồ đều có hoặc không biểu đồ nào có tô màu và do đó khả năng tô màu là bất biến dưới các nước đi Reidemeister III.
Làm sao để ta có thể chứng minh rằng một nước đi Reidemeister I không làm thay đổi khả năng tô màu?
Nếu màu của các sợi A và B như đã được chỉ ra, khi đó điều kiện tô màu yêu cầu ở hình bên trái A + B ≡ 2B mod N và ở hình bên phải B + A ≡ 2A mod N. Ở cả hai trường hợp B = A là một giải pháp:
Điều này có nghĩa rằng, thực hiện một nước đi Reidemeister I không làm thay đổi khả năng tô màu.
Làm sao để ta có thể chứng minh rằng một nước đi Reidemeister II không làm thay đổi khả năng tô màu?
Nếu màu của các sợi là A, B và C như đã chỉ ra thì C được xác định duy nhất từ điều kiện B + C ≡ 2A mod N ở hình bên trái nên C ≡ (2A - B mod N) và ở hình bên phải A + C ≡ 2B mod N nên C ≡ (2B - A mod N). Điều này xác định màu của sợi mới khi thực hiện một nước đi Reidemeister II. Khả năng tô màu không bị ảnh hưởng.
Làm sao để ta có thể chứng minh rằng một nước đi Reidemeister III không làm thay đổi khả năng tô màu?
Nếu màu sắc của các sợi là A,B,C,D,E,F và G như đã được chỉ ra, thì ba điều kiện bên trái là
A + D ≡ 2C mod N
E + F ≡ 2D mod N
F + B ≡ 2C mod N .
Bằng cách loại bỏ sợi bên trong F, điều kiện trên các sợi bên ngoài là
2D - E ≡ 2C - B mod N mà bằng cách sử dụng A + D ≡ 2C mod N được rút gọn thành
2D - E ≡ A + D - B mod N và do đó A - B - D + E ≡ 0 mod N.
Ba điều kiện bên phải là
E + G ≡ 2C mod N
G + B ≡ 2A mod N
A + D ≡ 2C mod N
Bằng cách loại bỏ đoạn cáp bên trong G, điều kiện trên các đoạn cáp bên ngoài là
2C - E ≡ 2A - B mod N mà bằng cách sử dụng 2C ≡ A + D mod N được rút gọn thành
A + D - E ≡ 2A - B mod N và do đó 0 ≡ A - B - D + E mod N.
F và G được tính từ bất kỳ quan hệ nào mà chúng xuất hiện trong đó.
Ta kết luận rằng với cả hai biểu đồ, điều kiện về màu sắc của các sợi bên ngoài là giống nhau: A + D ≡ 2C mod N và A - B - D + E ≡ 0 mod N.
Do đó, một là cả hai biểu đồ đều có hoặc không biểu đồ nào có tô màu và do đó khả năng tô màu là bất biến dưới các nước đi Reidemeister III.
Tính tầm thường, tính tương đương và tính độc lập của phép tô màu
Nếu một biểu đồ được tô một màu, những phép tô màu nào khác có thể được lấy từ nó với bất kỳ biểu đồ nút thắt nào?
Mỗi điều kiện tô màu có dạng A + B ≡ 2C mod N. Ta hãy viết nó là A - C ≡ C - B mod N.
1) Khi cộng thêm cùng một hằng số, giả sử là S, cho mỗi màu thì sự khác biệt không thay đổi:
(A+S) - (C+S) = A - C + S - S = A - C và
(C+S) - (B+S) = C - B + S - S = C - B và
do đó các điều kiện được thoả mãn.
2) Ở phần trước, ta đã thấy quy tắc của số học mô đun là ta có thể nhân cả hai vế của ≡ với một số cùng nguyên tố với N và thu một nghiệm tương đương của hệ phương trình và do đó, một phép tô màu tương đương.
1) Khi cộng thêm cùng một hằng số, giả sử là S, cho mỗi màu thì sự khác biệt không thay đổi:
(A+S) - (C+S) = A - C + S - S = A - C và
(C+S) - (B+S) = C - B + S - S = C - B và
do đó các điều kiện được thoả mãn.
2) Ở phần trước, ta đã thấy quy tắc của số học mô đun là ta có thể nhân cả hai vế của ≡ với một số cùng nguyên tố với N và thu một nghiệm tương đương của hệ phương trình và do đó, một phép tô màu tương đương.
Khả năng tô màu mod 2 có quan trọng hay không?
Không, với N=2 phép tô màu là không quan trọng.
Ta hãy bắt đầu với một sợi có màu A tiếp tục như sợi B sau khi đi qua bên dưới cầu vượt đầu tiên có màu C. Khi đó A, B, C có liên quan qua A + B ≡ 2C mod 2 và sau khi cộng B vào cả hai vế A ≡ B mod 2 vì 2B ≡ 2C ≡ 0 mod 2. Tiếp tục lập luận đó ở tất cả các điểm giao nhau, tất cả các sợi đều có màu chẵn (0) hoặc một màu lẻ (1). Điều này mang lại một màu tầm thường.
Ta hãy bắt đầu với một sợi có màu A tiếp tục như sợi B sau khi đi qua bên dưới cầu vượt đầu tiên có màu C. Khi đó A, B, C có liên quan qua A + B ≡ 2C mod 2 và sau khi cộng B vào cả hai vế A ≡ B mod 2 vì 2B ≡ 2C ≡ 0 mod 2. Tiếp tục lập luận đó ở tất cả các điểm giao nhau, tất cả các sợi đều có màu chẵn (0) hoặc một màu lẻ (1). Điều này mang lại một màu tầm thường.
Vậy khả năng tô màu mod (2N), tức là modulo là một số chẵn, thì sao?
Ta đã thấy ở phía trên rằng tất cả các màu đều là chẵn hoặc lẻ. Nếu chúng đều là chẵn thì ta có thể chia tất cả với 2 và có một phép tô màu mod N, mà không làm mất thông tin. Nếu chúng đều là lẻ thì ta cộng thêm 1 vào tất cả các màu và nhận được một phép tô màu tương đương, mà bây giờ tất cả các màu đều là chẵn nên ta có thể giảm hệ số 2 và có một phép tô màu mod N tương đương.
Kết quả là, mỗi phép tô màu mod (2N) đều tương đương với một phép tô màu mod N.
Kết quả là, mỗi phép tô màu mod (2N) đều tương đương với một phép tô màu mod N.
Với N nào thì N-khả năng tô màu là hữu dụng và không phải không quan trọng?
Với N>1 khả năng tô màu lẻ, mod N là có nghĩa.
Có đủ để biết tất cả các phép tô màu mod P và mod Q, trong đó P và Q là đồng nguyên tố để biết tất cả các phép tô màu mod (PQ) hay không?
Nếu N là một hợp số, tức là một tích với cả hai thừa số đều không phải là 1, sau đó ta có thể viết nó là N=PQ với P và Q là đồng nguyên tố. Có một giải pháp cho điều kiện phép nguyên tố mod N cho ta một phép tô màu mod P bằng cách tính tất cả giá trị màu mod P và cho ta một phép tô màu mod Q bằng cách tính tất cả giá trị màu mod Q. Vậy thì các hướng đi khác thì sao? Nếu một hệ thống các điều kiện phép tô màu cho một biểu đồ hình nút có một lời giải mod P và một lời giải mod Q khác, trong đó P và Q là đồng nguyên tố, hệ thống các điều kiện này có lời giải mod PQ không?
Đáp án: Có
Minh chứng:
Để a1, a2 là các màu của một sợi trong phép tô màu mod P và mod Q.
Khi đó, Định lý số dư Trung Hoa đảm bảo sự tồn tại và sự độc nhất của một số nguyên A mod PQ thoả mãn cả hai điều kiện
A ≡ a1 mod P
A ≡ a2 mod Q.
Điều này có thể được lặp lại với mỗi sợi cho các giá trị về màu sắc A, B, C,...mod PQ.
Ở mỗi điểm giao nhau hai điều kiện tô màu
(A + B - 2C) mod P = a1 + b1 - 2c1 ≡ 0 mod P
(A + B - 2C) mod Q = a2 + b2 - 2c2 ≡ 0 mod Q
đều được thoả mãn. Chỉ có giá trị của (A + B - 2C) mod PQ bằng không mod P và bằng không mod Q là A + B - 2C ≡ 0 mod PQ. Điều này cho thấy giá trị màu sắc A, B, C,...cung cấp một phép tô màu mod PQ.
Bởi vì tất cả các số nguyên dương đề có sự tìm thừa số nguyên tố, chúng có thể được viết dưới dạng tích luỹ thừa của các số nguyên tố. Do đó, ta có thể tìm tất cả các số tô màu bằng cách điều tra tất cả các luỹ thừa của tất cả các số nguyên tố lẻ như các số được tô màu. Ta đã thấy được ở phần trước rằng số nguyên tố 2 và luỹ thừa của 2 không thể là các số tô màu.
Ta có thể bắt đầu kiểm tra sự tồn tại của phép tô màu modulo một số số nguyên tố và nếu thành công thì lặp lại việc kiểm tra với luỹ thừa cao hơn của số nguyên tố đó cho đến khi không còn tồn tại phép tô màu nữa.
Đáp án: Có
Minh chứng:
Để a1, a2 là các màu của một sợi trong phép tô màu mod P và mod Q.
Khi đó, Định lý số dư Trung Hoa đảm bảo sự tồn tại và sự độc nhất của một số nguyên A mod PQ thoả mãn cả hai điều kiện
A ≡ a1 mod P
A ≡ a2 mod Q.
Điều này có thể được lặp lại với mỗi sợi cho các giá trị về màu sắc A, B, C,...mod PQ.
Ở mỗi điểm giao nhau hai điều kiện tô màu
(A + B - 2C) mod P = a1 + b1 - 2c1 ≡ 0 mod P
(A + B - 2C) mod Q = a2 + b2 - 2c2 ≡ 0 mod Q
đều được thoả mãn. Chỉ có giá trị của (A + B - 2C) mod PQ bằng không mod P và bằng không mod Q là A + B - 2C ≡ 0 mod PQ. Điều này cho thấy giá trị màu sắc A, B, C,...cung cấp một phép tô màu mod PQ.
Bởi vì tất cả các số nguyên dương đề có sự tìm thừa số nguyên tố, chúng có thể được viết dưới dạng tích luỹ thừa của các số nguyên tố. Do đó, ta có thể tìm tất cả các số tô màu bằng cách điều tra tất cả các luỹ thừa của tất cả các số nguyên tố lẻ như các số được tô màu. Ta đã thấy được ở phần trước rằng số nguyên tố 2 và luỹ thừa của 2 không thể là các số tô màu.
Ta có thể bắt đầu kiểm tra sự tồn tại của phép tô màu modulo một số số nguyên tố và nếu thành công thì lặp lại việc kiểm tra với luỹ thừa cao hơn của số nguyên tố đó cho đến khi không còn tồn tại phép tô màu nữa.
Các gợi ý để tìm kiếm một phép tô màu bằng cách thử nhiều biện pháp khác nhau cho đến khi tìm được biện pháp đúng là gì?
Chữ cái nào nên được cho một giá trị?
- Để quyết định xem sẽ tô màu sợi nào tiếp theo, nhấn Enter để sắp xếp các phương trình theo số lượng chữ cái của chúng, tức là theo mức độ khẩn cấp.
- Nếu một phương trình có một vài chữ cái thì hãy chọn một chữ xuất hiện trong phần lớn các phương trình khác để nhiều phương trình được rút gọn hơn khi một số được gán giá trị. Tương tự, di chuột qua phương trình, xem điểm giao nhau đã được khoanh tròn và ở điểm giao nhau này, nhấn chuột vào sợi chưa được tô màu mà có nhiều đường đi vượt qua nhất.
- Các chữ cái ở vế bên phải của ≡ dễ tính hơn các chữ ở vế bên trái. Để tính toán một chữ cái phía bên trái ta cần chia với 2, điều này có thể yêu cầu cộng N vào vế bên phải để nó trở thành số chẵn. Điều này không khó nhưng thời gian thi rất quý báo. Vì cùng lý do đó, khi đoán giá trị của một chữ cái ta có thể lấy một chữ cái ở vế trái của một dấu ≡.
- Để tiết kiệm thời gian, đừng lo tính toán các giá trị trong khoảng 0..N−1. Các giá trị có thể âm hoặc lớn tuỳ ý. Nếu chúng là đúng thì một phương trình màu tím trở thành màu xanh và đó mới là vấn đề quan trọng.
- Nếu một phương trình chỉ còn lại một chữ cái thì nền màu tím và khi đó không có lựa chọn nào khác, giá trị cần được tính để phương trình có màu xanh. Nhìn các ví dụ ở phần hướng dẫn.
- Như đã được hiển thị trong phần này > Phần 'Nếu có một tô màu ...', Các giá trị của tất cả các chữ cái có thể được dịch chuyển theo cùng một giá trị không đổi. Do đó chữ cái đầu tiên mà ta muốn gán giá trị có thể được cho giá trị 0 mà không mất tính tổng quát. Ta sẽ không thử bất kỳ giá trị nào khác cho chữ cái đó vì ta luôn có thể chuyển giá trị đó thành 0.
- Với chữ cái thứ hai để tô màu nó ta cần phải xét chỉ hai trường hợp: 1) Nó có cùng giá trị với chữ cái thứ nhất, tức là bằng 0, và 2) nó có giá trị khác. Trong trường hợp này ta chỉ cần cân nhắc 1 bởi vì ta đã thấy rằng tất cả các số có thể được nhân với 2..(N-1) (trong đó N là số nguyên tố các màu có sẵn) và vẫn có nghiệm tương đương. Vui lòng tham khảo phần này > 'Nếu có một phép tô màu ...'. Ví dụ, nếu N=5 và ta đã thử một giá trị khác cho chữ cái được chỉ định thứ 2, chẳng hạn như 3 và đã nhận được một lời giải thì nhân giá trị này (và tất cả các giá trị khác) với 2 sẽ làm 3 trở thành 3x2 = 6 ≡ mod 5 kết quả là 1. Do đó chữ cái thứ 2 chỉ cần thử 0 hoặc 1.
- Các bài kiểm tra cũng là các câu hỏi về mặt thời gian. Một người có thể tiết kiệm thời gian bằng cách nhập các số âm khi chúng dễ dàng tính toán hơn các số dương. Giao diện không cần số trong khoảng 0..N-1.
- Khi một phương trình chuyển thành màu đỏ thì điều kiện ≡ không được thoả mãn và ít nhất một số phải được thay đổi. Khi đó hãy thử một số khác. Để không bỏ qua các số ta có thể thử các số theo thứ tự 0,1,...,N-1 và dừng lại khi phép tô màu được tìm thấy.
- Khi đang lùi lại bằng cách nhấn vào nút hoàn tác, nếu ta thấy một phương trình màu tím thì ta có thể nhấn vào nút hoàn tác một lần nữa mà không cần phải suy nghĩ. Lý do là phương trình màu tím chỉ có một chữ cái và với chữ cái này chỉ có thể có một giá trị (mod N) nên không có giá trị nào khác cần được thử với chữ cái này trong trường hợp này.
- Để tìm một cách có hệ thống và không bỏ qua bất kỳ khả năng phép tô màu nào, ta có thể bắt đầu bằng việc gán cho mỗi biến giá trị 0 để đưa ra giải pháp tầm thường và sau đó bắt đầu lùi lại để có một giải pháp không tầm thường.
- Các biểu đồ nút thắt được dùng trong trò chơi này đã có số lượng tối thiểu các điểm giao nhau. Nhưng nếu một biểu đồ không tối thiểu thì nó sẽ là một lợi thế nếu rút gọn chúng trước tiên. Nếu không có các kỹ thuật phía trên để tăng tốc, ta sẽ phải thử NC phép tô màu, trong đó N là số lượng các màu và C là số lượng các điểm giao = số lượng các sợi. Giảm số lượng các điểm giao đi 1 sẽ làm giảm nỗ lực của một FACTOR của N.
Có những nút thắt không thể được tô màu hay không?
Có. Các nút với ít hơn 12 điểm giao mà không được tô màu là 0124, 10153, 11n34, 11n42, 11n49, 11n116 và, dĩ nhiên, là nút không có nút thắt. Hình ảnh cho thấy một biểu đồ của nút 10124.
Biểu đồ được đặt tên là 'Tuzun-Sikora' ở đầu tran g chỉ là một trong vô số các biểu đồ của nút không có nút thắt và do đó cũng không thể tô màu được.
Biểu đồ được đặt tên là 'Tuzun-Sikora' ở đầu tran g chỉ là một trong vô số các biểu đồ của nút không có nút thắt và do đó cũng không thể tô màu được.
Có nhiều bất biến màu sắc hơn không và chúng có thể được tính như thế nào?
Có, những bất biến bổ sung này là các bội số của lời giải, một bội cho mỗi số lượng màu có sẵn. Để hiểu những bình luận dưới đây, một số kiến thức về đại số tuyến tính là hữu ích.
Nếu một biểu đồ nút có C điểm giao nhau thì nó cũng có C cặp và do đó, hệ thống điều kiện có một ma trận hệ số CxC, trong đó mỗi hàng ngang đại diện cho giao điểm và nó gồm hai -1 và một 2 hoặc gồm a+1 và a-1 (Giao vòng lặp Reidemeister I). Mỗi cột dọc tương ứng với một sợi dây và có bằng số lượng số 2 bằng số lượng đường vượt qua của sợi dây, và có hai -1 và một -1 và một +1.
Các điều kiện tạo thành một hệ thống tuyến tính đồng nhất (phía bên tay phải chỉ chứa các số 0) và câu hỏi là tìm các số tô màu modulo tồn tại các giải pháp độc lập tuyến tính không cần thiết (màu sắc).
Giống như trong đại số tuyến tính, ma trận được đưa về dạng đường chéo bằng cách đổi chỗ các hàng ngang và cộng bội số của các hàng với các hàng khác. Ngoài ra, các bước này cũng được thực hiện với các cột. Điều không được phép ở đây là nhân các hàng và cột với một số vì điều đó sẽ thêm một modulo số màu mà định thức của ma trận sẽ bằng 0 và điều đó sẽ thêm một màu bổ sung. Thay vào đó, điều được thực hiện là chọn lặp đi lặp lại 2 thành phần khác 0 của một cột/hàng, giả sử A, B, để sử dụng thuật toán Euclid mở rộng để tìm p, q, thỏa mãn pA + qB = GCD(A, B). p,q là hệ số nhân của hai hàng/cột. Sau khi hoán đổi hàng/cột, GCD(A,B) trở thành phần tử đường chéo. Kết quả là một ma trận đường chéo được gọi là Dạng Chuẩn Smith trong đó góc trên cùng bên trái thường bắt đầu bằng 1 theo sau là các số là mỗi thừa số của số tiếp theo trong đường chéo. Phần tử đường chéo cuối cùng bằng 0 vì mỗi sơ đồ nút cho phép tô màu tầm thường chỉ bằng một màu. Do đó, chỉ cần tính toán Dạng Chuẩn Smith sau khi loại bỏ bất kỳ một cột và một hàng nào là đủ.
Tính toán định thức của ma trận hệ số C×C cho kết quả là không bởi vì các cột cộng lại bằng không. Tính toán định thức sau khi loại bỏ một hàng ngang và một cột dọc sẽ cho một số là tích của các số trên đường chéo của Dạng Chuẩn Smith. Do đó, cùng với một nỗ lực, Dạng Chuẩn Smith cung cấp nhiều thông tin hơn.
Ví dụ: Với biểu đồ có 83 đường giao ma trận hệ số có kích cỡ là 83x83.
Dạng Chuẩn Smith có một đường chéo bắt đầu ở góc trên bên trái với 79 nhân với 1 theo sau bởi 3, 3, 85837301265 (= 3 x 5 x 5722486751), 0. Điều này có nghĩa là có ba phép tô ba màu riêng biệt và một phép tô 85837301265 màu có nghĩa là cũng có một phép tô 5 màu, phép tô 15 màu, phép tô 3x5722486751 màu và 5x5722486751 màu.
Nếu một biểu đồ không được tô màu thì tất cả các số đường chéo là 1 ngoại trừ số 0 ở vị trí cuối cùng.
Biểu đồ sau thuộc về nút thắt 12a801.
Dạng Chuẩn Smith (SNF) có chín số 1 trong đường chéo, theo đó là 3, 45, 0. Ở dạng này, mỗi số là một thừa số của số có đường chéo tiếp theo. Và bội số của một phép tô màu là số phần tử đường chéo mà trong đó nó xuất hiện như một thừa số. Do đó, mỗi biểu đồ của nút thắt này có hai phép tô ba màu riêng biệt một phép tô 45 màu duy nhất, có nghĩa là nó cũng có một phép tô 5-,9-,15- duy nhất.
Nếu một biểu đồ nút có C điểm giao nhau thì nó cũng có C cặp và do đó, hệ thống điều kiện có một ma trận hệ số CxC, trong đó mỗi hàng ngang đại diện cho giao điểm và nó gồm hai -1 và một 2 hoặc gồm a+1 và a-1 (Giao vòng lặp Reidemeister I). Mỗi cột dọc tương ứng với một sợi dây và có bằng số lượng số 2 bằng số lượng đường vượt qua của sợi dây, và có hai -1 và một -1 và một +1.
Các điều kiện tạo thành một hệ thống tuyến tính đồng nhất (phía bên tay phải chỉ chứa các số 0) và câu hỏi là tìm các số tô màu modulo tồn tại các giải pháp độc lập tuyến tính không cần thiết (màu sắc).
Giống như trong đại số tuyến tính, ma trận được đưa về dạng đường chéo bằng cách đổi chỗ các hàng ngang và cộng bội số của các hàng với các hàng khác. Ngoài ra, các bước này cũng được thực hiện với các cột. Điều không được phép ở đây là nhân các hàng và cột với một số vì điều đó sẽ thêm một modulo số màu mà định thức của ma trận sẽ bằng 0 và điều đó sẽ thêm một màu bổ sung. Thay vào đó, điều được thực hiện là chọn lặp đi lặp lại 2 thành phần khác 0 của một cột/hàng, giả sử A, B, để sử dụng thuật toán Euclid mở rộng để tìm p, q, thỏa mãn pA + qB = GCD(A, B). p,q là hệ số nhân của hai hàng/cột. Sau khi hoán đổi hàng/cột, GCD(A,B) trở thành phần tử đường chéo. Kết quả là một ma trận đường chéo được gọi là Dạng Chuẩn Smith trong đó góc trên cùng bên trái thường bắt đầu bằng 1 theo sau là các số là mỗi thừa số của số tiếp theo trong đường chéo. Phần tử đường chéo cuối cùng bằng 0 vì mỗi sơ đồ nút cho phép tô màu tầm thường chỉ bằng một màu. Do đó, chỉ cần tính toán Dạng Chuẩn Smith sau khi loại bỏ bất kỳ một cột và một hàng nào là đủ.
Tính toán định thức của ma trận hệ số C×C cho kết quả là không bởi vì các cột cộng lại bằng không. Tính toán định thức sau khi loại bỏ một hàng ngang và một cột dọc sẽ cho một số là tích của các số trên đường chéo của Dạng Chuẩn Smith. Do đó, cùng với một nỗ lực, Dạng Chuẩn Smith cung cấp nhiều thông tin hơn.
Ví dụ: Với biểu đồ có 83 đường giao ma trận hệ số có kích cỡ là 83x83.
Dạng Chuẩn Smith có một đường chéo bắt đầu ở góc trên bên trái với 79 nhân với 1 theo sau bởi 3, 3, 85837301265 (= 3 x 5 x 5722486751), 0. Điều này có nghĩa là có ba phép tô ba màu riêng biệt và một phép tô 85837301265 màu có nghĩa là cũng có một phép tô 5 màu, phép tô 15 màu, phép tô 3x5722486751 màu và 5x5722486751 màu.
Nếu một biểu đồ không được tô màu thì tất cả các số đường chéo là 1 ngoại trừ số 0 ở vị trí cuối cùng.
Biểu đồ sau thuộc về nút thắt 12a801.
Dạng Chuẩn Smith (SNF) có chín số 1 trong đường chéo, theo đó là 3, 45, 0. Ở dạng này, mỗi số là một thừa số của số có đường chéo tiếp theo. Và bội số của một phép tô màu là số phần tử đường chéo mà trong đó nó xuất hiện như một thừa số. Do đó, mỗi biểu đồ của nút thắt này có hai phép tô ba màu riêng biệt một phép tô 45 màu duy nhất, có nghĩa là nó cũng có một phép tô 5-,9-,15- duy nhất.
Thống kê của phép tô màu nút thắt
Có một cái nhìn tổng quan về màu sắc có thể có của các nút nguyên tố lên đến một số kích thước hay không?
Tập tin văn bản
https://cariboutests.com/qi/knots/colour3-15-N.txt liệt kê với mỗi nút với các số giao nhau ≦ 15 tất cả các mục của Dạng Chuẩn Smith mà không phải là 0 hoặc 1. Những số này đã được tính từ một biểu đồ nhưng chúng là bất biến và do đó là giống nhau khi tính toán từ bất biểu đồ nào của nút thắt đó. Nếu bạn thích các bức tranh với các nút được tô màu thì bạn có thể tải một tấm áp phích trong bộ sưu tập áp phích của chúng tôi bằng cách nhấp vào trang chủ 'Home' > 'Posters' dẫn tới https://cariboutests.com/images/posters/knot_colouring_portrait.pdf.
N-khả năng tô màu dưới dạng một bất biến mạnh như thế nào?
Bảng dưới đây thể hiện việc sử dụng nhiều bất biến tô màu hơn tăng số lượng các lớp biến thể của các nút như thế nào, và do đó làm giảm số lượng trung bình của các nút ở mỗi lớp. Cột dọc bên phải thể hiện (#cr - 3)'th nghiệm của của số lượng các lớp bất biến tô màu gần như được giữ nguyên, trong đó #cr là số gia điểm của các nút.
Bảng 1: Thông số xung quanh các bất biến về màu sắc
# của cr: # của các điểm giao nhau
# của kn: # của các nút
# của cl1: # của các lớp khi chỉ xem xét danh sách các số nguyên tố tô màu
# của cl2: # của các lớp khi chỉ xem xét danh sách các bội số nguyên tố tô màu
# của cl3: # của các lớp khi chỉ xem xét danh sách các Mục Dạng Chuẩn Smith <>1
abs: exp(ln(noofcl3[cr])/(cr-3))
= (cr-3)th gốc của (# of cl3)
Bảng 1: Thông số xung quanh các bất biến về màu sắc
# của cr: # của các điểm giao nhau
# của kn: # của các nút
# của cl1: # của các lớp khi chỉ xem xét danh sách các số nguyên tố tô màu
# của cl2: # của các lớp khi chỉ xem xét danh sách các bội số nguyên tố tô màu
# của cl3: # của các lớp khi chỉ xem xét danh sách các Mục Dạng Chuẩn Smith <>1
abs: exp(ln(noofcl3[cr])/(cr-3))
= (cr-3)th gốc của (# of cl3)
| # của cr | # của kn | # của cl1 | kn/cl1 | # của cl2 | kn/cl2 | # của 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 |
Làm thế nào để số tô màu lớn nhất cho các nút thắt với C giao điểm phụ thuộc vào C?
Nếu ta lấy tất cả các nút thắt với số giao điểm C (<16) và tìm từ những nút thắt này nút có số tô màu cao nhất Nmax thì bảng sau đây cho thấy rằng Nmax tăng lên khoảng 1.7 lần khi tăng C lên 1.
Bảng 2L Bảng B(C) = Nmax1/(C−1)
Bảng 2L Bảng B(C) = Nmax1/(C−1)
| C | Nmax | nút | 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 |
Có chương trình máy tính nào có thể tính toán các phép tô màu không?
AsciiKnots là một chương trình máy tính tính toán tất cả các số tô màu cho một biểu đồ nút thắt đã cho bằng cách tính Mục Dạng Chuẩn Smith của ma trận hệ số. Nếu biểu đồ nút không có quá nhiều điểm giao thì nó cũng được tính bằng phương pháp thử nhiều phương pháp cho đến khi tìm được đáp án, phương pháp này được tối ưu, cho một số tô màu đã cho hoặc tất cả các số tô màu bao gồm cả màu của chúng.Ngoài tô màu, chương trình có thể tính nhiều thứ hơn nữa. Nó có thể được tải về từ
https://cariboutests.com/games/knots/AsciiKnots.tar.gz. AsciiKnots chạy trên hệ Linux. Những người dùng Windows nghiêm ngặt có thể cài đặt Ubuntu linux miễn phí dưới dạng một ứng dụng trên Windows 10. Các lệnh Linux để loại bỏ các phiên bản cũ đã được tải, để tải về bản mới nhất, giải nén và khởi động nó là
rm AsciiKnots.tar.gz
wget https://cariboutests.com/games/knots/AsciiKnots.tar.gz
tar xfz AsciiKnots.tar.gz
./AsciiKnots
Một chức năng tô màu bị hạn chế cũng có sẵn trên https://cariboutests.com/games/knots/knoteditor/ after selecting 'Tools' > 'Colour Knot'
Tài liệu tham khảo
[1] R. H. Fox, Metacyclic invariants of knots and links, Canadian Journal of Mathematics 22 (1970) 193−201.
[2] J. H. Przytycki, 3-coloring and other elementary invariants of knots. Banach Center Publications, Vol. 42, “Knot Theory”, Warszawa, 1998, 275−295.
[3] D. Rolfsen, Table of Knots and Links. Appendix C in Knots and Links. Wilmington, DE: Publish or Perish Press, pp. 280-287, 1976.
[4] J. C. Cha and C. Livingston, KnotInfo: Table of Knot Invariants, http://www. indiana.edu/~knotinfo
[5] “Colour Classification of Knots with Crossing Number up to 15”, 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-coloring and other elementary invariants of knots. Banach Center Publications, Vol. 42, “Knot Theory”, Warszawa, 1998, 275−295.
[3] D. Rolfsen, Table of Knots and Links. Appendix C in Knots and Links. Wilmington, DE: Publish or Perish Press, pp. 280-287, 1976.
[4] J. C. Cha and C. Livingston, KnotInfo: Table of Knot Invariants, http://www. indiana.edu/~knotinfo
[5] “Colour Classification of Knots with Crossing Number up to 15”, https:// cariboutests.com/qi/knots/colour3-15.txt
[6] T. Wolf, “A Knot Workbench”, https://cariboutests.com/games/knots/AsciiKnots.tar.gz
Theo dõi cập nhật sắp tới