TAILIEUCHUNG - 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ả .

• Toán học
• Chu trình Hamilton
• thuật toán
• đồ thị
• ứng dụng cây
• hàm trên đồ thị
• Lý thuyết đồ thị
• Đường đi Hamilton
• Đồ thị Hamilton
• Định nghĩa về chu trình Hamilton
• Định nghĩa về đường đi Hamilton
• Đường Hamilton
• bài toán mã đi tuần
• chu trình vô hướng hamilton
• Luận án Tiến sĩ Toán học
• Luận án Tiến sĩ
• Cơ sở toán học cho tin học
• Thuật toán đa thức xác định chu trình Hamilton
• Bài giảng Lý thuyết đồ thị
• Đồ thị Euler
• Kiểm tra đồ thị Hamilton
• Bài toán người du lịch
• Bài toán tối ưu tổ hợp
• Đường Hamilton
• Thuật toán nhánh cận giải TSP
• Bài toán người du lịch và thuật toán nhánh cận
• Bài toán tối ưu liên quan đến đường Hamilton
• Đồ thị tách cực
• Đồ thị tách cực phi Hamilton tối đại
• Bậc cực tiểu
• Chu trình euler
• thuật toán tìm chu trình
• đồ thị liên thông
• Bài toán lý thuyết đồ thị
• Bài toán luông
• toán rời rạc
• bài tập học phần
• Đường đi đồ thị
• Đồ thị phẳng
• Bài toán tô màu đồ thị
• Tài liệu Thực hành
• Đồ thị Chu trình
• Lý thuyết đồ thị chu trình
• Đường đi Euler
• Đồ thị ơ2= N
• Đồ thị đơn
• Bài toán HC
• Thuật toán đa thức
• Xây dựng thuật toán đa thức
• Đồ thị 2 phần
• Đồ thị đầy đủ
• Đồ thị rỗng
• tài liệu toán học
• phép toán hedetniemi
• bài giảng toán học
• các bài toán về đường đi
• Bài giảng Toán rời rạc
• Thuật toán Dijkstra
• giáo trình đồ thị
• tài liệu về đồ thị
• ứng dụng của đồ thị
• Đường đi trên đồ thị
• Bài toán đường đi tốt nhất
• Bài giảng Cấu trúc rời rạc
• Cấu trúc rời rạc
• Chu trình và đường đi Euler
• Chu trình và đường đi Hamilton