Thi thử trắc nghiệm ôn tập Toán rời rạc - Đề #14

Danh sách câu hỏi

1. Câu 1:

   Đường đi trong đồ thị G vô hướng từ đỉnh s đến đỉnh t là một dãy:

   • A. Các cạnh e1,e2,…,en kề nhau
   • B. Các đỉnh v0 = s, v1, v2, …,vn = t kề nhau, các cạnh ei=(vi-1,vi) đôi một khác nhau, i = 0..n.
   • C. Các cạnh e1,e2,…,en không kề nhau.
   • D. Các đỉnh v0 = s, v1, v2, …,vn = t không kề nhau

2. Câu 2:

   Cho đồ thị G vô hướng, đỉnh $v \times G$ có bậc bằng 1 khi:

   • A. Có một cạnh xuất phát từ v
   • B. Có hơn một cạnh xuất phát từ v
   • C. Có đúng một cạnh đi vào và có hơn một đỉnh đi ra khỏi đỉnh này.
   • D. Tồn tại khuyên ở đỉnh đó.

3. Câu 3:

   Đồ thị G là không liên thông nếu nó chứa:

   • A. Cạnh có hướng
   • B. Đỉnh cô lập
   • C. Đỉnh treo.
   • D. Cạnh vô hướng

4. Câu 4:

   Đồ thị G vô hướng được gọi là liên thông nếu giữa mọi cặp đỉnh u,v bất kỳ đều có:

   • A. Một cạnh nối giữa u và v
   • B. Một đường đi có hướng nối u đến v
   • C. Một đường đi vô hướng nối u đến v
   • D. Hai cạnh nối u đến v

5. Câu 5:

   Chu trình trên đồ thị G là:

   • A. Đường đi có hướng với đỉnh đầu và đỉnh cuối trùng nhau.
   • B. Đường đi có đỉnh đầu và đỉnh cuối trùng nhau.
   • C. Đường đi có đỉnh đầu và đỉnh cuối kề nhau.
   • D. Đường đi có đỉnh đầu và đỉnh cuối không kề nhau

6. Câu 6:

   Số đỉnh bậc lẻ trong đồ thị G vô hướng:

   • A. Phụ thuộc vào số đỉnh của đồ thị.
   • B. Là một số lẻ
   • C. Là một số chẵn.
   • D. Phụ thuộc vào số cạnh của đồ thị.

7. Câu 7:

   Chu trình đơn trên đồ thị G là:

   • A. Đường đi đơn có đỉnh đầu và đỉnh cuối trùng nhau.
   • B. Đường đi có hướng với đỉnh đầu và đỉnh cuối trùng nhau.
   • C. Đường đi đơn có đỉnh đầu và đỉnh cuối kề nhau.
   • D. Đường đi có đỉnh đầu và đỉnh cuối khác nhau

8. Câu 8:

   Bậc của đỉnh trong đồ thị có hướng G là:

   • A. Số cạnh đi vào đỉnh đó.
   • B. Số cạnh đi ra khỏi đỉnh đó.
   • C. Tổng của cạnh đi vào và số cạnh đi ra khỏi đỉnh đó.
   • D. Hiệu của cạnh đi vào và cạnh đi ra khỏi đỉnh đó

9. Câu 9:

   Độ dài của một chu trình trên đồ thị G là:

   • A. Số cạnh tạo thành chu trình.
   • B. Số đỉnh tạo thành chu trình +1.
   • C. Số cạnh tạo chu trình + 1.
   • D. Số đỉnh trên tạo chu trình – 1.

10. Câu 10:

    Đỉnh cô lập trên đồ thị G là:

    • A. Đỉnh có 2 đỉnh kề với nó.
    • B. Đỉnh có bậc bằng 1
    • C. Đỉnh có bậc bằng 0
    • D. Đỉnh có bậc -1

11. Câu 11:

    Đường đi đơn trong đồ thị G là đường đi:

    • A. Các đỉnh trên nó đối xứng từng đôi một
    • B. Các đỉnh chỉ xuất hiện một lần trừ đỉnh đầu và đỉnh cuối.
    • C. Đỉnh đầu và đỉnh cuối khác nhau.
    • D. Mỗi đỉnh chỉ kề với hai đỉnh.

12. Câu 12:

    Đồ thị đầy đủ K_n có số đỉnh và số cạnh tương ứng là:

    • A. n, 2n.
    • B. n, n(2n-1)/2.
    • C. n+1, 2n.
    • D. n, n(n-1)/2.

13. Câu 13:

    Đồ thị C_n có số đỉnh và số cạnh tương ứng là:

    • A. n, n+1
    • B. n, n
    • C. n, n-1
    • D. n, 2n

14. Câu 14:

    Đồ thị lập phương Q_n là đồ thị:

    • A. 2n đỉnh, mỗi đỉnh kề nhau chỉ khác nhau một bit.
    • B. 2n đỉnh, mỗi đỉnh kề nhau chỉ khác nhau nhiều nhất 2 bit.
    • C. 2n đỉnh, mỗi đỉnh được biểu diễn bởi một xâu bit độ dài n sao cho hai đỉnh kề nhau chỉ khác nhau một bit
    • D. n đỉnh, mỗi đỉnh được biểu diễn bởi một xâu bit độ dài n sao cho hai đỉnh kề nhau chỉ khác nhau một bit.

