Câu 1: Đồ thị là gì?

A. Tập hợp các điểm và các đoạn thẳng nối các điểm đó

B. Một hàm số

C. Một hình phẳng

D. Một đường cong

Câu 2: Các phần tử cơ bản của đồ thị gồm?

A. Đỉnh và cạnh

B. Hàm số và biến số

C. Điểm và vectơ

D. Góc và đường thẳng

Câu 3: Một cạnh trong đồ thị nối hai đỉnh gọi là gì?

A. Cạnh liền kề

B. Cạnh đơn

C. Đường đi

D. Cung

Câu 4: Độ của một đỉnh trong đồ thị là gì?

A. Số cạnh kề với đỉnh đó

B. Khoảng cách từ đỉnh đến gốc tọa độ

C. Số đỉnh liền kề

D. Số đỉnh không liên kết

Câu 5: Đồ thị vô hướng là đồ thị mà

A. Các cạnh không có hướng

B. Các cạnh có hướng rõ ràng

C. Chỉ có một đỉnh

D. Không có cạnh nào

Câu 6: Đồ thị có hướng là đồ thị mà

A. Các cạnh có hướng xác định từ đỉnh này sang đỉnh khác

B. Các cạnh không có hướng

C. Không có cạnh

D. Chỉ có một đỉnh

Câu 7: Đường đi trong đồ thị là gì?

A. Chuỗi các đỉnh liên tiếp nối với nhau bằng các cạnh

B. Cạnh duy nhất trong đồ thị

C. Đường thẳng nối hai đỉnh bất kỳ

D. Đường cong trong mặt phẳng

Câu 8: Chu trình trong đồ thị là gì?

A. Đường đi bắt đầu và kết thúc tại cùng một đỉnh

B. Đường đi không quay lại đỉnh nào

C. Một cạnh riêng biệt

D. Một điểm cố định

Câu 9: Đường đi Euler là gì?

A. Đường đi qua tất cả các cạnh của đồ thị mỗi cạnh đúng một lần

B. Đường đi qua tất cả các đỉnh của đồ thị

C. Chu trình trong đồ thị

D. Đường thẳng dài nhất trong đồ thị

Câu 10: Đường đi Hamilton là gì?

A. Đường đi đi qua tất cả các đỉnh của đồ thị mỗi đỉnh đúng một lần

B. Đường đi qua tất cả các cạnh của đồ thị

C. Đường đi không lặp lại cạnh nào

D. Đường thẳng nối hai đỉnh

Câu 11: Một đồ thị mà tồn tại chu trình Euler được gọi là

A. Đồ thị Euler

B. Đồ thị Hamilton

C. Đồ thị hoàn chỉnh

D. Đồ thị trống

Câu 12: Điều kiện để đồ thị vô hướng có chu trình Euler là?

A. Mọi đỉnh có bậc chẵn và đồ thị liên thông

B. Tồn tại đỉnh bậc lẻ

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

D. Có ít nhất một cạnh

Câu 13: Đồ thị có hướng có chu trình Euler khi nào?

A. Mỗi đỉnh có bậc vào bằng bậc ra và đồ thị liên thông

B. Đỉnh có bậc vào khác bậc ra

C. Không có cạnh

D. Có ít nhất một cạnh

Câu 14: Đồ thị Hamilton có đặc điểm gì?

A. Có đường đi đi qua tất cả đỉnh mỗi đỉnh đúng một lần

B. Có đường đi đi qua tất cả cạnh mỗi cạnh đúng một lần

C. Có ít cạnh nhất

D. Chỉ có một đỉnh

Câu 15: Đồ thị đầy đủ (đồ thị hoàn chỉnh) là đồ thị có đặc điểm gì?

A. Mọi cặp đỉnh đều có cạnh nối

B. Chỉ có một đỉnh

C. Không có cạnh

D. Có ít nhất một chu trình

Câu 16: Đồ thị hai phần là đồ thị mà

A. Tập đỉnh được chia thành hai tập không giao nhau, các cạnh chỉ nối đỉnh ở hai tập khác nhau

B. Có hai cạnh

C. Có hai đỉnh

D. Có hai chu trình

Câu 17: Trong đồ thị hai phần, đỉnh cùng tập có cạnh nối nhau không?

A. Không

B. Có

C. Có thể có hoặc không

D. Luôn luôn có

Câu 18: Độ liên thông của đồ thị thể hiện điều gì?

A. Đồ thị có thể đi từ bất cứ đỉnh nào đến đỉnh khác bằng đường đi

B. Đồ thị có nhiều đỉnh

C. Đồ thị có nhiều cạnh

D. Đồ thị có chu trình

Câu 19: Đồ thị liên thông là đồ thị mà

A. Có đường đi nối mọi cặp đỉnh

B. Có nhiều cạnh nhất

C. Không có chu trình

D. Có ít nhất một cạnh

Câu 20: Đồ thị không liên thông là đồ thị mà

A. Không tồn tại đường đi nối tất cả các đỉnh

B. Có chu trình Euler

C. Có chu trình Hamilton

D. Tất cả đều đúng

Câu 21: Định nghĩa trọng số trong đồ thị là gì?

