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!

Môn:
Trường:

Đại học Bách Khoa Hà Nội 2.8 K tài liệu

Thông tin:
1 trang 7 tháng trước

Bình luận

Vui lòng đăng nhập hoặc đăng ký để gửi bình luận.

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!

59 30 lượt tải Tải xuống
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ẻ.