Ta nói cặp hai đỉnh (u,v) là cạnh vô hướng của đồ thị G = (V,E) nếu:
Đáp án đúng: C
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ự.
Câu hỏi liên quan
- 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:
Trong bài toán luồng cực đại, tính cân bằng của luồng (hay còn gọi là bảo toàn luồng) là một điều kiện tiên quyết. Điều này có nghĩa là, tại mọi đỉnh của mạng (trừ đỉnh phát s và đỉnh thu t), lượng luồng vào phải bằng lượng luồng ra. Đỉnh phát s là nơi luồng được tạo ra, và đỉnh thu t là nơi luồng được hấp thụ. Vì vậy, cân bằng luồng không áp dụng cho hai đỉnh này.
