Đang chuẩn bị liên kết để tải về tài liệu:
Giáo trình lý thuyết đồ thị - Bài 4

Các tập hợp đặc biệt trên đồ thị Trong chương này chúng ta sẽ nghiên cứu một số tập hợp đặc biệt các đỉnh trên đồ thị. Đó là các tập ổn định trong, tập ổn định ngoài và nhân của một đồ thị. 3.1. Tập ổn định trong Giả sử G = (V, E) là một đồ thị. Định nghĩa 3.1: Tập B ⊆ V được gọi là tập ổn định trong của đồ thị G nếu: ∀ x ∈ B : B ∩ F(x) = ∅. Từ định nghĩa trên ta thấy rằng, trong một tập ổn định. | BÀI 04 Các tập hợp đặc biệt trên đồ thị Trong chương này chúng ta sẽ nghiên cứu một số tập hợp đặc biệt các đỉnh trên đồ thị. Đó là các tập ổn định trong tập ổn định ngoài và nhân của một đồ thị. 3.1. Tập ổn định trong Giả sử G V E là một đồ thị. Định nghĩa 3.1 Tập B c V được gọi là tập ổn định trong của đồ thị G nếu V x G B B n F X 0. Từ định nghĩa trên ta thấy rằng trong một tập ổn định trong không có hai đỉnh nào kề nhau. Hơn nữa nếu tập B ổn định trong thì tập con B c B cũng là tập ổn định trong. Khái niệm ổn định trong không phụ thuộc vào hướng các cạnh của đồ thị. Ví dụ 3.2 Gauss - Bài toán tám quân hậu. Hãy đặt 8 quân hậu vào các ô của một bàn cờ vua sao cho chúng không ăn được lẫn nhau. Để giải quyết bài toán này ta xây dựng đồ thị vô hướng biểu diễn bàn cờ vua như sau 64 ô của bàn cờ là 64 đỉnh của đồ thị hai đỉnh x và y có cạnh nối với nhau nếu đó là hai ô mà khi đặt hai quân hậu vào chúng có thể ăn lẫn nhau. Các ô cần tìm để đặt các quân hậu chính là một tập ổn định trong gồm 8 đỉnh. Bài toán trên có 92 nghiệm suy ra từ 12 tập ổn định trong khác nhau là A7 B2 C6 D3 E1 F4 G8 H5 A3 B5 C8 D4 E1 F7 G2 H6 A1 B6 C8 D3 E7 F4 G2 H5 A5 B1 C4 D6 E8 F2 G7 H3 A6 B1 C5 D2 E8 F3 G7 H4 A4 B6 C1 D5 E2 F8 G3 H7 A5 B7 C2 D6 E3 F1 G8 H4 A4 B2 C7 D5 E1 F8 G6 H3 A5 B8 C4 D1 E7 F2 G6 H3 A5 B7 C2 D6 E3 F1 G4 H8 A4 B8 C1 D5 E7 F2 G6 H3 A3 B5 C2 D8 E1 F7 G4 H6 Ví dụ 3.3 C.E. Shanton - Bài toán về dung lượng thông tin. Giả sử một máy phát có thể truyền đi 5 tín hiệu a b c d e. ở máy thu mỗi tín hiệu có thể cho hai cách hiểu khác nhau như sau a - p q b - q r c - r s d - s t e - t p Hỏi số các tín hiệu nhiều nhất có thể sử dụng để máy thu không bị nhầm lẫn là bao nhiêu Ta xây dựng một đồ thị vô hướng gồm 5 đỉnh a b c d e. Hai đỉnh là kề nhau nếu chúng biểu thị hai tín hiệu có thể bị nhầm lẫn nhau ở máy thu. Hình 3.1. Sự nhầm lẫn của các tín hiệu và đồ thị biểu diễn Khi đó tập các tín hiệu cần chọn là một trong các tập ổn định trong dưới đây a c a d b d b e c e . Tập con các đỉnh B