Trình Kiểm Tra Đồ Thị Phẳng

Giới thiệu về Trình Kiểm Tra Đồ Thị Phẳng

Trình Kiểm tra Đồ thị Phẳng xác định liệu một đơn đồ thị vô hướng có phải là phẳng — có thể vẽ được trên mặt phẳng mà không có hai cạnh nào cắt nhau — và khi đồ thị không vượt qua bài kiểm tra, nó sẽ tìm và trực quan hóa minh chứng Kuratowski: một phân chia của K₅ (đồ thị đầy đủ trên 5 đỉnh) hoặc K₃,₃ (đồ thị hai phía đầy đủ trên 3 + 3 đỉnh). Công cụ này được xây dựng cho việc giảng dạy, khởi động lập trình thi đấu và kiểm tra nhanh các cấu trúc đồ thị nhỏ.

"Phẳng" Nghĩa là Gì?

Một đồ thị G = (V, E) là phẳng nếu nó có thể được nhúng vào mặt phẳng sao cho các cạnh chỉ gặp nhau tại các điểm đầu chung — không có điểm cắt. Tương đương, G có thể được vẽ trên bề mặt của một hình cầu mà không có điểm cắt. Tính phẳng là một thuộc tính thuần túy topo: nó không phụ thuộc vào cách bạn vẽ đồ thị, mà chỉ phụ thuộc vào việc liệu có tồn tại một cách vẽ không có điểm cắt nào hay không.

Đồ thị phẳng xuất hiện ở khắp mọi nơi — mạng lưới đường bộ và tiện ích, định tuyến bảng mạch in, đồ thị cạnh của các khối đa diện và cấu trúc mặt của các khối đa diện. Tuy nhiên, nhiều đồ thị "tự nhiên" lại kiên trì không phẳng: bất cứ khi nào bạn cố gắng kết nối 3 ngôi nhà với 3 tiện ích mà không có điểm cắt, bạn sẽ đụng phải rào cản K₃,₃.

Định Lý Kuratowski — Trái Tim của Trình Kiểm Tra

Kazimierz Kuratowski đã chứng minh vào năm 1930 rằng tính phẳng có một đặc tính tổ hợp thuần túy:

Một phân chia của một đồ thị H có được bằng cách thay thế một số cạnh của H bằng các đường đi dài hơn mà các đỉnh nội bộ của chúng đều là các đỉnh bậc 2 mới. Do đó, định lý Kuratowski nói rằng K₅ và K₃,₃ là các vật cản duy nhất đối với tính phẳng — mọi đồ thị không phẳng đều chứa một trong số chúng dưới dạng "kéo dài".

Các Đồ Thị Bị Cấm

Công Thức Euler và Các Điều Kiện Cần Nhanh

Trước khi chạy tìm kiếm phân chia (tương đối tốn kém), trình kiểm tra sẽ áp dụng hai điều kiện cần nhanh được rút ra từ công thức Euler: đối với bất kỳ đồ thị phẳng liên thông nào được vẽ trên mặt phẳng với V đỉnh, E cạnh và F mặt (tính cả mặt ngoài không giới hạn), chúng ta có

Kết hợp với nhận xét rằng mọi mặt của một đơn đồ thị phẳng có ít nhất 3 cạnh trên biên, chúng ta có giới hạn trên của số cạnh

Bất kỳ đồ thị nào vi phạm các bất đẳng thức này đều ngay lập tức không phẳng, không cần tìm kiếm phân chia. K₅ có m = 10, n = 5 ⇒ 3n − 6 = 9, vì 10 > 9 nên vi phạm giới hạn. K₃,₃ có m = 9, n = 6 ⇒ 2n − 4 = 8, vì 9 > 8 nên vi phạm giới hạn hai phía.

Cách Thức Tìm Kiếm Phân Chia Hoạt Động

Sau các bước kiểm tra Euler giá rẻ, trình kiểm tra sẽ tìm kiếm phân chia trực tiếp:

1. Thắng nhanh — phát hiện K₅ hoặc K₃,₃ dưới dạng đồ thị con đen. Nếu 5 đỉnh kề nhau từng đôi một, đó chính là K₅. Nếu 6 đỉnh chia thành 3 + 3 với tất cả 9 cạnh chéo hiện diện, đó chính là K₃,₃.
2. Tìm kiếm phân chia K₅. Đối với mỗi tập hợp ứng viên gồm 5 đỉnh "nhánh" (mỗi đỉnh có bậc ≥ 4 trong G), cố gắng tìm 10 đường đi — mỗi đường cho một cặp nhánh — mà chúng không giao nhau tại đỉnh nội bộ (không có đỉnh không phải nhánh nào xuất hiện trong nhiều hơn một đường đi) và tránh sử dụng các nhánh khác làm đỉnh nội bộ. Một kết quả khớp chứng minh tính không phẳng.
3. Tìm kiếm phân chia K₃,₃. Chọn 6 nhánh (mỗi nhánh có bậc ≥ 3) và một phân hoạch hai phía 3 + 3. Tìm kiếm 9 đường đi cặp chéo với cùng yêu cầu không giao nhau tại đỉnh nội bộ.
4. Không có minh chứng ⇒ phẳng. Nếu không tìm thấy phân chia nào trong giới hạn kích thước, định lý Kuratowski đảm bảo đồ thị là phẳng.

