Toán rời rạc - Chương 4: đồ thị

Số cạnh lớn nhất của một đơn đồ thị vô hướng có 8 đỉnh là

A. \(32\)

B. \(16\)

C. \(28\)

D. \(64\)

Mỗi đỉnh của đồ thị đầy đủ \(K_6\) có bậc bằng

A. \(5\)

B. \(6\)

C. \(15\)

D. \(30\)

Đồ thị hai phía đầy đủ \(K_{4,5}\) có bao nhiêu cạnh?

A. \(9\)

B. \(10\)

C. \(25\)

D. \(20\)

Một đồ thị vô hướng có tổng bậc bằng 36. Số cạnh của nó là

A. \(36\)

B. \(18\)

C. \(72\)

D. \(9\)

Trong mọi đồ thị vô hướng, số đỉnh có bậc lẻ luôn là

A. số lẻ

B. số chẵn

C. bằng số cạnh

D. bằng số đỉnh bậc chẵn

Một đồ thị vô hướng liên thông có chu trình Euler nếu

A. có đúng hai đỉnh bậc lẻ

B. không có chu trình

C. mọi đỉnh đều có bậc chẵn

D. mọi đỉnh đều có bậc lẻ

Một đồ thị vô hướng liên thông có đúng hai đỉnh bậc lẻ thì

A. có đường đi Euler nhưng không có chu trình Euler

B. không có đường đi Euler

C. có chu trình Euler

D. chắc chắn là cây

Một đồ thị vô hướng là hai phía khi và chỉ khi

A. mọi đỉnh có bậc chẵn

B. đồ thị liên thông

C. không có chu trình

D. không chứa chu trình độ dài lẻ

Số màu tối thiểu để tô đúng các đỉnh của chu trình \(C_7\) là

A. \(1\)

B. \(2\)

C. \(7\)

D. \(3\)

Số sắc của đồ thị đầy đủ \(K_n\) bằng

A. \(2\)

B. \(n\)

C. \(n-1\)

D. \(\binom n2\)

Một đơn đồ thị phẳng liên thông có 10 đỉnh và 15 cạnh. Số miền là

A. \(5\)

B. \(6\)

C. \(7\)

D. \(25\)

Với đơn đồ thị phẳng có \(n\ge3\) đỉnh, bất đẳng thức nào luôn đúng?

A. \(m\le3n-6\)

B. \(m\ge3n-6\)

C. \(m=n^2\)

D. \(m\le n-1\)

Đồ thị nào sau đây không phẳng?

A. \(K_5\)

B. \(K_4\)

C. \(C_6\)

D. một cây 10 đỉnh

Ma trận kề của một đơn đồ thị vô hướng luôn

A. phản đối xứng

B. tam giác trên

C. có mọi phần tử bằng 1

D. đối xứng qua đường chéo chính

Một đơn đồ thị có 7 đỉnh và 9 cạnh. Đồ thị bù của nó có bao nhiêu cạnh?

A. \(21\)

B. \(12\)

C. \(9\)

D. \(16\)

Một đồ thị có dãy bậc \((4,3,3,2,2,2)\). Số cạnh của đồ thị là

A. \(16\)

B. \(6\)

C. \(8\)

D. \(10\)

Một đường đi đơn trong đồ thị là một dãy đỉnh liên tiếp sao cho

A. mọi đỉnh có bậc 2

B. đỉnh đầu bằng đỉnh cuối

C. mọi cạnh của đồ thị đều được dùng

D. không lặp đỉnh

Thuật toán Dijkstra tìm đường đi ngắn nhất đúng khi trọng số các cạnh

A. đều bằng nhau

B. không âm

C. đều âm

D. chỉ nhận giá trị 0 hoặc 1

Siêu lập phương \(Q_4\) có bao nhiêu cạnh?

A. \(16\)

B. \(64\)

C. \(32\)

D. \(8\)

Mười người bắt tay nhau, mỗi cặp bắt tay đúng một lần. Tổng số cái bắt tay là

A. \(45\)

B. \(90\)

C. \(10\)

D. \(100\)