Một đồ thị phẳng, hay Planar Graph, được định nghĩa là một đồ thị có thể được vẽ trên một mặt phẳng mà không có bất kỳ hai cạnh nào cắt nhau. Điều này có nghĩa là bạn có thể đặt tất cả các đỉnh của đồ thị trên một mặt phẳng sao cho tất cả các cạnh đều là các đường thẳng không giao nhau, ngoại trừ ở các đỉnh mà chúng gặp nhau. Sự phẳng của đồ thị giúp chúng trở nên dễ hiểu và phân tích hơn, đồng thời giúp biểu diễn các mối quan hệ phức tạp một cách trực quan.
Đồ thị phẳng đóng một vai trò quan trọng trong nhiều lĩnh vực khác nhau, từ khoa học máy tính, toán học đến kỹ thuật. Trong khoa học máy tính, chúng thường được sử dụng trong thiết kế mạch và lập trình đồ họa, nơi việc tránh các cạnh cắt nhau là cần thiết để giảm độ phức tạp và tối ưu hóa hiệu suất. Trong toán học, đồ thị phẳng giúp chúng ta nghiên cứu các tính chất hình học và topo một cách trực quan, qua đó mở ra cánh cửa cho nhiều khám phá và chứng minh mới. Đồ thị phẳng cũng có ứng dụng trong kỹ thuật, đặc biệt trong quy hoạch đô thị và thiết kế mạng, nơi việc phân bổ các tuyến đường và mạng lưới cần được tối ưu hóa để tránh sự chồng chéo và lãng phí không gian.
Đặc điểm và tính chất của Planar Graph
Đồ thị phẳng có những đặc điểm và tính chất độc đáo giúp chúng nổi bật so với các loại đồ thị khác. Đặc điểm cơ bản nhất là khả năng biểu diễn đồ thị trên một mặt phẳng mà không có hai cạnh nào giao nhau, ngoại trừ tại các đỉnh mà chúng kết nối. Điều này không chỉ giúp đồ thị dễ hiểu và phân tích hơn mà còn tạo ra cơ sở để nghiên cứu thêm về các tính chất topo và hình học của đồ thị.
Để một đồ thị được coi là đồ thị phẳng, nó phải thỏa mãn điều kiện có thể được vẽ trên mặt phẳng mà không có sự chéo cắt giữa các cạnh. Điều này đòi hỏi mỗi cạnh phải được vẽ dưới dạng một đường thẳng hoặc đường cong không gặp bất kỳ cạnh nào khác, ngoại trừ tại các điểm cuối của chúng.
Một trong những công thức quan trọng nhất liên quan đến đồ thị phẳng là công thức Euler, được biểu diễn là (V – E + F = 2), trong đó (V) là số đỉnh, (E) là số cạnh, và (F) là số mặt (kể cả mặt ngoài cùng). Công thức này mô tả mối quan hệ giữa số lượng đỉnh, cạnh và mặt của một đồ thị phẳng và cung cấp một công cụ mạnh mẽ để chứng minh và phân tích các tính chất của đồ thị phẳng. Công thức này cũng giúp xác định liệu một đồ thị có thể được vẽ mà không có cạnh chéo hay không, qua đó khẳng định tính phẳng của đồ thị đó.
Một đồ thị được cho là phẳng nếu nó có thể được vẽ trong một mặt phẳng sao cho không có cạnh nào cắt ngang.
Ví dụ: Đồ thị trong hình là đồ thị phẳng.
Region of a Graph: Xét một đồ thị phẳng G = (V, E). Một vùng được xác định là một vùng của mặt phẳng bị giới hạn bởi các cạnh và không thể chia nhỏ hơn nữa. Biểu đồ phẳng chia các kế hoạch thành một hoặc nhiều vùng. Một trong những vùng này sẽ là vô hạn.
Finite Region: Nếu diện tích của vùng là hữu hạn thì vùng đó được gọi là vùng hữu hạn.
Infinite Region: Nếu diện tích của vùng là vô hạn, vùng đó được gọi là vùng vô hạn. Một đồ thị phẳng chỉ có một vùng vô hạn.
Ví dụ: Hãy xem xét đồ thị trong hình. Xác định số vùng, vùng hữu hạn và vùng vô hạn.
Biểu diễn một đồ thị phẳng
Biểu diễn một đồ thị phẳng đòi hỏi việc sắp xếp các đỉnh và vẽ các cạnh sao cho chúng không giao nhau trên mặt phẳng. Đây là một quá trình cẩn thận và thường yêu cầu một số thử nghiệm để tìm ra cách sắp xếp tối ưu. Để bắt đầu, hãy xác định vị trí của các đỉnh trên mặt phẳng. Cố gắng phân bổ chúng một cách đồng đều để tránh tình trạng quá đông đúc và làm tăng khả năng cạnh giao nhau.
Khi các đỉnh đã được đặt, bước tiếp theo là vẽ các cạnh. Bắt đầu với các cạnh ngắn nhất hoặc những cạnh quan trọng nhất, và tiếp tục vẽ từng cạnh một, đảm bảo rằng không có cạnh nào cắt qua cạnh khác. Trong trường hợp gặp khó khăn với việc vẽ một cạnh mà không làm giao nhau, bạn có thể cần phải điều chỉnh vị trí của một số đỉnh.
Ví dụ, giả sử bạn có một đồ thị đơn giản với 4 đỉnh tạo thành hình vuông và một đỉnh ở giữa kết nối với tất cả các đỉnh khác. Bạn sẽ bắt đầu bằng cách đặt 4 đỉnh tạo thành hình vuông trên giấy, sau đó đặt đỉnh thứ 5 ở trung tâm. Tiếp theo, vẽ các cạnh từ đỉnh trung tâm tới các đỉnh ở góc mà không làm chúng cắt nhau, tạo thành một hình dạng giống như cái ô. Kết quả cuối cùng là một đồ thị phẳng mà tất cả các cạnh đều được vẽ mà không giao nhau.
Cách tiếp cận này không chỉ giúp biểu diễn đồ thị trở nên rõ ràng và dễ hiểu hơn mà còn tạo điều kiện cho việc phân tích và nghiên cứu đồ thị. Đồ thị phẳng khi được vẽ đúng cách sẽ cho thấy một cách trực quan các đặc điểm và mối quan hệ giữa các đỉnh và cạnh, từ đó hỗ trợ trong việc giải quyết các bài toán liên quan đến đồ thị.
Định Lý và Bổ Đề đồ thị phẳng
Định lý Kuratowski là một trong những kết quả quan trọng nhất trong lý thuyết đồ thị phẳng. Định lý này đặc trưng hóa đồ thị phẳng dựa trên sự không tồn tại của hai loại đồ thị con cụ thể, đó là (K_5) và (K_{3,3}). (K_5) là đồ thị đầy đủ với 5 đỉnh, nghĩa là mỗi đỉnh đều được kết nối trực tiếp với bốn đỉnh còn lại. (K_{3,3}) là đồ thị hai phần đầy đủ với hai tập hợp mỗi tập có 3 đỉnh, trong đó mỗi đỉnh của tập này được kết nối với tất cả các đỉnh của tập kia, nhưng không có cạnh nào nối hai đỉnh trong cùng một tập. Định lý Kuratowski khẳng định rằng một đồ thị là phẳng nếu và chỉ nếu nó không chứa bất kỳ đồ thị con thu gọn nào isomorph với (K_5) hoặc (K_{3,3}).
Bổ đề về số cạnh của đồ thị phẳng cung cấp một hạn chế về số lượng cạnh mà một đồ thị phẳng có thể có dựa trên số đỉnh của nó, đặc biệt là trong trường hợp đồ thị không chứa chu trình 3-đỉnh (đồ thị tam giác). Công thức (E \leq 3V – 6) mô tả mối quan hệ này, trong đó (E) là số cạnh và (V) là số đỉnh của đồ thị. Công thức này cho thấy số lượng cạnh tối đa mà một đồ thị phẳng có thể có khi không chứa chu trình 3-đỉnh, đồng thời cung cấp một công cụ hữu ích để kiểm tra tính phẳng của đồ thị khi biết số đỉnh và cạnh.
Cả Định lý Kuratowski và Bổ đề về số cạnh đều giúp nhà toán học và nhà khoa học máy tính không chỉ xác định tính phẳng của đồ thị mà còn hiểu rõ hơn về cấu trúc và giới hạn của các đồ thị phẳng, từ đó ứng dụng vào các vấn đề thực tế trong nhiều lĩnh vực khác nhau.
Phân loại đồ thị phẳng
Trong lĩnh vực đồ thị phẳng, có hai loại đặc biệt quan trọng cần được chú ý: đồ thị phẳng đầy đủ và đồ thị phẳng hai phần.
Đồ thị phẳng đầy đủ (K_4):
Đồ thị (K_4) là một ví dụ điển hình của đồ thị phẳng đầy đủ. Đây là đồ thị có 4 đỉnh và mỗi đỉnh được kết nối với ba đỉnh còn lại, tạo ra tổng cộng 6 cạnh. Đặc điểm nổi bật của (K_4) là khả năng vẽ nó trên mặt phẳng mà không có bất kỳ hai cạnh nào giao nhau, làm cho nó trở thành một ví dụ hoàn hảo của đồ thị phẳng. (K_4) cũng thú vị vì nó là đồ thị phẳng đầy đủ lớn nhất; bất kỳ đồ thị đầy đủ nào với nhiều hơn 4 đỉnh đều không thể là đồ thị phẳng do sẽ tồn tại các cạnh phải giao nhau.
Đồ thị phẳng hai phần (K_{3,3}):
Mặc dù (K_{3,3}) thường được đề cập đến khi nói về Định lý Kuratowski như một ví dụ của đồ thị không phẳng, nhưng nó cũng cung cấp cái nhìn sâu sắc về đặc điểm của đồ thị phẳng hai phần. (K_{3,3}) bao gồm hai tập hợp đỉnh, mỗi tập hợp có ba đỉnh, và mỗi đỉnh của một tập hợp được kết nối với tất cả các đỉnh của tập hợp kia, tạo ra tổng cộng 9 cạnh. Điều thú vị là không thể vẽ (K_{3,3}) trên mặt phẳng mà không có các cạnh giao nhau, điều này minh họa rõ ràng rằng không phải tất cả các đồ thị hai phần đều là đồ thị phẳng. Điều này giúp làm sáng tỏ sự khác biệt giữa đồ thị hai phần có thể và không thể được biểu diễn như một đồ thị phẳng.
Cả (K_4) và (K_{3,3}) đều là những ví dụ quan trọng giúp chúng ta hiểu rõ hơn về cấu trúc và giới hạn của đồ thị phẳng, cũng như cung cấp cái nhìn sâu sắc về cách mà các đỉnh và cạnh có thể được tổ chức trong không gian hai chiều mà không gây ra sự chéo cắt.
Non-Planar Graph
Một đồ thị được cho là không phẳng nếu nó không thể được vẽ trong một mặt phẳng sao cho không có cạnh nào cắt ngang.
Ví dụ: Các đồ thị trong hình là đồ thị không phẳng.
Các đồ thị này không thể được vẽ trong một mặt phẳng để không có cạnh nào cắt nhau do đó chúng là đồ thị không phẳng.
Thuộc tính của Non-Planar Graph:
Một biểu đồ là không phẳng nếu và chỉ khi nó chứa một biểu đồ con biến hình thành K5 hoặc K3,3
Ví dụ 1: Chứng tỏ rằng K5 là không phẳng.
Lời giải: Đồ thị hoàn chỉnh K5 chứa 5 đỉnh và 10 cạnh.
Bây giờ, cho một đồ thị phẳng được kết nối 3v-e≥6.
Do đó, với K5, chúng ta có 3 x 5-10 = 5 (không thỏa mãn tính chất 3 vì nó phải lớn hơn hoặc bằng 6).
Như vậy, K5 là một đồ thị không phẳng.
Ví dụ 2: Chứng tỏ rằng các đồ thị trong hình là không phẳng bằng cách tìm một hình đồng dạng đồ thị con cho K5 hoặc K3,3.
Giải: Nếu chúng ta loại bỏ các cạnh (V1, V4), (V3, V4) và (V5, V4) thì đồ thị G1 sẽ trở thành đồng phân hình với K5, do đó nó không phẳng.
Nếu chúng ta loại bỏ các cạnh V2, V7) thì đồ thị G2 trở thành đồng dạng của K3,3 Do đó nó không phải là hình phẳng.
Màu đồ thị
Giả sử rằng G = (V, E) là đồ thị không có nhiều cạnh. Màu đỉnh của G là phép gán màu cho các đỉnh của G sao cho các đỉnh liền kề có màu khác nhau. Một đồ thị G là M-Coloring nếu tồn tại một màu của G sử dụng M-Colors.
Tô màu đúng: Một tô màu là thích hợp nếu hai đỉnh liền kề u và v có các màu khác nhau, nếu không thì được gọi là tô màu không đúng.
Ví dụ: Hãy xem xét đồ thị sau và tô màu C = {r, w, b, y}. Tô màu đồ thị đúng cách bằng cách sử dụng tất cả các màu hoặc ít màu hơn.
Biểu đồ được hiển thị trong hình là tối thiểu có 3 màu, do đó x (G) = 3
Giải: Hình cho thấy đồ thị được tô màu đúng với cả bốn màu.
Hình cho thấy biểu đồ được tô màu đúng với ba màu.
Số màu của G: Số màu tối thiểu cần thiết để tạo ra màu thích hợp của đồ thị G được gọi là số màu của G và được ký hiệu là x (G).
Ví dụ: Số sắc độ của Kn là n.
Giải: Một màu của Kn có thể được xây dựng bằng n màu bằng cách gán các màu khác nhau cho mỗi đỉnh. Không có hai đỉnh nào có thể được gán cùng màu, vì mọi hai đỉnh của đồ thị này đều kề nhau. Do đó số màu của Kn = n.
