Check circular coloring
Check circular coloring
The video could not load. Check your connection and try again, or download it directly.
Download video
Open Chinese transcript
- 四个座位围成一圈,颜色依次是红、蓝、红、蓝。环形中首尾也相邻。
- 先查1号和2号,是红与蓝,不同色。
- 再查2号和3号,是蓝与红;3号和4号是红与蓝,也都不同。
- 最后不能漏掉4号与1号。它们是蓝与红,仍然不同。
- 四条相邻边:一号和二号、二号和三号、三号和四号、四号和一号,全部通过。
- 因此这组颜色安排可行。检查环形约束时,必须补上最后一个与第一个的边。线性序列只查三条边,环形还必须多查首尾这一条边。
Sources for this explanation
Logical thinking
Check every cycle edge, including the last-to-first edge.
Worked example
Four circular seats are red, blue, red, blue. Adjacent seats, including 4 and 1, must differ. Is it valid?
All four edges 1–2, 2–3, 3–4 and 4–1 connect different colors.
Try one question
Seats 3 and 1 are adjacent and both red.