TAILIEUCHUNG - BÀI 05: Nhân của đồ thị

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. | BÀI 05 . 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à Vx G B B n F x 0 và Vy e B B n F y o. 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 E 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
• Nhân của đồ thị
• ứng dụng nhân
• lý thuyết trò chơi
• đồ thị đối xứng
• hàm grundy
• đồ thị
• giáo trình đồ thị
• tài liệu về đồ thị
• ứng dụng của đồ thị
• Lý thuyết tổ hợp
• Lý thuyết đồ thị
• Nghịch đảo Mobius
• Bài toán tối ưu trên đồ thị
• Độ liên thông
• Nhân tử của đồ thị
• Tô màu đồ thị
• Lý thuyết ramsey
• Phân tích thuật toán
• Thiết kế thuật toán
• Ngôn ngữ C
• Cách tìm sắc số
• Số ổn định trong
• Số ổn định ngoài
• tập hợp đồ thị đặc biệt
• tập ổn định trong
• tập ổn định ngoài
• nhân của một đồ thị
• bài toán tám quân hậu
• Cẩm nang xuất khẩu sang Nhật Bản
• Xuất khẩu đồ nội thất sang Nhật Bản
• Xuất khẩu đồ gia dụng sang Nhật Bản
• Xuất khẩu vải vóc sang Nhật Bản
• Quy định nhập khẩu của Nhật Bản
• Thị trường hàng hóa Nhật Bản
• Thông tin trách nhiệm xã hội
• Doanh nghiệp thực phẩm và đồ uống
• Doanh nghiệp niêm yết
• Thị trường chứng khoán
• Tỷ suất sinh lời
• báo cáo thực tập
• khóa luận tốt nghiệp
• đồ án marketing
• thị trường tiếp thị
• giải pháp marketing
• quản trị chiến lược
• marketing ngân hàng
• nhân viên bán hàng
• bảo hiểm nhân thọ Thanh Hoá
• Luận văn Thạc sĩ
• Luận văn Thạc sĩ Kế toán
• Báo cáo tài chính
• Mô hình tác động ngẫu nhiên
• Chuẩn mực báo cáo tài chính quốc tế
• Đặc tính sinh học của chủng virus KTY PRRS 01
• Sinh học phân tử của chủng virus KTY PRRS 01
• Hội chứng rối loạn sinh sản và hô hấp ở lợn
• Bệnh tai xanh
• Nhân virus PRRS
• Đồ thị sinh trưởng của virus KTY PRRS 01
• Chủng virus KTY PRRS 01
• văn bản luật
• bất động sản
• văn bản quy phạm pháp luật
• Chỉ thị Số 22 2009 CT UBND
• KIỂM KÊ ĐẤT ĐAI
• XÂY DỰNG BẢN ĐỒ
• HIỆN TRẠNG SỬ DỤNG ĐẤT NĂM 2010
• đồ án tốt nghiệp
• kinh tế thị trường
• lao động
• doanh nghiệp
• tài chính
• thị trường cạnh tranh
• chuyên ngành marketing
• kỹ năng quản trị
• quản trị nhân sự
• Trí Tuệ Nhân Tạo
• Thuật Toán Tìm Kiếm Sâu Lặp
• đồ thị không gian trạng thái
• mảng father
• mã giả của thuật toán
• nguồn nhân lực
• hiện đại hóa
• công nghiệp hóa
• kinh tế thế giới
• nhà đầu tư cá nhân
• hị trường chứng khoán Việt Nam
• luận văn
• công nghệ môi trường
• khoa học công nghệ
• Lạm dụng đồ uống có cồn
• Phòng chống tác hại của rượu bia
• Dịch tễ học lâm sàng lạm dụng rượu
• Bệnh nhân loạn thần do rượu
• Sức khỏe cộng đồng
• Khóa luận tốt nghiệp Quản trị kinh doanh
• Quản trị kinh doanh
• Hành vi người tiêu dùng
• Quyết định mua của người tiêu dùng
• Ứng dụng đặt thức ăn
• Giao dịch trực tuyến
• Thị trường giao đồ ăn
• Nâng cao uy tín của doanh nghiệp
• Dịch vụ thương mại điện tử
• Kinh tế lượng
• Bài giảng Kinh tế lượng
• Bước phân tích kinh tế lượng
• Hàm tiêu dùng Keynes
• Ước lượng qua đồ thị
• Vai trò của kinh tế lượng
• Bài giảng Kinh tế học đại cương
• Công cụ điều tiết vĩ mô
• Chỉ tiêu đo lường tổng sản lượng quốc gia
• Đầu tư tư nhân
• Thu nhập khả dụng
• Chi tiêu của chính phủ
• Sơ đồ chu chuyển kinh tế
• Phân biệt GDP và GNP
• Đề kiểm tra giữa học kì 2 Toán 12
• Đề kiểm tra môn Toán lớp 12
• Đề thi Toán 12
• Bài tập Toán 12
• Tìm tiệm cận ngang của đồ thị
• Đề thi thử tốt nghiệp THPT Quốc gia
• Đề thi thử tốt nghiệp THPT năm 2021
• Đề thi thử tốt nghiệp THPT môn Toán
• Ôn thi tốt nghiệp THPT năm 2021 môn Toán
• Giao điểm của đồ thị hàm số
• Cấp số nhân với công bội
• Năng suất cấp độ doanh nghiệp
• Kỹ thuật bán tham số
• Doanh nghiệp FDI
• Thị trường tài chính
• Mô hình hội tụ không điều kiện