15. Câu 15:

    Chu trình Euler của đồ thị là chu trình đi qua tất cả các đỉnh.

    • A. Mỗi đỉnh đúng một lần.
    • B. Mỗi cạnh đúng một lần.
    • C. Mỗi cạnh không quá một lần
    • D. Đi qua đỉnh đầu và đỉnh cuối hai lần

16. Câu 16:

    Chu trình Euler đi qua mỗi đỉnh của đồ thị:

    • A. Không quá một lần
    • B. Đúng một lần.
    • C. Không xác định
    • D. Nhiều hơn một lần

17. Câu 17:

    Đường đi Euler đi qua mỗi cạnh của đồ thị:

    • A. Không quá một lần.
    • B. Đúng một lần.
    • C. Không xác định
    • D. Có thể nhiều hơn một lần.

18. Câu 18:

    Chu trình Hamilton là chu trình đi qua tất cả các đỉnh của đồ thị mỗi đỉnh.

    • A. Không quá một lần.
    • B. Đúng một lần.
    • C. Luôn nhiều hơn một lần.
    • D. Không xác định

19. Câu 19:

    Đường đi Hamilton là đường đi đi qua tất cả các đỉnh của đồ thị mỗi đỉnh.

    • A. Đúng một lần
    • B. Luôn nhiều hơn một lần.
    • C. Không quá một lần.
    • D. Không xác định.

20. Câu 20:

    Đồ thị G được gọi là nửa Hamilton nếu tồn tại đường đi đi qua tất cả các đỉnh của đồ thị.

    • A. Mỗi cạnh một lần.
    • B. Mỗi cạnh không quá một lần.
    • C. Mỗi đỉnh một lần.
    • D. Một đỉnh không quá một lần.

21. Câu 21:

    Đa đồ thị liên thông G có chu trình Hamilton nếu:

    • A. Bậc của các đỉnh trong đồ thị -2
    • B. Bậc của các đỉnh trong đồ thị -n
    • C. Bậc của các đỉnh trong đồ thị -n/2
    • D. Bậc của các đỉnh trong đồ thị -n/4

22. Câu 22:

    Một đồ thị được gọi là phẳng nếu:

    • A. Có thể vẽ được trên một mặt phẳng mà có các cạnh cắt nhau ở đỉnh ngoài
    • B. Có thể vẽ được trên một mặt phẳng mà không có các cạnh nào cắt nhau
    • C. Có thể vẽ được trên một mặt phẳng mà có hai cạnh bất kỳ cắt nhau
    • D. Có thể vẽ được trên một mặt phẳng mà không có quá hai cạnh cắt nhau

23. Câu 23:

    Số màu của một đồ thị là:

    • A. Số trung bình các màu cần thiết để tô màu đồ thị này
    • B. Số tối thiểu các màu cần thiết để tô màu đồ thị này
    • C. Số tối đa các màu cần thiết để tô màu đồ thị này
    • D. Số theo yêu cầu các màu cần thiết để tô màu đồ thị này

24. Câu 24:

    Số màu của một đồ thị phẳng là:

    • A. Bằng 5.
    • B. Lớn hơn 4.
    • C. Lớn hơn hoặc bằng 5.
    • D. Không lớn hơn 4

25. Câu 25:

    Đồ thị đầy đủ K_n có số màu bằng: 

    • A. (n- 2)
    • B. n
    • C. (n-1)
    • D. n(n-1)/2

26. Câu 26:

    Đồ thị G vô hướng n đỉnh là một cây nếu:

    • A. Nếu liên thông và có n-1 cạnh
    • B. Nếu không liên thông và có n-1 cạnh
    • C. Nếu liên thông và có n cạnh
    • D. Nếu không liên thông và có n cạnh

27. Câu 27:

    Cây là một đồ thị vô hướng:

    • A. Liên thông và số đỉnh nhỏ hơn số cạnh là 1.
    • B. Liên thông và số đỉnh bằng số cạnh
    • C. Liên thông và không chứa chu trình
    • D. Không liên thông và có số đỉnh bằng số cạnh là 1.

28. Câu 28:

    Bài toàn xây dựng cây khung nhỏ nhất của đồ thị được phát biểu trên:

    • A. Đồ thị có hướng có trọng số
    • B. Đồ thị vô hướng có trọng số bất kỳ
    • C. Đồ thị vô hướng
    • D. Đồ thị vô hướng có trọng số dương

29. Câu 29:

    Cho G =(V,E) là đồ thị vô hướng liên thông n đỉnh. Cây T =(V_T, E_T) được gọi là cây khung của đồ thị G nếu:

    • A. T liên thông và mỗi cạnh của nó đều là cầu.
    • B. Nếu thêm vào T một cạnh thì ta có ít nhất một chu trình
    • C. ${V_T} = V,{\rm{ }}{E_T} \times {\rm{ }}E$
    • D. T liên thông, có đúng n cạnh và ${E_T} \times E.$

30. Câu 30:

    Cho G =(V,E) là đồ thị vô hướng liên thông n đỉnh. T = (V_T, E_T) được gọi là cây khung của đồ thị G nếu:

    • A. T liên thông và chứa n đỉnh của G.
    • B. T không liên thông, không chứa chu trình và chứa n cạnh của G.
    • C. T liên thông, không chứa chu trình và chứa n đỉnh của G.