TAILIEUCHUNG - 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à

• Toán học
• Lý thuyết đồ thị và ứng dụng
• Bậc của đỉnh đồ thị
• Đồ thị liên thông
• Đồ thị màu
• Số ổn định trong
• Số ổn định ngoài
• Hội thảo khoa học Toán học
• Lý thuyết đồ thị
• Đồ thị vô hướng
• Đồ thị có hướng
• Đồ thị đơn vô hướng hữu hạn đỉnh
• Đồ thị lưỡng phân
• Luận văn Thạc sĩ
• Luận văn Thạc sĩ Toán học
• Ứng dụng lý thuyết đồ thị
• Giải toán sơ cấp
• Phương pháp toán sơ cấp
• kỹ thuật lý thuyết đầu tư
• ứng dụng trong đầu tư
• thị trường chứng khoán Việt Nam
• kỹ thuật chứng khoán
• lý thuyết ứng dụng trong đầu tư
• đồ thị đầu tư chứng khoán
• Bài toán tô màu đồ thị
• Tóm tắt luận văn thạc sĩ khoa học
• Luận văn thạc sĩ khoa học
• Ứng dụng bài toán tô màu đô thị
• Cây và một số ứng dụng
• Khái niệm cây
• tìm cây bao trùm
• Thuật toán đồ thị
• Ứng dụng đồ thị
• Cấu trúc dữ liệu
• Bài giảng giải thuật
• Lý thuyết cấu trúc dữ liệu
• Toán rời rạc
• Khoa học tự nhiên
• giải toán phổ thông
• luận văn
• điều khiển tối ưu
• giao thông vận tải
• mạng viễn thông
• đường đi sơ cấp
• chu trình sơ cấp
• Khoa học máy tính
• hệ thống điện
• kỹ thuật điện
• tóm tắt luận văn
• Thuật toán LCA
• ứng dụng thuật toán LCA
• Thuật toán RMQ
• Ứng dụng thuật toán RMQ
• Lý thuyết đồ thị và mạng máy tính
• Bài toán LCA
• thuật toán tô màu đô thị
• xếp lịch thi
• chuyên đề toán học
• kiến thức toán
• Quản lý bưu chính
• Ebook Quản lý bưu chính
• Bảo dưỡng thiết bị bưu chính
• Hệ thống thông tin bưu chính
• Bưu chính điện tử
• cây đồ thị
• tài liệu toán
• ôn thi toán
• lý thuyết toán cơ bản
• cây đồ thị bao trùm
• Luận văn Thạc sĩ Khoa học Máy tính
• Thuật toán Dijkstra Fibonacci heap
• Tìm đường đi tối ưu trên đồ thị
• Tóm tắt luận văn Thạc sĩ
• Đường đi trong mê cung
• ứng dụng đường đi trong mê cung
• Kỹ thuật phễu
• Kỹ thuật cây phễu
• Bài toán đường đi ngắn nhất
• Toán ứng dụng
• đại số 12
• tài liệu đại số 12
• giáo án đại số 12
• bải giảng đại số 12
• lý thuyết đại số 12
• giải tích 12
• tài liệu giải tích 12
• giáo án giải tích 12
• bải giảng giải tích 12
• lý thuyết giải tích 12
• Bài toán đa thức
• Tìm đường ngắn nhất
• Bài toán ghép cặp
• Công tác tuyển sinh
• Thuật toán tìm core
• Phân tích mạng xã hội