TAILIEUCHUNG - Giáo trình đồ thị - Nhân của đồ thị

Tham khảo tài liệu 'giáo trình đồ thị - nhân của đồ thị', khoa học tự nhiên, toán học phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả | 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
• đồ thị
• giáo trình đồ thị
• tài liệu về đồ thị
• ứng dụng của đồ thị
• tài liệu về đồ thị
• Lý thuyết đồ thị
• Bài giảng Lý thuyết đồ thị
• Đại cương về đồ thị
• Các mô hình đồ thị
• Thuật ngữ cơ bản của đồ thị
• Đường đi của đồ thị
• Sự liên thông đồ thị
• Đồ thị phẳng
• định lý Kemple
• định lý heawood
• đồ thị vô hướng
• đồ thị Euler
• đồ thị hamiton
• bài giảng đồ thị phẳng
• biểu diễn đồ thị
• bậc của đỉnh trong đồ thị
• đại cương đồ thị
• bài giảng về đồ thị
• Biểu diễn đồ thị trên máy tính
• Sự đẳng cấu của đồ thị
• Phương pháp biểu diễn đồ thị
• Biểu diễn đồ thị bằng ma trận kề
• Đồ thị Hamilton
• Chu trình Hamilton
• Kiểm tra đồ thị Hamilton
• Đơn đồ thị đặc biệt
• Đồ thị bánh xe
• Đồ thị con
• Mô hình đồ thị
• Khái niệm đồ thị
• đồ thị riêng
• sự đẳng hình của đồ thị
• cách biểu diễn đồ thị
• định nghĩa đồ thị
• toán rời rạc
• nguyên lý đồ thị
• tự học đồ thị
• cách vẽ đồ thị
• tô màu đồ thị
• Vẽ đồ thị
• bài toán luồng trên mạng
• tài liệu học đại học
• bài giảng toán học
• toán đồ thị
• đơn đồ thị
• đa đồ thị
• giả đồ thị
• đồ thị có hướng