-
Thông tin
-
Quiz
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 (BKHN) 53 tài liệu
Đại học Bách Khoa Hà Nội 2.8 K tài liệu
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: Toán rời rạc (BKHN) 53 tài liệu
Trường: Đại học Bách Khoa Hà Nội 2.8 K tài liệu
Thông tin:
Tác giả:

Tài liệu khác của Đại học Bách Khoa Hà Nội
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ẻ.