G là một đơn đồ thị phẳng liên thông n đỉnh, m cạnh, gọi r là số miền trong biểu diễn phẳng của G khi đó:
Đáp án đúng: B
Câu hỏi liên quan
* A. Cạnh có hướng: Việc đồ thị có cạnh có hướng không ảnh hưởng đến tính liên thông. Đồ thị có hướng vẫn có thể liên thông nếu có đường đi giữa mọi cặp đỉnh (theo hướng hoặc bỏ qua hướng).
* B. Đỉnh cô lập: Đỉnh cô lập là đỉnh không kề với bất kỳ đỉnh nào khác. Nếu một đồ thị chứa đỉnh cô lập, chắc chắn đồ thị đó không liên thông, vì không có đường đi từ đỉnh cô lập đến bất kỳ đỉnh nào khác và ngược lại.
* C. Đỉnh treo: Đỉnh treo là đỉnh có bậc là 1 (chỉ kề với một đỉnh duy nhất). Một đồ thị chứa đỉnh treo vẫn có thể liên thông.
* D. Cạnh vô hướng: Việc đồ thị có cạnh vô hướng là điều kiện cần để xét tính liên thông (đối với đồ thị vô hướng), nhưng không phải là điều kiện khiến đồ thị không liên thông.
Vậy, đáp án đúng là 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.
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.
