Chu trình Hamilton là:
Đáp án đúng: C
Chu trình Hamilton là một chu trình đi qua tất cả các đỉnh của đồ thị, mỗi đỉnh đúng một lần. Do đó, đáp án C là đáp án chính xác.
Câu hỏi liên quan
* Sử dụng mảng: Độ phức tạp là O(n^2), trong đó n là số đỉnh.
* Sử dụng hàng đợi ưu tiên (heap nhị phân): Độ phức tạp là O(E log V), trong đó E là số cạnh và V là số đỉnh. Trong trường hợp đồ thị dày đặc (E ≈ V^2), độ phức tạp trở thành O(V^2 log V) hay O(n^2 log n).
* Sử dụng Fibonacci heap: Độ phức tạp là O(E + V log V), có thể tốt hơn trong một số trường hợp, nhưng phức tạp hơn để triển khai.
Trong các phương án được đưa ra, O(n^2 log2n) (tương đương O(n^2 log n)) là độ phức tạp phổ biến nhất khi triển khai Dijkstra với hàng đợi ưu tiên (heap nhị phân).
Đồ thị đơn (simple graph) là đồ thị vô hướng không có khuyên (loop) và không có cạnh song song (multiple edges). Điều này có nghĩa là giữa hai đỉnh bất kỳ trong đồ thị đơn, chỉ có tối đa một cạnh nối chúng. Đáp án B thể hiện chính xác định nghĩa này.
Trong đồ thị vô hướng, một cạnh nối hai đỉnh u và v không phân biệt thứ tự của hai đỉnh đó. Tức là cạnh (u, v) và cạnh (v, u) được xem là một. Vì vậy, điều kiện để (u, v) là một cạnh vô hướng của đồ thị G = (V, E) là u và v thuộc tập đỉnh V và cặp (u, v) không có thứ tự.
- Phương án A sai vì chỉ yêu cầu các cạnh kề nhau mà không đề cập đến đỉnh đầu và đỉnh cuối, cũng như không đảm bảo tính liên tục của đường đi từ s đến t.
- Phương án C sai vì yêu cầu các cạnh không kề nhau, điều này trái với định nghĩa đường đi.
- Phương án D sai vì yêu cầu các đỉnh không kề nhau, điều này cũng trái với định nghĩa đường đi.
Cho mạng G, điểm phát s điểm thu t. Tính cân bằng của luồng f trên mạng G phải thỏa mãn cho:
