Euler x Hamilton

Đường đi Hamilton là:

• Một đường đi sơ cấp từ đỉnh A đến đỉnh B và qua mọi đỉnh của đồ thị G

• Một đường đi sơ cấp từ đỉnh A đến đỉnh B và qua 1 đỉnh của đồ thị G

• Một đường đi sơ cấp từ đỉnh A đến đỉnh B và qua 2 đỉnh của đồ thị G

• Một đường đi sơ cấp từ đỉnh A đến đỉnh B và không qua đỉnh nào của đồ thị G

Chu trình Hamilton của G là

• Một chu trình sơ cấp không chứa đỉnh của G

• Một chu trình sơ cấp chứa mọi đỉnh của G

• Một chu trình sơ cấp chứa 1 đỉnh của G

• Một chu trình sơ cấp chứa 2 đỉnh của G

Nếu G có n đỉnh (n ≥ 2) thì có bậc

• Lớn hơn (n-1)/2

• Nhỏ hơn (n+1)/2

• Nhỏ hơn (n-1)/2

• Nhỏ hơn (n-2)/2

Nếu G có n đỉnh (n ≥ 2) thì có bậc

• Lớn hơn (n-1)/2

• Nhỏ hơn (n+1)/2

• Nhỏ hơn (n-1)/2

• Nhỏ hơn (n-2)/2

Chu trình Hamilton từ S đến R nào đúng?

• SABCDEGR

• SABCDER

• SRABCDE

• SEBCADR

Đồ thị trên có chu trình Hamilton không?

• Có

• Không

Tìm chu trình Hamilton từ S của G

• SACHREFDB

• SACHERFDB

• SCAREHFDB

• SACHERFBD

Nếu G có n đỉnh (n ≥ 3), để có một chu trình Hamilton thì mỗi đỉnh phải có bậc:

• Lớn hơn n/2

• Không nhỏ hơn n/2

• Không nhỏ hơn n/3

• Bằng n/2

Đường đi Euler là

• Đường đi đơn giản từ đỉnh A đến đỉnh B và chứa mọi cạnh của G

• Đường đi đơn giản từ đỉnh A đến đỉnh B và không chứa cạnh của G

• Đường đi đơn giản từ đỉnh A đến đỉnh B và chứa 1 cạnh của G

• Đường đi đơn giản từ đỉnh A đến đỉnh B và chứa 2 cạnh của G

Một đa đồ thị G có 1 chu trình Euler khi và chỉ khi G liên thông và mọi đỉnh của G đều có bậc lẻ

• Đúng

• Sai