A. Giá trị gán cho các cạnh biểu thị độ dài, chi phí hoặc trọng lượng

B. Số cạnh trong đồ thị

C. Số đỉnh trong đồ thị

D. Độ dài đoạn thẳng trên mặt phẳng

Câu 22: Đồ thị có trọng số thường dùng để giải bài toán nào?

A. Tìm đường đi ngắn nhất

B. Tính diện tích

C. Tính chu vi

D. Tính thể tích

Câu 23: Thuật toán Dijkstra dùng để làm gì?

A. Tìm đường đi ngắn nhất từ một đỉnh đến các đỉnh còn lại trong đồ thị có trọng số dương

B. Tính chu trình Euler

C. Tính độ liên thông

D. Tìm chu trình Hamilton

Câu 24: Đồ thị có hướng khác đồ thị vô hướng ở điểm nào?

A. Cạnh có hướng rõ ràng từ đỉnh này đến đỉnh kia

B. Không có cạnh

C. Chỉ có một đỉnh

D. Tất cả đều đúng

Câu 25: Trong đồ thị có hướng, bậc vào của một đỉnh là gì?

A. Số cạnh kết thúc tại đỉnh đó

B. Số cạnh bắt đầu từ đỉnh đó

C. Tổng số cạnh kề với đỉnh

D. Số đỉnh kề

Câu 26: Bậc ra của một đỉnh trong đồ thị có hướng là gì?

A. Số cạnh bắt đầu từ đỉnh đó

B. Số cạnh kết thúc tại đỉnh đó

C. Tổng số cạnh kề với đỉnh

D. Số đỉnh kề

Câu 27: Đường đi Euler trong đồ thị có hướng là gì?

A. Đường đi đi qua tất cả các cạnh mỗi cạnh đúng một lần theo đúng hướng

B. Đường đi đi qua tất cả đỉnh

C. Chu trình Hamilton

D. Đường đi không lặp lại đỉnh

Câu 28: Trong đồ thị, một đỉnh cô lập là đỉnh

A. Không có cạnh nối đến hoặc đi từ nó

B. Có nhiều cạnh nối

C. Thuộc chu trình

D. Thuộc đường đi Euler

Câu 29: Đồ thị rỗng là đồ thị

A. Không có cạnh

B. Có một đỉnh

C. Có nhiều đỉnh

D. Có chu trình

Câu 30: Định nghĩa một cây trong đồ thị là gì?

A. Đồ thị liên thông không có chu trình

B. Đồ thị có nhiều chu trình

C. Đồ thị có ít nhất một chu trình

D. Đồ thị rỗng

Câu 31: Đặc điểm của cây có n đỉnh là?

A. Có đúng n-1 cạnh và không có chu trình

B. Có n cạnh

C. Có n+1 cạnh

D. Không có cạnh

Câu 32: Đường đi ngắn nhất trong đồ thị là gì?

A. Đường đi có tổng trọng số nhỏ nhất nối hai đỉnh

B. Đường đi có nhiều cạnh nhất

C. Đường đi không có trọng số

D. Đường thẳng nối hai điểm

Câu 33: Thuật toán nào sau đây thường dùng để tìm đường đi ngắn nhất?

A. Thuật toán Dijkstra

B. Thuật toán Euclid

C. Thuật toán QuickSort

D. Thuật toán MergeSort

Câu 34: Đồ thị liên thông nghĩa là

A. Từ mọi đỉnh có thể đi đến mọi đỉnh khác bằng đường đi

B. Có nhiều cạnh

C. Có ít nhất một chu trình

D. Không có cạnh

Câu 35: Đồ thị vô hướng là đồ thị

A. Cạnh không có hướng

B. Cạnh có hướng

C. Không có cạnh

D. Chỉ có một đỉnh

Câu 36: Đỉnh kề trong đồ thị là gì?

A. Hai đỉnh được nối bởi một cạnh

B. Hai đỉnh không liên kết

C. Đỉnh nằm trong chu trình

D. Đỉnh nằm trên trục đối xứng

Câu 37: Trong đồ thị, cạnh kề là gì?

A. Cạnh nối hai đỉnh kề nhau

B. Cạnh nối hai đỉnh không kề nhau

C. Cạnh nằm trong chu trình

D. Cạnh không có trọng số

Câu 38: Một chu trình trong đồ thị là

A. Đường đi bắt đầu và kết thúc tại cùng một đỉnh

B. Đường thẳng nối hai đỉnh

C. Cạnh độc lập

D. Đường đi không quay lại đỉnh nào

Câu 39: Một đường đi trong đồ thị là

A. Chuỗi các đỉnh liên tiếp nhau qua các cạnh

B. Đường thẳng nối hai đỉnh bất kỳ

C. Cạnh riêng biệt

D. Đường cong trên mặt phẳng

Câu 40: Độ dài của đường đi trong đồ thị trọng số là gì?

A. Tổng trọng số các cạnh trong đường đi

B. Số cạnh trong đường đi

C. Số đỉnh trong đường đi

D. Khoảng cách hình học

Câu 41: Định nghĩa đường đi ngắn nhất trong đồ thị trọng số là gì?

