Kinh doanh - Marketing
Kinh tế quản lý
Biểu mẫu - Văn bản
Tài chính - Ngân hàng
Công nghệ thông tin
Tiếng anh ngoại ngữ
Kĩ thuật công nghệ
Khoa học tự nhiên
Khoa học xã hội
Văn hóa nghệ thuật
Sức khỏe - Y tế
Văn bản luật
Nông Lâm Ngư
Kỹ năng mềm
Luận văn - Báo cáo
Giải trí - Thư giãn
Tài liệu phổ thông
Văn mẫu
Giới thiệu
Đăng ký
Đăng nhập
Tìm
Danh mục
Kinh doanh - Marketing
Kinh tế quản lý
Biểu mẫu - Văn bản
Tài chính - Ngân hàng
Công nghệ thông tin
Tiếng anh ngoại ngữ
Kĩ thuật công nghệ
Khoa học tự nhiên
Khoa học xã hội
Văn hóa nghệ thuật
Y tế sức khỏe
Văn bản luật
Nông lâm ngư
Kĩ năng mềm
Luận văn - Báo cáo
Giải trí - Thư giãn
Tài liệu phổ thông
Văn mẫu
Thông tin
Điều khoản sử dụng
Quy định bảo mật
Quy chế hoạt động
Chính sách bản quyền
Giới thiệu
Đăng ký
Đăng nhập
0
Trang chủ
Khoa Học Tự Nhiên
Toán học
Giáo trình đồ thị - Nhân của đồ thị
Đang chuẩn bị liên kết để tải về tài liệu:
Giáo trình đồ thị - Nhân của đồ thị
Yến Trâm
95
8
pdf
Đang chuẩn bị nút TẢI XUỐNG, xin hãy chờ
Tải xuống
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 3.3. Nhân của đồ thị Giả sử G V E là một đồ thị. Định nghĩa 3.8 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ụ 3.9 Xét các đồ thị sau đây Hình 3.4. Đồ 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ý 3.4 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ụ 3.10 Xé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â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ý 3.4 là đúng. Định lý 3.5 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ả 3.6 .
TÀI LIỆU LIÊN QUAN
Đồ án: Quy hoạch giao thông tĩnh khu đô thị Nhân Chính
Giáo trình đồ thị - Nhân của đồ thị
Giáo trình Kỹ thuật chung về máy thi công (Nghề Sửa chữa máy thi công xây dựng - Trình độ Cao đẳng) - CĐ GTVT Trung ương I
Thủ tục cấp Giấy phép xây dựng công trình cấp đặc biệt, cấp I, cấp II; công trình tôn giáo; công trình di tích lịch sử - văn hoá; công trình tượng đài, quảng cáo, tranh hoành tráng; những công trình trên các tuyến, trục đường phố chính trong đô thị; công trình thuộc dự án có vốn đầu tư trực tiếp nước ngoài; công trình thuộc dự án và các công trình khác do UBND cấp tỉnh quy định
Giáo trình Kỹ thuật chung về máy thi công xây dựng (Nghề Sửa chữa máy thi công xây dựng – Trình độ trung cấp) – CĐ GTVT Trung ương I
Báo cáo khoa học: "PHÂN TíCH CáC NGUYÊN NHÂN DẫN ĐếN ùN TắC Và TAI NạN GIAO THÔNG DO XE BUýT TạI CáC ĐÔ THị VIệT NAM Và Đề XUấT GIảI PHáP KHắC PHụC"
GIAO THÔNG VÀ MÔI TRƯỜNG
Báo cáo khoa học: "GIAO THÔNG CÔNG CỘNG: VAI TRÒ VÀ SỰ TƯƠNG TÁC VỚI GIAO THÔNG CÁ NHÂN TRONG HỆ THỐNG GIAO THÔNG ĐÔ THỊ THÀNH PHỐ HỒ CHÍ MINH"
Giáo trình Chuẩn bị làm việc (Nghề Sửa chữa máy thi công xây dựng – Trình độ trung cấp) – CĐ GTVT Trung ương I
Xây dựng tiêu chuẩn đánh giá trình độ sức mạnh tốc độ đòn chân của nam vận động viên Muay lứa tuổi 17-18, Trung tâm Huấn luyện và thi đấu thể thao Công an nhân dân
crossorigin="anonymous">
Đã phát hiện trình chặn quảng cáo AdBlock
Trang web này phụ thuộc vào doanh thu từ số lần hiển thị quảng cáo để tồn tại. Vui lòng tắt trình chặn quảng cáo của bạn hoặc tạm dừng tính năng chặn quảng cáo cho trang web này.