Câu hỏi 98
Cho $G$ là một đồ thị hai phía có trọng số $A \cup B$, với $|A|=|B|=n$. Nói cách khác, mỗi cạnh của đồ thị được gán một giá trị nguyên dương, gọi là trọng số của nó. Ngoài ra, định nghĩa trọng số của một ghép cặp hoàn hảo trong $G$ là tổng trọng số của các cạnh trong ghép cặp đó.
Gọi $G'$ là đồ thị có tập đỉnh $A \cup B$, và chứa cạnh $e$ khi và chỉ khi $e$ thuộc một ghép cặp hoàn hảo có trọng số nhỏ nhất nào đó trong $G$.
Chứng minh rằng mọi ghép cặp hoàn hảo trong $G'$ đều có cùng trọng số.
Gọi $G'$ là đồ thị có tập đỉnh $A \cup B$, và chứa cạnh $e$ khi và chỉ khi $e$ thuộc một ghép cặp hoàn hảo có trọng số nhỏ nhất nào đó trong $G$.
Chứng minh rằng mọi ghép cặp hoàn hảo trong $G'$ đều có cùng trọng số.