BÀI TOÁN

Đường đi Euler là gì?

• Một đường đi qua tất cả các đỉnh của đồ thị một lần và chỉ một lần.

• Một đường đi qua tất cả các cạnh của đồ thị nhiều lần.

• Một đường đi qua tất cả các đỉnh của đồ thị nhiều lần.

•  Một đường đi qua tất cả các cạnh của đồ thị một lần và chỉ một lần.

Đường đi Euler có thể tồn tại trong đồ thị vô hướng không liên thông không?

• có

• không

 Điều kiện cần và đủ để một đồ thị có đường đi Euler là gì?

• Đồ thị liên thông và tất cả các đỉnh đều có bậc chẵn

• Đồ thị có ít nhất một cạnh là cạnh cắt.

• Đồ thị có ít nhất một cạnh là cạnh cắt.

• Tất cả các đỉnh của đồ thị đều có bậc chẵn.

Điều gì là đúng khi nói về chu trình Euler và đường đi Euler?

• Mọi chu trình Euler đều là đường đi Euler, nhưng không phải tất cả các đường đi Euler đều là chu trình Euler.

• Mọi đường đi Euler đều là chu trình Euler, nhưng không phải tất cả các chu trình Euler đều là đường đi Euler.

• Chu trình Euler và đường đi Euler là hai khái niệm hoàn toàn không liên quan.

•  Chu trình Euler và đường đi Euler là hai khái niệm giống hệt nhau.

 Đường đi Hamilton là gì?

• Một đường đi qua tất cả các đỉnh của đồ thị một lần và chỉ một lần.

•  Một đường đi qua tất cả các cạnh của đồ thị một lần và chỉ một lần.

•  Một đường đi qua tất cả các đỉnh của đồ thị một lần và chỉ một lần, kết thúc ở đỉnh xuất phát.

• Một đường đi qua tất cả các cạnh của đồ thị một lần và chỉ một lần, kết thúc ở đỉnh xuất phát.

 Định lý Dirac (1952) nói gì ? 

•  Đối với đồ thị vô hướng G có n đỉnh (n ≥ 3), nếu mọi đỉnh của G đều có bậc lớn hơn hoặc bằng n thì G có chu trình Hamilton.

• Đối với đồ thị vô hướng G có n đỉnh (n ≥ 3), nếu mọi đỉnh của G đều có bậc nhỏ hơn hoặc bằng n/2 thì G có chu trình Hamilton.

• Đối với đồ thị vô hướng G có n đỉnh (n ≥ 3), nếu mọi đỉnh của G đều có bậc lớn hơn hoặc bằng n/2 thì G có chu trình Hamilton.

• Đối với đồ thị vô hướng G có n đỉnh (n ≥ 3), nếu mọi đỉnh của G đều có bậc nhỏ hơn hoặc bằng n thì G có chu trình Hamilton.

Nếu một đồ thị vô hướng đơn gồm n đỉnh với n ≥ 3 và mọi đỉnh của G đều có bậc lớn hơn hoặc bằng (n-1)/2 thì: G không có chu trình Hamilton. ĐÚNG/SAI?

• đúng

• sai

 Định lý Ore nói rằng nếu một đồ thị vô hướng đơn gồm n đỉnh với n ≥ 3 và mọi cặp đỉnh không kề nhau của G đều có tổng bậc lớn hơn hoặc bằng n thì: 

• G có thể là đồ thị Hamilton.

• G không phải là đồ thị Hamilton.

• G là đồ thị Hamilton.

• a và c đều đúng

Điều gì đúng khi nói về chu trình hamilton và đường đi hamilton?

•  Đường đi Hamilton và chu trình Hamilton là hai khái niệm giống hệt nhau.

• Mọi chu trình Hamilton đều là đường đi Hamilton, nhưng không phải tất cả các đường đi Hamilton đều là chu trình Hamilton.

• Đường đi Hamilton và chu trình Hamilton là hai khái niệm hoàn toàn không liên quan.

• Mọi đường đi Hamilton đều là chu trình Hamilton, nhưng không phải tất cả các chu trình Hamilton đều là đường đi Hamilton.

Cho đồ thị G như Hình 2.26. Tìm một chu trình Hamilton xuất phát từ đỉnh S của G

• SABCREFDGS.

• SABCREDFGS.

• SGBCREDFAS.

• SABFREDCGS.