A. Đường đi có tổng trọng số nhỏ nhất giữa hai đỉnh

B. Đường đi có số cạnh ít nhất

C. Đường đi qua tất cả đỉnh

D. Đường đi có nhiều cạnh nhất

Câu 42: Đồ thị đầy đủ là đồ thị có

A. Cạnh nối mọi cặp đỉnh

B. Không có cạnh

C. Chỉ có một đỉnh

D. Chu trình Euler

Câu 43: Đồ thị rỗng là đồ thị có

A. Không có cạnh

B. Một đỉnh

C. Chu trình

D. Đỉnh cô lập

Câu 44: Đồ thị đường đôi là gì?

A. Đồ thị có hai cạnh nối cùng cặp đỉnh

B. Đồ thị có hai đỉnh

C. Đồ thị có hai chu trình

D. Đồ thị có hai cạnh song song

Câu 45: Đồ thị đơn là đồ thị

A. Không có đường đôi và không có cạnh tự hồi

B. Có đường đôi

C. Có cạnh tự hồi

D. Không có cạnh

Câu 46: Cạnh tự hồi trong đồ thị là gì?

A. Cạnh nối một đỉnh với chính nó

B. Cạnh nối hai đỉnh khác nhau

C. Cạnh không có trọng số

D. Cạnh không tồn tại

Câu 47: Định nghĩa đỉnh lá trong cây là gì?

A. Đỉnh có bậc bằng 1

B. Đỉnh có bậc lớn nhất

C. Đỉnh không kề cạnh nào

D. Đỉnh nằm trong chu trình

Câu 48: Đồ thị con của đồ thị G là gì?

A. Đồ thị được tạo từ một tập con các đỉnh và cạnh của G

B. Đồ thị có nhiều đỉnh hơn G

C. Đồ thị không liên quan đến G

D. Đồ thị có ít cạnh hơn G

Câu 49: Đường đi ngắn nhất từ đỉnh A đến đỉnh B là

A. Đường đi có tổng trọng số nhỏ nhất nối A và B

B. Đường đi có nhiều cạnh nhất

C. Đường đi qua tất cả đỉnh

D. Đường thẳng nối A và B

Câu 50: Trong đồ thị có hướng, đường đi từ đỉnh A đến đỉnh B là

A. Chuỗi các đỉnh liên tiếp mà các cạnh có hướng đúng chiều từ A đến B

B. Chuỗi các đỉnh bất kỳ

C. Đường thẳng nối A và B

D. Chu trình

Câu 51: Định nghĩa chu trình Euler là

A. Chu trình đi qua tất cả các cạnh mỗi cạnh một lần

B. Chu trình đi qua tất cả các đỉnh

C. Đường đi đi qua các đỉnh lặp lại

D. Đường thẳng nối đỉnh

Câu 52: Thuật toán tìm đường đi ngắn nhất trong đồ thị trọng số không âm là

A. Thuật toán Dijkstra

B. Thuật toán Kruskal

C. Thuật toán Floyd

D. Thuật toán Prim

Câu 53: Thuật toán Kruskal dùng để

A. Tìm cây khung nhỏ nhất trong đồ thị có trọng số

B. Tìm đường đi ngắn nhất

C. Tìm chu trình Euler

D. Tìm đường đi Hamilton

Câu 54: Thuật toán Prim dùng để

A. Tìm cây khung nhỏ nhất trong đồ thị có trọng số

B. Tìm đường đi ngắn nhất

C. Tìm chu trình Euler

D. Tìm đường đi Hamilton

Câu 55: Đặc điểm của cây khung nhỏ nhất là gì?

A. Là cây bao phủ tất cả các đỉnh với tổng trọng số cạnh nhỏ nhất

B. Là cây có số cạnh nhiều nhất

C. Là cây có nhiều chu trình

D. Là cây có trọng số lớn nhất

Câu 56: Định nghĩa đồ thị hoàn chỉnh là

A. Đồ thị có cạnh nối mọi cặp đỉnh

B. Đồ thị không có cạnh

C. Đồ thị có chu trình Euler

D. Đồ thị có ít đỉnh nhất

Câu 57: Thuật toán Floyd dùng để

A. Tìm đường đi ngắn nhất giữa mọi cặp đỉnh trong đồ thị trọng số

B. Tìm cây khung nhỏ nhất

C. Tìm chu trình Euler

D. Tìm đường đi Hamilton

Câu 58: Độ liên thông của đồ thị thể hiện

A. Mức độ kết nối giữa các đỉnh trong đồ thị

B. Số cạnh trong đồ thị

C. Số đỉnh trong đồ thị

D. Tổng trọng số cạnh

Câu 59: Đồ thị có hướng liên thông mạnh khi nào?

A. Có đường đi từ mọi đỉnh đến mọi đỉnh khác

B. Có ít nhất một cạnh

C. Có một chu trình

D. Không có cạnh

Câu 60: Đồ thị có hướng liên thông yếu khi nào?

A. Đồ thị vô hướng tương ứng liên thông

B. Có nhiều chu trình

C. Không có chu trình

D. Không có cạnh