Đồ thị phẳng: nhúng và định lý Kuratowski

Giới thiệu

Bài này học đồ thị phẳng và định lý Kuratowski. Bạn dùng nó để vẽ sơ đồ ít giao cắt nhất.

Kiến thức cần nhớ

Nhúng và đồ thị phẳng

• Nhúng là cách đặt đỉnh và vẽ cạnh lên mặt phẳng.
• Cùng 1 đồ thị có nhúng rối và nhúng gọn.
• Phẳng là tính chất của đồ thị, rối là tính chất của bức vẽ.
• Ví dụ đời thường: như cùng 1 mớ dây, xếp khéo thì không rối.

Hai chướng ngại K5 và K3-3

• K5: 5 đỉnh nối đôi một, kiểu gì cũng thừa 1 giao cắt.
• K3-3: 2 nhóm 3 đỉnh nối chéo hết, bài toán 3 nhà 3 giếng.
• Quá nhiều cạnh dồn vào ít đỉnh thì phải cắt nhau.
• Ví dụ đời thường: như vẽ quá nhiều đường bay trên 1 tờ giấy.

Định lý Kuratowski

• Đồ thị phẳng khi và chỉ khi không chứa bản phóng K5 hay K3-3.
• Bản phóng là chèn thêm đỉnh bậc 2 lên cạnh cũ.
• Muốn chứng minh không phẳng thì moi K5 hoặc K3-3 ra.
• Muốn thêm cạnh mà giữ phẳng thì kiểm tra chướng ngại trước.

Kiểu vẽ cạnh

• Đoạn thẳng: đơn giản nhưng dễ cắt nhau.
• Đa tuyến bẻ góc: vòng tránh được chỗ đông.
• Cong Bezier: mềm và dễ bó nhưng tính giao tốn hơn.
• Tránh vẽ đỉnh chạm cạnh dù không nối vì gây hiểu nhầm.

Ví dụ

• Input: đồ thị chứa K3-3 phóng, đòi vẽ phẳng tuyệt đối. Output: báo không thể.
• Giải thích: có chướng ngại thì phải chuyển sang tối thiểu giao cắt.
• Input: sơ đồ đầy giao cắt nhưng đồ thị nền phẳng. Output: chẩn đoán nhúng xấu.
• Giải thích: cần vẽ lại chứ không phải đổi dữ liệu.

💻 Bài tập

Ngôn ngữ: Python 3 với networkx và matplotlib. Nộp vào day-079/.

Bài 1: Đếm giao cắt của một bức vẽ

K4 vẽ hình vuông có 2 đường chéo -> 1 giao cắt
K4 vẽ tam giác có 1 đỉnh ở giữa   -> 0 giao cắt

Bài 2: Kiểm tra phẳng bằng điều kiện cần

1. Viết edge_bound_check(G): đồ thị phẳng đơn liên thông có $n \ge 3$ thì $m \le 3n - 6$. Nếu không có tam giác thì $m \le 2n - 4$.
2. Áp vào K5, K3,3, cây 10 đỉnh, lưới 4x4. Chỉ ra trường hợp điều kiện cần không đủ để kết luận.
3. So với networkx.check_planarity. Với đồ thị không phẳng, dùng counterexample để lấy đồ thị con Kuratowski và vẽ nó ra.

K5: m = 10 > 3*5 - 6 = 9  -> chắc chắn không phẳng
K3,3: m = 9 <= 12 nhưng không có tam giác: 9 > 2*6 - 4 = 8 -> không phẳng

Bài 3: Vẽ phẳng (nâng cao)

1. Với đồ thị phẳng, dùng networkx.planar_layout để có bức vẽ 0 giao cắt. Kiểm tra bằng count_crossings.
2. So spring_layout, circular_layout, planar_layout trên 3 đồ thị phẳng (lưới 5x5, đồ thị bánh xe 10 đỉnh, cây nhị phân 31 đỉnh). In bảng số giao cắt.
3. Thêm từng cạnh ngẫu nhiên vào lưới 5x5 cho tới khi mất tính phẳng. In cạnh làm mất tính phẳng và đồ thị con Kuratowski.

✅ Tiêu chí hoàn thành

• Test mẫu đếm giao cắt pass.
• Bảng điều kiện cần cho 4 đồ thị kèm nhận xét.
• Có hình đồ thị con Kuratowski.
• Bảng số giao cắt 3 layout có số thật.

❓ Câu hỏi ôn tập

• Nhúng phẳng nghĩa là gì?
• K5 và K3-3 là gì?
• Định lý Kuratowski nói gì?
• Khi nào nên chấp nhận giao cắt?

🌕 Bạn đã hoàn thành ngày 79. Làm hết bài tập phía trên rồi sang ngày tiếp theo.