Tìm kiếm các đường đi không giao nhau tại đỉnh nói chung là bài toán NP-khó, vì vậy trình kiểm tra sử dụng tìm kiếm tham lam ngẫu nhiên có giới hạn: mỗi lần lặp sẽ sắp xếp các cặp yêu cầu theo độ khó, chọn đường đi cho cặp khó nhất trước bằng BFS ngẫu nhiên, loại bỏ các đỉnh nội bộ đó và tiếp tục. Nếu thứ tự cụ thể đó thất bại, nó sẽ thử lại với thứ tự đã xáo trộn — tối đa 40 lần thử cho mỗi cấu hình nhánh. Trên mọi đồ thị nhỏ được kiểm tra (tối đa 16 đỉnh), điều này đủ để xác định minh chứng bất cứ khi nào nó tồn tại.

Cách Sử Dụng Công Cụ Tính Này

1. Chọn định dạng đầu vào bằng cách sử dụng các tab ở trên cùng: danh sách cạnh hoặc danh sách kề. Cả hai đều mã hóa cùng một đồ thị.
2. Nhập đồ thị của bạn. Đồ thị được coi là vô hướng, vì vậy A-B và B-A là cùng một cạnh.
3. Nhấp vào Kiểm tra tính phẳng. Công cụ báo cáo kết quả, hiển thị lập luận từng bước (Euler, hai phía, Kuratowski) và hiển thị đồ thị.
4. Đối với đồ thị không phẳng, phần trực quan hóa sẽ tô màu phân chia K₅ hoặc K₃,₃ và liệt kê 10 (hoặc 9) đường đi không giao nhau tại đỉnh. Nhấp vào một hàng đường đi để tách biệt nó.
5. Đối với đồ thị phẳng, số mặt F = m − n + 1 + c được báo cáo cùng với cấu trúc đồ thị.

Ví dụ 1 — K₄ là phẳng

K₄ có n = 4, m = 6. Mọi đồ thị trên ≤ 4 đỉnh đều phẳng, và thực tế K₄ nhúng dưới dạng một hình tam giác với một đỉnh duy nhất bên trong được nối với cả ba góc. Euler nói rằng có F = 6 − 4 + 2 = 4 mặt: ba mặt tam giác bên trong cộng với mặt bên ngoài.

Ví dụ 2 — K₃,₃ không phẳng

K₃,₃ có n = 6, m = 9. Nó là đồ thị hai phía, vì vậy giới hạn hai phía được áp dụng: m = 9 > 2n − 4 = 8. Chỉ riêng điều này đã chứng minh tính không phẳng. Minh chứng rất rõ ràng — bản thân K₃,₃ chính là đồ thị con bị cấm. Công cụ sau đó làm nổi bật phân hoạch 3 + 3 và 9 cạnh trực tiếp.

Ví dụ 3 — Đồ thị Petersen

Đồ thị Petersen có n = 10, m = 15, do đó m ≤ 3n − 6 = 24 và các bước kiểm tra Euler nhanh đã vượt qua. Tuy nhiên, nó nổi tiếng là không phẳng. Trình kiểm tra xác định được một phân chia K₃,₃: chọn sáu đỉnh từ ngũ giác ngoài và ngũ giác trong sao cho mọi cặp chéo có thể được định tuyến qua bốn đỉnh còn lại bằng các đường đi không giao nhau tại đỉnh. Công cụ vẽ minh chứng, làm cho hình học của những năm 1930 trở nên hữu hình.

Ứng Dụng của Tính Phẳng

