JavaScript is required

Chu trình đơn trên đồ thị G là:

A.

Đường đi đơn có đỉnh đầu và đỉnh cuối trùng nhau.

B.

Đường đi có hướng với đỉnh đầu và đỉnh cuối trùng nhau.

C.

Đường đi đơn có đỉnh đầu và đỉnh cuối kề nhau.

D.

Đường đi có đỉnh đầu và đỉnh cuối khác nhau

Trả lời:

Đáp án đúng: A


Chu trình đơn trên đồ thị G là một đường đi đơn, tức là đường đi không lặp lại đỉnh, và có đỉnh đầu và đỉnh cuối trùng nhau. Điều này có nghĩa là bạn có thể bắt đầu từ một đỉnh, đi qua các đỉnh khác nhau, và quay trở lại đỉnh ban đầu mà không đi qua bất kỳ đỉnh nào hai lần (ngoại trừ đỉnh đầu/cuối).

Phương án A: Đúng. "Đường đi đơn có đỉnh đầu và đỉnh cuối trùng nhau" chính xác là định nghĩa của chu trình đơn.

Phương án B: Sai. Mặc dù chu trình là một dạng đường đi có hướng (nếu đồ thị có hướng), nhưng việc chỉ nói là "đường đi có hướng" không đủ để xác định một chu trình đơn. Hơn nữa, nó không nhấn mạnh tính chất "đơn" (không lặp lại đỉnh).

Phương án C: Sai. "Đường đi đơn có đỉnh đầu và đỉnh cuối kề nhau" không đủ để tạo thành một chu trình, vì nó chỉ đảm bảo đỉnh đầu và đỉnh cuối nối với nhau, chứ không đảm bảo là đường đi quay trở lại điểm xuất phát.

Phương án D: Sai. "Đường đi có đỉnh đầu và đỉnh cuối khác nhau" là định nghĩa của một đường đi, không phải chu trình.

Câu hỏi liên quan