Lý thuyết đồ thị cơ bản

Đồ thị (Graph) trong lý thuyết đồ thị là gì?

• Một tập hợp các điểm được gọi là đỉnh
• Một tập hợp các đường nối các đỉnh được gọi là cạnh
• Một tập hợp bao gồm các đỉnh (vertices) và các cạnh (edges) nối các cặp đỉnh đó.
• Một cấu trúc dữ liệu chỉ dùng để tìm đường đi ngắn nhất.

Answer explanation

Một đồ thị được định nghĩa chính thức bởi hai thành phần: một tập hợp đỉnh V (Vertices) và một tập hợp cạnh E (Edges).

Trong đồ thị vô hướng, cạnh (u, v) và (v, u) được xem là gì?

• Hai cạnh khác nhau.
• Cùng một cạnh.
• Là một vòng lặp (loop).
• Là một cạnh có hướng.

Answer explanation

Trong đồ thị vô hướng, cạnh không có chiều, nên cạnh nối giữa u và v là duy nhất và có thể biểu diễn bằng (u, v) hoặc (v, u).

Bậc (degree) của một đỉnh trong đồ thị vô hướng là gì?

• Số đỉnh kề với nó.
• Số cạnh đi ra từ nó.
• Số cạnh đi vào nó.
• Tổng số đỉnh trong đồ thị.

Answer explanation

Bậc của đỉnh là số cạnh liên thuộc với đỉnh đó. Trong đồ thị vô hướng, đây cũng chính là số đỉnh kề với nó.

Cấu trúc dữ liệu nào thường được sử dụng để biểu diễn một đồ thị? (Chọn nhiều đáp án)

• Ma trận kề (Adjacency Matrix)
• Danh sách kề (Adjacency List)
• Mảng (Array)
• Hàng đợi (Queue)

Answer explanation

Ma trận kề và Danh sách kề là hai cách phổ biến và hiệu quả nhất để lưu trữ cấu trúc của một đồ thị trong máy tính.

Một đường đi (path) trong đồ thị là gì?

• Một chuỗi các đỉnh sao cho từ mỗi đỉnh có một cạnh nối tới đỉnh tiếp theo.
• Một tập hợp tất cả các đỉnh.
• Một tập hợp tất cả các cạnh.
• Một đỉnh không có cạnh nào.

Answer explanation

Định nghĩa của đường đi là một dãy các đỉnh liên tiếp được kết nối bởi các cạnh.

Thế nào là một chu trình (cycle) trong đồ thị?

• Một đường đi bắt đầu và kết thúc tại cùng một đỉnh.
• Một đường đi đi qua tất cả các đỉnh.
• Một đồ thị không có cạnh nào.
• Một tập hợp các đỉnh không được kết nối.

Answer explanation

Chu trình là một trường hợp đặc biệt của đường đi, nơi điểm xuất phát cũng là điểm kết thúc.

Ưu điểm của việc sử dụng Danh sách kề so với Ma trận kề là gì?

• Tiết kiệm không gian lưu trữ đối với đồ thị thưa (sparse graph).
• Luôn nhanh hơn khi kiểm tra sự tồn tại của một cạnh.
• Dễ cài đặt hơn.
• Tốn ít bộ nhớ hơn đối với đồ thị dày đặc (dense graph).

Answer explanation

Với đồ thị thưa (số cạnh E << V²), danh sách kề chỉ lưu các cạnh tồn tại (O(V+E)) nên tiết kiệm bộ nhớ hơn ma trận kề (luôn tốn O(V²)).

Trong đồ thị có trọng số (weighted graph), mỗi cạnh có thêm thuộc tính gì?

• Hướng (direction)
• Tên (label)
• Trọng số (weight) hoặc chi phí (cost)
• Màu sắc (color)

Answer explanation

Trọng số là một giá trị số được gán cho mỗi cạnh, thường biểu thị chi phí, khoảng cách, hoặc dung lượng.

Một đồ thị được gọi là liên thông (connected) khi nào?

• Khi mọi đỉnh đều có bậc lớn hơn 0.
• Khi có đường đi giữa mọi cặp đỉnh bất kỳ trong đồ thị.
• Khi đồ thị không có chu trình.
• Khi số cạnh bằng số đỉnh.

Answer explanation

Tính liên thông đảm bảo rằng toàn bộ đồ thị là một khối duy nhất, không bị chia cắt thành các phần riêng biệt.

Cây (Tree) là một dạng đồ thị đặc biệt có những tính chất nào? (Chọn nhiều đáp án)

• Vô hướng
• Liên thông
• Không chứa chu trình
• Mỗi đỉnh có bậc bằng 2

Answer explanation

Một cây được định nghĩa là một đồ thị vô hướng, liên thông và không có chu trình.