• Định tuyến VLSI và PCB. Một mạch đơn lớp chỉ khả thi nếu đồ thị kết nối là phẳng; các mạng không phẳng buộc phải sử dụng các lỗ thông (vias) hoặc các lớp bổ sung.
• Vẽ đồ thị và trực quan hóa. Đồ thị phẳng cho phép bố cục rõ ràng, không có điểm cắt — hữu ích cho bản đồ tàu điện ngầm, đồ thị gọi hàm và sơ đồ nguyên lý.
• Thiết kế thuật toán. Nhiều bài toán NP-khó (cắt lớn nhất, phủ đỉnh, đẳng cấu đồ thị) trở thành bài toán thời gian đa thức khi giới hạn trong đồ thị phẳng.
• Tô màu đồ thị. Định lý Bốn màu đảm bảo mọi đồ thị phẳng đều có thể tô bằng 4 màu — một kết quả kinh điển mà phát biểu của nó phụ thuộc vào tính phẳng.
• Tối ưu hóa tổ hợp. Đường đi ngắn nhất phẳng, luồng cực đại và cắt cực tiểu đều có các thuật toán nhanh chuyên biệt.
• Hóa học phân tử. Đồ thị hydrocarbon thơm vòng benzene là phẳng; một số phân tử dạng lồng thì không.

Câu Hỏi Thường Gặp

Đồ thị phẳng nghĩa là gì?

Một đồ thị là phẳng nếu bạn có thể vẽ nó trên mặt phẳng sao cho không có hai cạnh nào cắt nhau ngoại trừ tại các đỉnh chung. Tương đương, một đồ thị là phẳng nếu và chỉ nếu nó có thể được vẽ trên bề mặt của một hình cầu mà không có điểm cắt. Cây, chu trình, đồ thị khối lập phương và các khối đa diện đều là đồ thị phẳng, trong khi K₅ và K₃,₃ là các ví dụ điển hình về đồ thị không phẳng.

Định lý Kuratowski là gì?

Định lý Kuratowski phát biểu rằng một đồ thị hữu hạn là phẳng nếu và chỉ nếu nó không chứa đồ thị con nào là một phân chia của K₅ hoặc K₃,₃. Một phân chia có được bằng cách thay thế một số cạnh bằng các đường đi dài hơn, mỗi đường đi qua các đỉnh bậc 2 hoàn toàn mới. Điều này cung cấp một minh chứng tổ hợp cụ thể cho tính không phẳng.

Sự khác biệt giữa K₅ và K₃,₃ là gì?

K₅ có 5 đỉnh, mọi cặp đỉnh được nối với nhau bằng một cạnh, tổng cộng có 10 cạnh. K₃,₃ có 6 đỉnh được chia thành hai nhóm mỗi nhóm 3 đỉnh, với mọi đỉnh trong nhóm này được nối với mọi đỉnh trong nhóm kia, tổng cộng có 9 cạnh. Cả hai đều là những đồ thị không phẳng nhỏ nhất cùng loại, và cùng nhau chúng tạo thành các đồ thị con cấm cho tính phẳng.

Bất đẳng thức Euler giúp ích gì?

Công thức Euler V − E + F = 2 cho đồ thị phẳng liên thông kết hợp với thực tế là mỗi mặt của đơn đồ thị phẳng có ít nhất 3 cạnh dẫn đến m ≤ 3n − 6. Bất kỳ đơn đồ thị nào vi phạm giới hạn này đều ngay lập tức không phẳng. Đối với đồ thị phẳng hai phía, mỗi mặt có ít nhất 4 cạnh, đưa ra giới hạn chặt hơn m ≤ 2n − 4. Trình kiểm tra áp dụng cả hai như quy tắc loại bỏ nhanh.

Giới hạn kích thước là bao nhiêu?

Trình kiểm tra xử lý tối đa 16 đỉnh và 60 cạnh. Điều này bao gồm các đồ thị giảng dạy và thi đấu điển hình như đồ thị Petersen, đồ thị Möbius-Kantor, khối siêu lập phương nhỏ và đồ thị đầy đủ K₇. Các đồ thị lớn hơn yêu cầu các bài kiểm tra tính phẳng chuyên biệt thời gian tuyến tính như Hopcroft-Tarjan.

Phân chia minh chứng được vẽ như thế nào?

Khi đồ thị không phẳng, 5 đỉnh nhánh của K₅ được tìm thấy — hoặc 6 đỉnh nhánh của K₃,₃ chia thành hai bộ ba A và B — sẽ được làm nổi bật trên một vòng tròn nội bộ. 10 (hoặc 9) đường đi không giao nhau tại đỉnh được yêu cầu sẽ được vẽ bằng các màu riêng biệt để bạn có thể theo dõi cấu trúc liên kết K₅ hoặc K₃,₃ một cách trực quan. Các đỉnh và cạnh không nằm trong phân chia sẽ bị làm mờ đi.

Đọc Thêm

• Đồ thị phẳng — Wikipedia
• Định lý Kuratowski — Wikipedia
• Đặc trưng Euler — Wikipedia
• Đồ thị Petersen — Wikipedia
• Định lý Wagner (phiên bản minor) — Wikipedia