Câu hỏi: Có bao nhiêu cạnh trong đồ thị có 10 đỉnh, mỗi đỉnh có bậc bằng 6?

A. 60

B. 45

C. 30

D. 20

Câu 1: Cho đồ thị trọng số G=(V,E) như hình vẽ. Cây khung nhỏ nhất H = (V,T) theo thuật toán Prim có tập cạnh:

A. T ={(2,5)(2,6)(2,3)(6,2)(4,1)(5,4)}

B. T ={(5,3)(3,7)(2,3)(6,2)(4,1)(7,4)}

C. T ={(5,1)(3,5)(2,3)(6,2)(4,1)(7,4)}

D. T ={(4,7)(3,5)(2,3)(6,2)(4,1)(3,6)}

Câu 2: Cho đồ thị trọng số G=(V,E) như hình vẽ. Cây khung nhỏ nhất H = (V,T) theo thuật toán Prim có tập cạnh là:

A. T = {(3,6),(1,8),(8,2), (3,6), (6,7), (8,5), (5,7)}

B. T = {(1,2),(3,8),(8,5), (3,6), (6,7), (2,4), (4,7)}

C. T = {(5,7),(5,6),(8,2), (3,6), (6,7), (8,5), (8,4)}

D. T = {(1,8),(3,8),(8,2), (3,6), (6,7), (8,5), (8,4)}

Câu 3: Cho đồ thị như hình vẽ. Hãy cho biết kết quả thực hiện thuật toán BFS(1):

A. 1, 2, 4, 7, 3, 6, 8, 5, 9, 10

B. 1, 7, 6, 3, 9, 8, 5, 10, 4, 2

C. 1, 2, 6, 4, 5, 10, 9, 8, 3, 7

D. 1, 2, 4, 7, 8, 9, 5, 10, 3, 6

Câu 4: Mạng là một đồ thị có hướng,

A. trong đó có một đỉnh cô lập. Mỗi cung \(e = ({v_i}{\rm{ }},{v_j}){\rm{ }} \times {\rm{ }}E\) được gán một giá trị không âm qij gọi là khả năng thông qua của cung e.

B. trong đó có duy nhất một đỉnh s không có cung đi vào gọi là điểm phát, có duy nhất một đỉnh t không có cung đi ra gọi là điểm thu. Mỗi cung \(e = ({v_i}{\rm{ }},{v_j}){\rm{ }} \times {\rm{ }}E\) được gán một giá trị không âm qij gọi là khả năng thông qua của cung 

C. trong đó có duy nhất một đỉnh s có cung đi vào gọi là điểm phát, có duy nhất một đỉnh t có cung đi ra gọi là điểm thu. Mỗi cung \(e = ({v_i}{\rm{ }},{v_j}){\rm{ }} \times {\rm{ }}E\) được gán một giá trị không âm qij gọi là khả năng thông qua của cung

D. trong đó có duy nhất một đỉnh s có cung đi vào gọi là điểm phát, có duy nhất một đỉnh t không có cung đi ra gọi là điểm thu. Mỗi cung \(e = ({v_i}{\rm{ }},{v_j}){\rm{ }} \times {\rm{ }}E\) được gán một giá trị không âm qij gọi là khả năng thông qua của cung 

Câu 5: Biểu thức \((P \wedge Q) \to (P \vee Q)\) tương đương logic với biểu thức nào sau đây?

A. \((P \wedge Q) \vee (P \vee Q)\)

B. \((P \wedge Q) \vee (\overline {P \vee Q} )\)

C. \((\overline {P \wedge Q} ) \vee (P \vee Q)\)

D. \((\overline {P \wedge Q} ) \wedge (P \vee Q)\)

Câu 6: Cho đồ thị như hình vẽ. Kết quả khi duyệt đồ thị theo thuật toán DFS(G) là:

A. G, H, I, N, K, B, A, C, D, E, F

B. G, H, N, K, B, A, D, C, E, F, I

C. G, H, N, K, B, A, C, D, E, I, F

D. G, A, B, C, D, E, F, N, K, H, I