tailieunhanh - Giáo trình lý thuyết đồ thị - Bài 5

Nhân của đồ thị Giả sử G = (V, E) là một đồ thị. Định nghĩa : 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, nghĩa là: ∀x ∈ B : B ∩ F(x) = ∅ và ∀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. Từ định nghĩa của nhân, ta suy ra: - Nhân không chứa đỉnh nút. - Nếu F(x). | BÀI 05 . Nhân của đồ thị Giả sử G V E là một đồ thị. Định nghĩa Tập B c 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 nghĩa là Vx G B B n F x 0 và Vy Ể B B n f v 0. Hai điều kiện trên của nhân tương đương với đẳng thức F-1 B V B. Từ định nghĩa của nhân ta suy ra - Nhân không chứa đỉnh nút. - Nếu F x 0 thì x phải thuộc vào một nhân nào đó của đồ thị. Ví dụ Xét các đồ thị sau đây Hình . Đồ thị và có nhân và đồ thị không có nhân Chú ý Nếu g là một hàm Grundy của đồ thị G thì tập hợp B x I g x 0 là một nhân của G. Quả vậy nếu x y đều thuộc B thì g x g y 0 nên x không thể kề với y. Vậy B là tập ổn định trong. Mặt khác nếu x t B thì g x 0. Khi đó với u 0 g x sẽ tồn tại y G F x sao cho g y u 0 . Ta có y G B . Vậy B là tập ổn định ngoài. Định lý 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 Giả sử ngược lại 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 u 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 u a không thể là tập ổn định trong. Suy ra điều vô lý. Định lý được chứng minh xong. Chú ý rằng mệnh đề ngược lại là không đúng. Ví dụ Xét phản ví dụ sau đây. Hình . Tập ổn định trong cực đại không phảI là nhân Tập B a là tập ổn định trong cực đại nhưng không phải là nhân của đồ thị. Nhưng với đồ thị đối xứng thì mệnh đề ngược lại của Định lý là đúng. Định lý 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 V E . Ta chỉ cần chứng minh rằng B là ổn định ngoài. Thật vậy giả sử x t 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 G F x . Suy ra tập B là ổn định ngoài. Định lý được chứng minh xong. 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ả .