Định lý con đường màu

A directed graph with a synchronizing coloring

Định lý con đường màu là bài toán được nhà toán học người Israel Benjamin Weiss đưa ra giả thiết lần đầu tiên năm 1970 và được Avraham Trahtman giải tháng 9 năm 2007.

Phát biểu

Một anh chàng đi đến một thị trấn mà anh ta chưa từng đặt chân đến bao giờ để tìm nhà người bạn gái của mình. Mặc dù các đoạn đường trong thị trấn đều không có gắn tên, người bạn gái của anh an ủi anh cứ yên tâm đi theo chỉ dẫn của mình thì anh sẽ đến được đúng nơi, sau một tập hợp hữu hạn các thao tác (rẽ trái, rẽ phải, rẽ phải...) và giả thiết là luôn tồn tại phương án hướng dẫn chỉ dẫn tổng quát để đến một vị trí cần đến, trong một hệ đóng mà ở đó không có con đường nào rẽ ra ngoài.

Chứng minh

Ứng dụng

Xem thêm

• Định lý bốn màu

Tham khảo

• Adler, R.L.; Weiss, B. (1970), Similarity of automorphisms of the torus, Memoires of the American Mathematical Society, quyển 98.
• Hegde, Rajneesh; Jain, Kamal (2005), "A min-max theorem about the road coloring conjecture", Proc. EuroComb 2005 (PDF), Discrete Mathematics & Theoretical Computer Science, tr. 279–284.
• Kari, Jarkko (2003), "Synchronizing finite automata on Eulerian digraphs", Theoretical Computer Science, 295 (1–3): 223–232, doi:10.1016/S0304-3975(02)00405-X.
• O'Brien, G. L. (1981), "The road-colouring problem", Israel Journal of Mathematics, 39 (1–2): 145–154, doi:10.1007/BF02762860.
• Trahtman, Avraham N. (2009), "The road coloring problem", Israel Journal of Mathematics, 172 (1): 51–60, arXiv:0709.0099, doi:10.1007/s11856-009-0062-5.