Bài tập Toán rời rạc - Phần: Đồ thị Hamilton
Toán rời rạc: Đồ thị Hamilton
Bài tập 11
1. Với những giá trị nào của r thì đồ thị hai phần đầy đủ Kr,r là Hamilton?
2. Với mọi n > 1, hãy chứng minh rằng Kn,n có (n − 1)!n!/2 chu trình Hamilton.
3. Chứng minh rằng đồ thị G là nửa Hamilton chỉ nếu với mọi tập đỉnh S, số thành phần
liên thông của G − S nhiều nhất là |S| + 1.
4. Đồ thị Gro¨tzsch sau đây có là Hamilton?
5. Chứng minh rằng không tồn tại chu trình cho con mã đi hết bàn cờ 4 × n.
Gợi ý:Tìm tập đỉnh thích hợp vi phạm điều kiện cần để đồ thị là Hamilton.
6. Đồ thị sau đây có chu trình Hamilton không?
7. Giả sử G = (V, E) là đồ thị Peterson.
a. Chứng minh rằng G là đồ thị nửa Hamilton, nhưng không là Hamilton.
b. Chứng minh rằng với mọi v ∈ V, đồ thị G − v là đồ thị Hamilton.
8. Chứng minh rằng đồ thị hai phần với một số lẻ đỉnh không là đồ thị Hamilton.
9. Chứng minh rằng đồ thị đầy đủ Kn có thể phân rã thành các chu trình Hamilton nếu và
chỉ nếu n lẻ.
1 trang
18300
Free
Bạn đang xem tài liệu "Bài tập Toán rời rạc - Phần: Đồ thị Hamilton", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- bai_tap_toan_roi_rac_phan_do_thi_hamilton.pdf
