tailieunhanh - Ebook Lý thuyết đồ thị và ứng dụng: Phần 2 - Đặng Huy Ruận

Phần 2 Ebook Lý thuyết đồ thị và ứng dụng do Đặng Huy Ruận biên soạn gồm nội dung chương 9 đến chương 18 của tài liệu và phần phụ lục. Nội dung phần này trình bày về: Nhân của đồ thị, trò chơi trên đồ thị, đồ thị Eulere, mạng vận tải,. Mời bạn tham khảo nội dung 2 phần tài liệu. | CHƯƠNG 9 NHÂN CỦA ĐỒ THỈ 1. ĐỊNH NGHĨA Giả sử có đồ thị G X U . Tập hợp s cX được gọi là nhân của đồ thị G nếu nó vừa là tập ổn định trong lại vììa là tập ổn định ngoài. Do s là tập ổn định trong nên nó không chứa khuyên. Mặt khác s ổn định ngoài nên nó phải chứa tất cả các đình biệt lập và các đỉnh không có cung đi ra. Ví dụ . Đồ thị hình có hai nhân là A A-J và IAb AJ. Còn đồ thị ở hình không có nhân vì các tập ổn định trong chỉ gồm 1 đỉnh còn các tập ổn định ngoài phải gồm ít nhất 2 đỉnh. 2. TÍNH CHAT điồu kiộn đổ đổ Ihị không có nhan Đinh lý 9. Ị Nếu đồ thị G Xf ư có số Ổn định trong nhô hơn sô ổn định ngoài thì nó không có nhân. 65 Chứng minh Giả sử trong đồ thị G X U có a G 0 G 1 nhitng lại có nhàn và s là một trong những nhân cùa đồ thị G. Khi đó theo định nghĩa a G max a aeH G S min Ịb Be .7ịG ỉ G 2 So sánh 1 và 2 đi tới mâu thuẫn nên G không thể có nhân. Định lý được chứng minh. Định lý Nếu đồ thị G X U có hàm Grundy g x thì tập hợp s x eX I g x 0 là nhân cùa đồ thị G. Chứng minh 1 tóc y e s g x g y 0 nên X y không thể kề nhau. Do đó s là tập ổn định trong. 2 Vz e X - S . Khí đó g z 0 nên tồn tại y. để hoặc từ z sang y có cung hoặc z. y có cạnh nối vói nhau. Do đó g y 0 tức y eS. Bởi vậy s là tập ổn định ngoài. Định lý Nếu s là nhân của đồ thị G X U thì nó cũng là tập ổn định trong cực đại. Chứng minh Giả sử s là nhân của đồ thị và Vxe X - S . Xét 1S vjfx . Vì s là nhân và x s . nên HyeS để hoặc được nôi bằng một cạnh hoặc từ X sang y có cung. Bỏi vậy s u IxỊ không ổn định trong nên s ổn định trong cực đại. Định lý Trong đồ thị vô hướng không có khuyên mọi tập ổn định trong cực đại đều là nhân. Chting minh Giả srt B là một tập ổn định trong cite đại của đồ thị vô hướng G - X E . Khi đó Vxe X - B đều 3 yeB để X y có cạnh nối với nhau nên B đồng thời là tập ổn định ngoài. Do đó B là nhân của đồ thị G. 66 Giả sử có đồ thị G X E và AclX. Dùng D A để ký hiện tập đỉnh mà mỗi đỉnh này có cạnh nối với ít nhất một đỉnh thuộc A. Còn D A là