Câu hỏi 38
Cho một đồ thị (đơn) $G$ có $n \geq 2$ đỉnh $v_{1}, v_{2}, \ldots, v_{n}$ và $m \geq 1$ cạnh. Joël và Robert chơi trò chơi sau với $m$ đồng xu:
i) Đầu tiên Joël gán cho mỗi đỉnh $v_{i}$ một số nguyên không âm $w_{i}$ sao cho $w_{1}+\cdots+w_{n}=m$.
ii) Sau đó Robert chọn một tập con các cạnh (có thể rỗng), với mỗi cạnh được chọn anh ấy đặt một đồng xu lên đúng một trong hai đầu mút của nó, rồi xóa cạnh đó khỏi đồ thị. Khi anh ấy làm xong, số đồng xu trên mỗi đỉnh $v_{i}$ không được lớn hơn $w_{i}$.
iii) Sau đó Joël làm tương tự với tất cả các cạnh còn lại.
iv) Joël thắng nếu số đồng xu trên mỗi đỉnh $v_{i}$ bằng $w_{i}$.
Xác định tất cả các đồ thị $G$ mà Joël có chiến lược thắng.
i) Đầu tiên Joël gán cho mỗi đỉnh $v_{i}$ một số nguyên không âm $w_{i}$ sao cho $w_{1}+\cdots+w_{n}=m$.
ii) Sau đó Robert chọn một tập con các cạnh (có thể rỗng), với mỗi cạnh được chọn anh ấy đặt một đồng xu lên đúng một trong hai đầu mút của nó, rồi xóa cạnh đó khỏi đồ thị. Khi anh ấy làm xong, số đồng xu trên mỗi đỉnh $v_{i}$ không được lớn hơn $w_{i}$.
iii) Sau đó Joël làm tương tự với tất cả các cạnh còn lại.
iv) Joël thắng nếu số đồng xu trên mỗi đỉnh $v_{i}$ bằng $w_{i}$.
Xác định tất cả các đồ thị $G$ mà Joël có chiến lược thắng.