Bài học cùng chủ đề
Đường đi Euler và đường đi Hamilton SVIP
Một đồ thị có chu trình Euler khi nào?
Một đường đi của đồ thị là đường đi Hamilton nếu
Đồ thị nào dưới đây có không có chu trình Euler?
Chu trình Euler của đồ thị dưới đây là
Cho đồ thị có hình vẽ dưới đây:
| a) Đồ thị có cạnh. |
|
| b) Đỉnh có bậc là . |
|
| c) Một đường đi từ đỉnh đến đỉnh là . |
|
| d) Đồ thị có đường đi Euler. |
|
Những đồ thị nào dưới đây có đường đi Hamilton?
Có thành phố du lịch , , , , và các con đường nối các thành phố này như. Đường đi nào dưới đây đi tham quan cả thành phố đó, mà không cần đến địa điểm nào quá một lần?
Cho đồ thị có hình vẽ dưới đây:
Chu trình Hamilton xuất phát từ đỉnh của là
Trả lời: SA
Thành phố Königsberg thuộc Phổ (nay là Kaliningrad thuộc Nga) có bảy cây cầu nối bốn vùng đất được chia bởi các nhánh sông Pregel như hình dưới:
| a) Từ vùng đất đến thẳng vùng đất có hai cách. |
|
| b) Không có con đường nào đi từ vùng đất đến vùng đất mà qua vùng đất . |
|
| c) Có thể đi từ vùng đất đến vùng đất đi qua cả vùng đất , và chỉ đi qua đúng một lần. |
|
| d) Không thể nào đi dạo qua khắp các cây cầu của thành phố Königsberg mà mỗi cầu chỉ đi qua một lần. |
|
Một chu trình Hamilton của đồ thị có hình vẽ dưới đây là
Cho đồ thị có hình vẽ như hình dưới đây:
| a) Bậc của đỉnh bằng . |
|
| b) Đồ thị có đường đi Euler. |
|
| c) Đồ thị có chu trình Hamilton. |
|
| d) Nếu nối với thì đồ thị đã cho có chu trình Euler. |
|
Cho các đồ thị có hình vẽ sau:
| a) Có đồ thị có chu trình Euler. |
|
| b) Đồ thị của hình không có chu trình Hamilton. |
|
| c) Một đường đi Hamilton của đồ thị hình là . |
|
| d) Đồ thị hình vừa có chu trình Euler, vừa có chu trình Hamilton. |
|
