Planarity testing và crossing number tối thiểu
Kiểm tra phẳng naive tới hiệu quả, số giao cắt và giao cắt thẳng, giao đoạn thẳng đa tuyến Bezier.
Chuyên giaThuật toán ~60 phút
Ôn lại trước khi học
Giới thiệu
Bài này học kiểm đồ thị vẽ phẳng không rối dây. Dùng để vẽ sơ đồ mạch và luồng đọc dễ.
Kiến thức cần nhớ
Kiểm tra phẳng
- Định nghĩa: đồ thị phẳng là vẽ được không cắt nhau.
- Naive thử mọi cách xếp nên chỉ nổi đồ thị bé.
- Thuật toán nhanh thêm từng đỉnh giữ biên phẳng.
- Ví dụ đời thường: như xếp dây sạc không rối nhau.
- Đồ thị lớn phải dùng bản tuyến tính theo đỉnh cạnh.
Số giao cắt
- Định nghĩa: số cặp cạnh cắt ít nhất mọi cách vẽ.
- Cho cong thì luồn dễ, ít cắt hơn bắt thẳng.
- Bắt thẳng gọn mắt nhưng thường cắt nhiều hơn.
- Ví dụ đời thường: như dây cong luồn dễ hơn que thẳng.
- Tìm tối thiểu là khó nên dùng heuristic dần.
| Kiểu cạnh | Tính giao | Đẹp khi |
|---|---|---|
| Đoạn thẳng | Nhanh, định hướng | Sơ đồ kỹ thuật |
| Đa tuyến | Từng đoạn một | Gấp khúc vừa |
| Bezier cong | Giải bậc 2, chia nhỏ | Sơ đồ nhỏ cần mềm |
Tính giao hình học
- Hai đoạn cắt khi đầu này khác phía đường kia.
- Thẳng hàng thì kiểm tra hộp bao chứa nhau.
- Đa tuyến kiểm tra từng cặp đoạn thẳng nhỏ.
- Bezier giao thẳng cần giải bậc 2 hoặc chia nhỏ.
- Lọc bằng hộp bao trước rồi mới tính chính xác.
Ví dụ
- Input: đồ thị 5000 nút kiểm naive treo -> Output: đổi thuật toán tuyến tính.
- Giải thích: thử mọi cách bùng nổ nên không chạy nổi.
# Hai đoạn cắt khi khác phía nhau
def khac_phia(a, b, c, d):
return dinh_huong(a, b, c) * dinh_huong(a, b, d) < 0
print("cat nhau" if khac_phia else "khong cat")
💻 Bài tập
Ngôn ngữ: Python 3 (dùng networkx để đối chiếu). Nộp vào day-120/.
Bài 1: Giao cắt chính xác cho mọi trường hợp
Nâng cấp hàm ngày 79:
| Hàm | Yêu cầu |
|---|---|
orientation(p, q, r) | Trả -1, 0, 1. Dùng số nguyên hoặc fractions.Fraction để tránh sai số |
on_segment(p, q, r) | q nằm trên đoạn pr khi thẳng hàng |
segments_intersect(a, b, c, d) | Xử lý cả trường hợp thẳng hàng chồng nhau và chạm đầu mút |
polyline_crossings(e1, e2) | Đếm giao cắt giữa 2 đa tuyến |
(0,0)-(2,2) và (0,2)-(2,0) -> cắt
(0,0)-(2,0) và (1,0)-(3,0) -> chồng (thẳng hàng)
(0,0)-(1,1) và (1,1)-(2,0) -> chạm đầu mút (không tính nếu 2 cạnh chung đỉnh)
(0,0)-(1,0) và (2,0)-(3,0) -> không cắt
Bài 2: Kiểm tra phẳng tăng dần
- Cài kiểm tra phẳng ngây thơ cho đồ thị nhỏ (
n <= 8): thử mọi hoán vị đỉnh trên vòng tròn và kiểm tra định lý Kuratowski bằng cách tìm đồ thị con đồng phôi với K5, K3,3 (có thể dùngnetworkxđể tìm, rồi tự kiểm tra kết quả). - So kết quả với
networkx.check_planaritytrên 200 đồ thị ngẫu nhiênn = 6..8. - Đo thời gian
check_planaritytrên đồ thị phẳng lớn (lưới 100x100 và tam giác hóa Delaunay 10^4 điểm). Xác nhận thời gian gần tuyến tính.
Bài 3: Crossing number nhỏ (nâng cao)
- Với vẽ thẳng, viết heuristic giảm giao cắt: bắt đầu từ
circular_layout, lặp dời 1 đỉnh tới vị trí làm giảm giao cắt nhiều nhất trong 50 vị trí thử. - Chạy trên K5, K6, K3,3, K4,4. So với giá trị đã biết:
cr(K5) = 1,cr(K6) = 3,cr(K3,3) = 1,cr(K4,4) = 4. - Vẽ bức tranh tốt nhất cho mỗi đồ thị.
✅ Tiêu chí hoàn thành
- 4 test giao cắt pass, không dùng số thực cho phép so sánh.
- Kiểm tra phẳng khớp
networkxtrên 200 đồ thị. - Bảng số giao cắt heuristic so với giá trị đã biết.
- Có hình 4 đồ thị.
❓ Câu hỏi ôn tập
- Đồ thị phẳng là gì?
- Vì sao naive chỉ chạy bé?
- Cong khác thẳng ở gì?
- Hộp bao để làm gì?
🌕 Bạn đã hoàn thành ngày 120. Làm hết bài tập phía trên rồi sang ngày tiếp theo.