MAD-nhomB

Bài toán người bán hàng (Traveling Salesman Problem - TSP) tương đương với bài toán nào sau đây trong lý thuyết đồ thị?

• A. Tìm chu trình Euler có trọng số lớn nhất

• B. Tìm chu trình Hamilton có tổng trọng số nhỏ nhất

• C. Tìm đường đi ngắn nhất từ một đỉnh đến tất cả các đỉnh còn lại

• D. Tìm chu trình ngắn nhất không lặp lại đỉnh

Đâu là điều kiện cần và đủ để một đồ thị vô hướng có chu trình Euler?

• A. Đồ thị liên thông và mọi đỉnh đều có bậc chẵn

• B. Đồ thị liên thông và có ít nhất một chu trình

• C. Đồ thị liên thông và tồn tại ít nhất hai đỉnh bậc lẻ

• D. Đồ thị có ít nhất một chu trình và một đỉnh bậc chẵn

Công thức tính số cung tối đa của một đồ thị có hướng đơn (không khuyên, không đa cung) với nnn đỉnh là:

• A. n(n−1)2\dfrac{n(n-1)}{2}2n(n−1)​

• B. n(n−1)n(n-1)n(n−1)

• C. 2n2n2n

• D. n2n^2n2

Thuật toán nào sau đây không dùng để tìm đường đi ngắn nhất trong đồ thị?

• A. Dijkstra

• B. Bellman-Ford

• C. Kruskal

• D. Floyd-Warshall

Đồ thị nào sau đây luôn liên thông?

A. Đồ thị có đúng một chu trình
B. Cây (Tree)
C. Đồ thị có tất cả đỉnh đều bậc chẵn
D. Đồ thị có ít nhất một cạnh

• A. Đồ thị có đúng một chu trình

• B. Cây (Tree)

• C. Đồ thị có tất cả đỉnh đều bậc chẵn

• D. Đồ thị có ít nhất một cạnh

Số cạnh tối đa trong một cây có nnn đỉnh là:

• A. n^2

• B. n

• C. n−1

• D. n+1

Thuật toán Kruskal dùng để giải bài toán:

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

• B. Tìm cây bao trùm nhỏ nhất

• C. Tìm chu trình Hamilton

• D. Tính số thành phần liên thông

Trong đồ thị vô hướng, tổng bậc của tất cả các đỉnh luôn là:

• A. Số chẵn

• B. Số lẻ

• C. Bằng số đỉnh

• D. Bằng số cạnh

Đâu là đặc điểm của đồ thị hai phía (bipartite graph)?

• A. Tồn tại chu trình Euler

• B. Không có chu trình

• C. Không có chu trình lẻ

• D. Mỗi đỉnh có bậc chẵn

Công cụ nào thường dùng để biểu diễn đồ thị trong máy tính?

• A. Cây AVL

• B. Ma trận kề hoặc danh sách kề

• C. Danh sách tuyến tính

• D. Mảng động