Bài giảng Toán - Nhân Của Đồ Thị

3.3. NHÂN CỦA ĐỒ THỊĐịnh nghĩa 3.3: Giả sử G = (V, F) là một đồ thị.Tập B  V được gọi là nhân của đồ thị G nếu nó vừa là tập ổn định trong vừa là tập ổn định ngoài của G: 	1)  x  B : B  F(x) =  và	2)  y  B : B  F(y)  .Hai điều kiện trên của nhân tương đương với đẳng thức: F-1(B) = V \ B. 13.3. NHÂN CỦA ĐỒ THỊ (tiếp)Từ định nghĩa của nhân suy ra: - Nhân không chứa đỉnh nút.- Nếu F(x) =  thì x phải thuộc vào một nhân nào đó của đồ thị. 2VÍ DỤ 3.6Xét các đồ thị sau đây: Hình 3.4. Đồ thị có nhân và đồ thị không có nhân 3142abc3NHÂN VÀ TẬP ỔN ĐỊNH TRONG CỰC ĐẠI Định lý 3.2: Nếu B là nhân của đồ thị G thì B cũng là tập ổn định trong cực đại.Chứng minh:Phản chứng, B không là tập ổn định trong cực đại. Điều này có nghĩa là tồn tại a  B mà B  {a} vẫn là tập ổn định trong. Vì B là nhân nên a sẽ kề với một đỉnh nào đó trong B. Vậy thì B  {a} không thể là tập ổn định trong. Suy ra điều vô lý.  4NHÂN VÀ TẬP ỔN ĐỊNH TRONG CỰC ĐẠI (tiếp)Chú ý: Mệnh đề ngược lại là không đúng Với đồ thị đối xứng thì mệnh đề ngược lại của Định lý 3.2 là đúng. 5VÍ DỤ 3.7Xét phản ví dụ sau đây:Hình 3.5. Tập ổn định trong cực đại không phải là nhânTập B ={a} là tập ổn định trong cực đại nhưng không phải là nhân của đồ thị.abc6NHÂN VÀ TẬP ỔN ĐỊNH TRONG CỰC ĐẠI (tiếp) Định lý 3.3: Trong đồ thị đối xứng không có đỉnh nút, mọi tập ổn định trong cực đại đều là nhân của đồ thị.Chứng minh: 	Giả sử B là tập ổn định trong cực đại của đồ thị G. 	Ta chỉ ra rằng B là ổn định ngoài. 	Thật vậy, giả sử x  B. Theo tính chất cực đại của B thì x phải kề với một đỉnh y nào đó ở trong B. 	Vì đồ thị G đối xứng nên y  F(x). Suy ra tập B là ổn định ngoài. 7NHÂN VÀ TẬP ỔN ĐỊNH TRONG CỰC ĐẠI (tiếp)Chú ý: Điều kiện G không có đỉnh nút là cần thiết vì trong trường hợp ngược lại, đỉnh x không nhất thiết phải kề với tập B.Hệ quả 3.1: Mọi đồ thị xứng không có đỉnh nút luôn có nhân8NHÂN VÀ CHU TRÌNHĐịnh lý 3.4: Mọi đồ thị G không có chu trình luôn có nhân.Chứng minh: 	Theo Định lý 2.1, đồ thị G có hàm Grundy, tập các đỉnh mà tại đó hàm Grundy bằng 0 chính là một nhân của đồ thị.  Câu hỏi: Khi nào đồ thị có chu trình có nhân? 9LÕI CỦA ĐỒ THỊĐịnh nghĩa 3.4: Tập con các đỉnh B được gọi là lõi của đồ thị G = (V, E) nếu:	1)  x, y  B , x  y : không tồn tại đường đi nối x với y.	2) x  B : có tồn tại đường đi từ x đến B.Hình 3.5: Lõi và nhân của một đồ thịabcdefghi10LÕI CỦA ĐỒ THỊ (tiếp)Bổ đề 3.1: Mọi đồ thị đều có lõi Chứng minh: Quy nạp theo số đỉnh n của đồ thị G.n = 1 : đỉnh duy nhất cũng là lõi của đồ thị.(n)  (n+1): Đồ thị G = (V, E) có n+1 đỉnh được xây dựng từ đồ thị G1 = (V1, E1) có n đỉnh thêmđỉnh a và một số cạnh kề a. Thế thì, V = V1  {a}. - Theo giả thiết quy nạp, đồ thị G1 có lõi là B1. 11LÕI CỦA ĐỒ THỊ (tiếp)Chứng minh bổ đề: 	- Nếu có đường đi từ a tới V1 thì sẽ có đường từ a tới B1, do vậy B1 cũng là lõi của G. 	- Ngược lại, giả sử không có đường đi từ a tới V1. Thế thì, không có cạnh đi ra từ a và a sẽ là đỉnh treo. Ký hiệu: B2 = { x x  B1 và không có đường đi từ x tới a }.Ta chứng minh tập B = B2  {a} là lõi của G. 12LÕI CỦA ĐỒ THỊ (tiếp)	Chứng minh bổ đề: Giả sử x, y  B và x  y. Ta chứng minh rằng không có đường nối x với y. - Nếu x và y cùng thuộc B2 thì chúng cùng thuộc B1. Mà B1 là lõi của G1 nên không có đường nối x với y trong G1. Hơn nữa, cũng không thể có đường nối qua đỉnh a vì a là đỉnh treo.13LÕI CỦA ĐỒ THỊ (tiếp)Chứng minh bổ đề:Nếu x = a , y  B2 thì theo định nghĩa của B2 sẽ không có đường đi từ y đến a và cũng không có đường từ a đến y vì a là đỉnh treo.B2B1a Hình 3.7. Xây dựng lõi của đồ thị14LÕI CỦA ĐỒ THỊ (tiếp)Chứng minh bổ đề: Với x  B thì x  a và x  B2.Ta chỉ ra là có đường đi từ x đến B.Giả sử x  B1. Vì x  B2 nên có đường từ x đếna theo định nghĩa của B2.Giả sử x  B1. Vì x  a nên x  V1. Suy ra có đường đi từ x đến y  B1 vì B1 là lõi của G1. Nếu y  B2 thì theo định nghĩa của B2 sẽ có đườngđi từ y đến a. Trong tất cả các trường hợp đều suyra là có đường từ x đến B. 15SỰ TỒN TẠI CỦA NHÂN Định lý 3.5: Mọi đồ thị không có chu trình độ dài lẻ luôn có nhân Phương hướng chứng minh: 	Ta xây dựng ba dãy tập con các đỉnh của đồ thị 	V0, V1, V2,  ; B0, B1, B2,  và C0, C1, C2,  lần lượt như sau: Đặt: V0 = V,Chọn B0 là lõi của V0 và C0 = { x x  V0 \ B0 và có cạnh đi từ x đến B0 }.16SỰ TỒN TẠI CỦA NHÂN (tiếp)Phương hướng chứng minh:Lấy V1 = V0 \ (B0  C0) ; B1 là lõi của V1 và C1 = { x x  V1 \ B1 và có cạnh đi từ x đến B1 }.Tương tự: V2 = V1 \ (B1  C1) C0B0. . .CiBi. . .V0V1ViVkHình 3.8. Cách xây dựng ba dãy tập con17SỰ TỒN TẠI CỦA NHÂN (tiếp)Phương hướng chứng minh:Giả sử đã chọn được Bi là lõi của Vi. Đặt: Ci = { x x  Vi \ Bi và có cạnh đi từ x đến Bi }.Đến một bước nào đó thì Vk \ Bk =  và ta đã vét hếtcác đỉnh của đồ thị. Chọn tập B = B0  B1  B2  ...  Bk. Ta chỉ ra rằngtập B là nhân của đồ thị G. 18NHÂN VÀ HÀM GRUNDYĐịnh lý 3.6: Nếu mỗi đồ thị con của đồ thị G đều có nhân thì G có hàm Grundy.Chứng minh: Xây dựng hai dãy tập con các đỉnh: V0, V1, V2,  vàB0, B1, B2,  lần lượt như sau:V0 = V,Chọn B0 là nhân của G.19NHÂN VÀ HÀM GRUNDY (tiếp)V1 = V0 \ B0B1 là nhân của đồ thị con tạo bởi V1. . . . . . . . .Vi+1 = Vi \ BiBi+1 là nhân của đồ thị con tạo bởi Vi+1.Vì mỗi nhân đều khác rỗng nên đến một bước nào đósẽ vét hết các đỉnh của đồ thị và ta nhận được dãy các nhân: B0, B1,  , Bk.20NHÂN VÀ HÀM GRUNDY (tiếp)Chứng minh định lý:Xây dựng hàm g như sau: với x  Bi , đặt g(x) = i .Ta chứng minh g là hàm Grundy của đồ thị.B0. . .y. . . xBiBkV0V1BiViVjVkHình 3.9. Cách xây dựng dãy các nhân21NHÂN VÀ HÀM GRUNDY (tiếp)Chứng minh định lý:1) Nếu x, y kề nhau thì chúng không thể thuộc cùng một tập Bi vì Bi là nhân, cho nên g(x)  g(y).2) Giả sử có số nguyên i j. 	Hàm Grundy của đồ thị này là: g(x) = x.Đồ thị của trò chơi bốc ba đống que ở trên là đồ thị tổng của ba trò chơi riêng biệt mà ta vừa xét:	 G = G1 + G2 + G3. 35VÍ DỤ 3.10 (tiếp)Hàm Grundy của G là: g((x,y,z)) = g1(x)  g2(y)  g3(z).Nhân của đồ thị là B = { (x,y,z) x y  z = 0 }. Hình trạng (0, 0, 0) là hình trạng kết thúc duy nhất nằm trong nhân. 	Do vậy, có thể áp dụng chiến thuật chơi ở trên.36VÍ DỤ 3.10 (tiếp)Chẳng hạn, với m1 = 6, m2 = 5, m3 = 2.Nếu được đi trước, ta phải bốc ở đống thứ hai 1 que đểdẫn tới đỉnh (6, 4, 2)  B. Sau đó đối thủ bốc thế nàocũng dẫn tới đỉnh nằm ngoài nhân, ta vẫn có thể bốc đểdẫn đến đỉnh nằm trong nhân. 37VÍ DỤ 3.10 (tiếp)	Chẳng hạn, anh ta bốc 3 que ở đống thứ nhất thì ta bốc 3 que ở đống thứ hai và dẫn tới hình trạng (3,1,2)  B. Anh ta lại bốc 3 que ở đống thứ nhất thì ta bốc 1 que ở đống thứ ba để dẫn tới hình trạng (0, 1, 1)  B. Anh ta bốc 1 que ở đống nào thì ta bốc nốt que ở đống còn lại và thắng cuộc. Có thể mở rộng các trò chơi trên thành trò chơi với số đống que tuỳ ý.38