Chu trình trên đồ thị G là:
Đáp án đúng: B
Chu trình trong đồ thị là một đường đi, trong đó đỉnh đầu và đỉnh cuối của đường đi đó trùng nhau. Điều này có nghĩa là ta có thể bắt đầu từ một đỉnh, đi qua một số đỉnh khác và quay trở lại đỉnh ban đầu.
Do đó, đáp án đúng là B.
Câu hỏi liên quan
Một đồ thị vô hướng được gọi là cây nếu nó liên thông và không có chu trình. Điều này tương đương với việc nó liên thông và có số cạnh bằng số đỉnh trừ 1 (n-1).
A. Đúng, nếu đồ thị liên thông và có n-1 cạnh thì nó là một cây.
B. Sai, cây phải liên thông.
C. Sai, nếu đồ thị liên thông và có n cạnh thì nó chứa chu trình, do đó không phải là cây.
D. Sai, cây phải liên thông.
Để xác định xem một dãy số có thể là bậc của các đỉnh trong một đồ thị vô hướng hay không, ta sử dụng định lý sau: Một dãy số nguyên không âm d±ợc sắp xếp theo thứ tự giảm dần d1, d2, ..., dn là dãy bậc của một đồ thị vô hướng khi và chỉ khi Σdi chẵn.
A. 2 + 4 + 3 + 1 + 4 + 2 + 5 = 21 (lẻ) - không tồn tại
B. 3 + 4 + 2 + 1 + 4 + 2 + 6 = 22 (chẵn)- có thể tồn tại
C. 5 + 2 + 2 + 1 + 3 + 2 + 4 = 19 (lẻ) - không tồn tại
D. 2 + 1 + 4 + 3 + 4 + 2 + 7 = 23 (lẻ) - không tồn tại
Vậy, chỉ có B là có thể tồn tại.
