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.
Giải pháp: Có năm vùng trong biểu đồ trên, tức là r1, r2, r3, r4, r5.
Có bốn vùng hữu hạn trong biểu đồ, tức là, r2, r3, r4, r5.
Chỉ có một vùng hữu hạn, tức là r1
Thuộc tính của đồ thị phẳng:
- Nếu một đồ thị phẳng liên thông G có e cạnh và r vùng thì r ≤ Đồ thị phẳng và không phẳng.
- Nếu một đồ thị phẳng liên thông G có e cạnh, v đỉnh và r vùng thì v-e + r = 2.
- Nếu một đồ thị phẳng liên thông G có e cạnh và v đỉnh thì 3v-e≥6.
- Một đồ thị hoàn chỉnh Kn là một hình phẳng khi và chỉ khi n <5.
- Một đồ thị lưỡng bội hoàn chỉnh Kmn là phẳng khi và chỉ khi m <3 hoặc n> 3.
Ví dụ: Chứng minh rằng đồ thị hoàn chỉnh K4 là hình phẳng.
Lời giải: Đồ thị hoàn chỉnh K4 có 4 đỉnh và 6 cạnh.
Chúng ta biết rằng đối với một đồ thị phẳng liên thông 3v-e≥6. Do đó đối với K4, chúng ta có 3×4-6 = 6 thỏa mãn tính chất (3).
Như vậy K4 là một đồ thị phẳng. Do đó đã được chứng minh.
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.
Các ứng dụng của tô màu đồ thị
Một số ứng dụng của tô màu đồ thị bao gồm:
- Đăng ký phân bổ
- Tô màu bản đồ
- Kiểm tra đồ thị lưỡng cực
- Ấn định tần số vô tuyến điện thoại di động
- Lập bảng thời gian, v.v.
Phát biểu và chứng minh Handshaking Theorem
.
Định lý Bắt tay: Tổng các bậc của tất cả các đỉnh trong đồ thị G bằng hai lần số cạnh trong đồ thị.
Về mặt toán học, nó có thể được phát biểu như sau:
Chứng minh: Gọi G = (V, E) là đồ thị trong đó V = {v1, v2 ,. . . . . . . . . .} là tập các đỉnh và E = {e1, e2. . . . . . . . . .} là tập các cạnh. Chúng ta biết rằng mọi cạnh đều nằm giữa hai đỉnh nên nó cung cấp bậc một cho mỗi đỉnh. Do đó mỗi cạnh đóng góp bậc hai cho đồ thị. Vậy tổng tung độ của tất cả các đỉnh bằng hai lần số cạnh trong G. Do đó:
