Bài tập 11 Toán rời rạc: Đồ thị Hamilton thầy Trần Vĩnh Đức | Trường Đại học Bách khoa Hà Nội

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ầnliên thông của G − S nhiều nhất là |S| + 1. Toán rời rạc: Đồ thị Hamilton Bài tập 11 thầy Trần Vĩnh Đức | Trường Đại học Bách khoa Hà Nội. Tài liệu được sưu tầm, giúp bạn ôn tập và đạt kết quả cao. Mời bạn đọc đón xem!

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 đủ K
r,r
Hamilton?
2. Với mọi n > 1, hãy chứng minh rằng K
n,n
(n 1)!n!/2 chu trình Hamilton.
3. Chứng minh rằng đồ thị G 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 |S| + 1.
4. Đồ thị Gr
¨
otzsch sau đây Hamilton?
5. Chứng minh rằng không tồn tại chu trình cho con đ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ị Hamilton.
6. Đồ thị sau đây chu trình Hamilton không?
7. Giả sử G = (V, E) đồ thị Peterson.
a. Chứng minh rằng G đồ thị nửa Hamilton, nhưng không Hamilton.
b. Chứng minh rằng với mọi v V , đồ thị G v đồ thị Hamilton.
8. Chứng minh rằng đồ thị hai phần với một số lẻ đỉnh không đồ thị Hamilton.
9. Chứng minh rằng đồ thị đầy đủ K
n
thể phân thành các chu trình Hamilton nếu
chỉ nếu n lẻ.
| 1/1

Preview text:

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 đủ K là Hamilton? r,r
2. Với mọi n > 1, hãy chứng minh rằng K có ( n,n
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ị Gr¨
otzsch 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 đủ K có thể phân rã thành các chu trình Hamilton nếu và n chỉ nếu n lẻ.