Đồ thị G = (V, E) được gọi là đơn đồ thị nếu.
giữa hai đỉnh bất kỳ i, j ∈V, có nhiều nhất một cạnh, có kể đến thứ tự các đỉnh.
Giữa hai đỉnh bất kỳ i, j ∈ V, có nhiều nhất một cạnh.
Giữa hai đỉnh bất kỳ i, j ∈ V, có thể có nhiều hơn một cạnh, có kể đến thứ tự các đỉnh.
Giữa hai đỉnh bất kỳ i, j ∈ V, có thể có nhiều hơn một cạnh, không kể đến thứ tự các đỉnh.
Đáp án đúng: B
Đồ 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.
Câu hỏi liên quan
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.
Gọi V là tập hợp các đỉnh của đồ thị G. Ta có:
∑deg(v) = 2|E|, với v ∈ V, trong đó |E| là số cạnh của đồ thị.
Tổng bậc của các đỉnh luôn là một số chẵn.
Giả sử V_l là tập hợp các đỉnh bậc lẻ và V_c là tập hợp các đỉnh bậc chẵn. Ta có:
∑deg(v) = ∑deg(v_l) + ∑deg(v_c) = 2|E|, với v ∈ V, v_l ∈ V_l, v_c ∈ V_c
Vì ∑deg(v_c) là một số chẵn, nên ∑deg(v_l) cũng phải là một số chẵn để tổng của chúng là một số chẵn.
Để ∑deg(v_l) là một số chẵn, số lượng các đỉnh bậc lẻ (|V_l|) phải là một số chẵn, vì mỗi deg(v_l) là một số lẻ.
Do đó, số đỉnh bậc lẻ trong đồ thị vô hướng G là một số chẵn.
Vậy đáp án đúng là C.
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:
