500+ câu trắc nghiệm tổng hợp Toán rời rạc có đáp án - Phần 15

75

35

45

30

34650

220

3465

650

Số đỉnh bậc lẻ và số đỉnh bậc chẵn là một số chẵn

Số đỉnh bậc chẵn là một số chẵn

Số đỉnh bậc lẻ là một số chẵn

Số đỉnh bậc lẻ là một số lẻ

1, 4, 3, 2, 5, 6.

2, 1, 5, 2, 3, 3.

2, 4, 3, 4, 3, 2.

1, 4, 3, 2, 2, 3.

1, 2, 3, 4, 5.

0, 1, 2, 2, 3.

3, 4, 3, 4, 3.

1, 2, 3, 4, 7.

Danh sách tất cả các cạnh.

Danh sách tất cả các đỉnh

Danh sách tất cả các cạnh và các đỉnh.

Không lưu trữ danh sách cạnh và đỉnh nào.

Các cạnh kề với một đỉnh.

Các đỉnh kề với một đỉnh.

Tất cả các đỉnh kề và cạnh kề với nó.

Các bậc của đỉnh kề với một đỉnh.

Hai lần số cạnh.

Hai lần số đỉnh.

Trung bình cộng của số đỉnh và số cạnh.

Tổng của số đỉnh và số cạnh.

Đồ thị là liên thông.

Đồ thị không liên thông.

Tính liên thông của đồ thị không xác định.

Đồ thị là liên thông mạnh

Euler

Hamilton và Euler

Hamilton

Không liên thông

Thuật toán DFS(u) duyệt tất cả các đỉnh của đồ thị trong cùng thành phần liên thông với đỉnh u

Thuật toán DFS(u) luôn tìm ra được đường đi giữa hai đỉnh bất kì của đồ thị

Thuật toán DFS(u) duyệt tất cả các thành phần liên thông của đồ thị

Thuật toán DFS(u) duyệt tất cả các đỉnh của đồ thị mỗi đỉnh đúng một lần

Thuật toán BFS(u) duyệt tất cả các thành phần liên thông của đồ thị

Thuật toán BFS(u) luôn tìm ra được đường đi giữa hai đỉnh bất kì của đồ thị

Thuật toán BFS(u) duyệt tất cả các đỉnh của đồ thị trong cùng thành phần liên thông với đỉnh u

Thuật toán BFS(u) duyệt tất cả các đỉnh của đồ thị mỗi đỉnh đúng một lần

4,6

4,8

5,8

4,4

Có tập đỉnh được phân thành hai tập con tương ứng có m đỉnh và n đỉnh.

Có một cạnh giữa hai đỉnh nếu và chỉ nếu một đỉnh thuộc tập con này và đỉnh thứ hai thuộc tập con kia.

Có một cạnh giữa hai đỉnh nếu và chỉ nếu mỗi đỉnh đều thuộc vào hai tập đỉnh con.

Có m+n đỉnh, mn cạnh.

Liên thông và có hai đỉnh bậc lẻ.

Không liên thông và có hai đỉnh bậc lẻ.

Liên thông và có một đỉnh bậc lẻ.

Không liên thông và không có đỉnh bậc lẻ.

3

4

2

-2

Trùng nhau

Khác nhau

Có cùng bậc chẵn

Đỉnh đầu bậc chẵn đỉnh cuối bậc lẻ

Không có đỉnh bậc chẵn

Không có đường đi Euler.

Không có chu trình Euler

Có chu trình Euler

1

2

3

4

1

2

3

4

Chu trình đi qua tất cả các đỉnh mỗi đỉnh đúng một lần trừ đỉnh bậc lẻ

Chu trình đi qua tất cả các đỉnh mỗi đỉnh đúng một lần trừ đỉnh bậc chẵn

Chu trình đi qua tất cả các đỉnh của đồ thị mỗi đỉnh đúng một lần

Chu trình đi qua tất cả các đỉnh của đồ thị mỗi đỉnh hơn một lần

G có chu trình Hamilton

G có chu trình Euler

G không có chu trình Hamilton

G không có chu trình

Có thể xóa tất cả các cạnh còn lại không liên thuộc với đỉnh đó.

Có thể xóa tất cả các cạnh còn lại liên thuộc với đỉnh đó.

Có thể xóa tất cả các cạnh còn lại của đồ thị.

Có thể lấy thêm các cạnh liên thuộc với đỉnh đó.

5 miền

6 miền

7 miền

8 miền

K5

K2

K6

K7

O(n3 log2n)

O(n2)

O(n3)

O(n2 log2n)

Đồ thị vô hướng hoặc có hướng có trọng số không âm.

Đồ thị liên thông có trọng số không âm

Đồ thị có hướng có trọng số không âm.

Đồ thị vô hướng hoặc có hướng không có chu trình âm