Báo cáo tài liệu vi phạm
Giới thiệu
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
THỊ TRƯỜNG NGÀNH HÀNG
NÔNG NGHIỆP, THỰC PHẨM
Gạo
Rau hoa quả
Nông sản khác
Sữa và sản phẩm
Thịt và sản phẩm
Dầu thực vật
Thủy sản
Thức ăn chăn nuôi, vật tư nông nghiệp
CÔNG NGHIỆP
Dệt may
Dược phẩm, Thiết bị y tế
Máy móc, thiết bị, phụ tùng
Nhựa - Hóa chất
Phân bón
Sản phẩm gỗ, Hàng thủ công mỹ nghệ
Sắt, thép
Ô tô và linh kiện
Xăng dầu
DỊCH VỤ
Logistics
Tài chính-Ngân hàng
NGHIÊN CỨU THỊ TRƯỜNG
Hoa Kỳ
Nhật Bản
Trung Quốc
Hàn Quốc
Châu Âu
ASEAN
BẢN TIN
Bản tin Thị trường hàng ngày
Bản tin Thị trường và dự báo tháng
Bản tin Thị trường giá cả vật tư
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
NGÀNH HÀNG
NÔNG NGHIỆP, THỰC PHẨM
Gạo
Rau hoa quả
Nông sản khác
Sữa và sản phẩm
Thịt và sản phẩm
Dầu thực vật
Thủy sản
Thức ăn chăn nuôi, vật tư nông nghiệp
CÔNG NGHIỆP
Dệt may
Dược phẩm, Thiết bị y tế
Máy móc, thiết bị, phụ tùng
Nhựa - Hóa chất
Phân bón
Sản phẩm gỗ, Hàng thủ công mỹ nghệ
Sắt, thép
Ô tô và linh kiện
Xăng dầu
DỊCH VỤ
Logistics
Tài chính-Ngân hàng
NGHIÊN CỨU THỊ TRƯỜNG
Hoa Kỳ
Nhật Bản
Trung Quốc
Hàn Quốc
Châu Âu
ASEAN
BẢN TIN
Bản tin Thị trường hàng ngày
Bản tin Thị trường và dự báo tháng
Bản tin Thị trường giá cả vật tư
Thông tin
Tài liệu Xanh là gì
Điều khoản sử dụng
Chính sách bảo mật
0
Trang chủ
Khoa Học Tự Nhiên
Toán học
GIÁO TRÌNH TOÁN RỜI RẠC - CHƯƠNG IVĐỒ THỊ EULER VÀ ĐỒ THỊ HAMILTON_3
Đang chuẩn bị liên kết để tải về tài liệu:
GIÁO TRÌNH TOÁN RỜI RẠC - CHƯƠNG IVĐỒ THỊ EULER VÀ ĐỒ THỊ HAMILTON_3
Tuyết Hoa
93
6
pdf
Không đóng trình duyệt đến khi xuất hiện nút TẢI XUỐNG
Tải xuống
4.2.5. Định lý (Ore, 1960): Nếu G là một đơn đồ thị có n đỉnh và bất kỳ hai đỉnh nào không kề nhau cũng có tổng số bậc không nhỏ hơn n thì G là một đồ thị Hamilton. | CHƯƠNG IV ĐÒ THỊ EULER VÀ ĐÒ THỊ HAMILTON 4.2.5. Định lý Ore 1960 Nếu G là một đơn đồ thị có n đỉnh và bất kỳ hai đỉnh nào không kề nhau cũng có tổng số bậc không nhỏ hơn n thì G là một đồ thị Hamilton. 4.2.6. Định lý Nếu G là đồ thị phân đôi với hai tập đỉnh là V1 V2 có số đỉnh cùng bằng n n 2 và bậc của mỗi đỉnh lớn hơn n thì G là một đồ thị Hamilton. Đồ thị G này có 5 đỉnh bậc 4 và 2 đỉnh bậc 2 kề nhau nên tổng số bậc của hai đỉnh không kề nhau bất kỳ bằng 7 hoặc 8 nên theo Định lý 4.2.5 G là đồ thị Hamilton. Đồ thị G này có 8 đỉnh đỉnh nào cũng có bậc 4 nên theo Định lý 4.2.3 G là đồ thị Hamilton. Đồ thị phân đôi này có bậc của mỗi đỉnh bằng 2 hoặc 3 3 2 nên theo Định lý 4.2.6 nó là đồ thị Hamilton. 4.2.7. Bài toán sắp xếp chỗ ngồi 54 Có n đại biểu từ n nước đến dự hội nghị quốc tế. Mỗi ngày họp một lần ngồi quanh một bàn tròn. Hỏi phải bố trí bao nhiêu ngày và bố trí như thế nào sao cho trong mỗi ngày mỗi người có hai người kế bên là bạn mới. Lưu ý rằng n người đều muốn làm quen với nhau. Xét đồ thị gồm n đỉnh mỗi đỉnh ứng với mỗi người dự hội nghị hai đỉnh kề nhau khi hai đại biểu tương ứng muốn làm quen với nhau. Như vậy ta có đồ thị đầy đủ Kn. Đồ thị này là Hamilton và rõ ràng mỗi chu trình Hamilton là một cách sắp xếp như yêu cầu của bài toán. Bái toán trở thành tìm các chu trình Hamilton phân biệt của đồ thị đầy đủ Kn hai chu trình Hamilton gọi là phân biệt nếu chúng không có cạnh chung . Định lý Đồ thị đầy đủ Kn với n lẻ và n 3 có đúng nỹ1 chu trình Hamilton phân biệt. Chứng minh Kn có n n 1 cạnh và mỗi chu trình Hamilton có n cạnh nên số chu trình Hamilton phân biệt nhiều nhất là ny1. Giả sử các đỉnh của Kn là 1 2 . n. Đặt đỉnh 1 tại tâm của một đường tròn và các đỉnh 2 . n đặt cách đều nhau trên đường tròn mỗi cung là 3600 n-1 sao cho đỉnh lẻ nằm ở nửa đường tròn trên và đỉnh chẵn nằm ở nửa đường tròn dưới. Ta có ngay chu trình Hamilton đầu tiên là 1 2 55 . n 1. Các đỉnh được giữ cố định xoay khung theo chiều kim đồng hồ với các góc quay 3600 2 3600 3
TÀI LIỆU LIÊN QUAN
Giáo trình Toán rời rạc - Chương 6 Lý thuyết đồ thị - Cây
Giáo trình Toán rời rạc - Chương 1 Cơ sở Logic
Giáo trình Toán rời rạc - Chương 2 Phép đếm
Giáo trình Toán rời rạc - Chương 3 Quan hệ
Giáo trình Toán rời rạc - Chương 4 Hàm Bool
Giáo trình Toán rời rạc - Chương 5 Đồ thị
GIÁO TRINH TOÁN RỜI RẠC - CHƯƠNG II BÀI TOÁN ĐẾM_3
GIÁO TRINH TOÁN RỜI RẠC - CHƯƠNG II BÀI TOÁN ĐẾM_4
GIÁO TRINH TOÁN RỜI RẠC - CHƯƠNG I: THUẬT TOÁN_1
GIÁO TRINH TOÁN RỜI RẠC - CHƯƠNG I: THUẬT TOÁN_2
Đã 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.