Bài tập Toán rời rạc - Bài 11

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ẻ.