Câu hỏi 141
Cho $G = G(V; E)$ là một biểu đồ đơn giản với đỉnh đặt $V$ và đặt cạnh $E$, và giả sử rằng $|V| = n$. Một bản đồ $f: V \rightarrow \mathbb{Z}$ được cho là tốt nếu $f$ thỏa mãn: $$
(1) \quad \sum_{v \in V} f(v) = |E|;
$$ (2) Nếu một màu tùy ý một số đỉnh thành màu đỏ, tồn tại một đỉnh màu đỏ $v$, sao cho $f(v)$ không lớn hơn số đỉnh tiếp giáp với $v$ không được tô màu thành màu đỏ. Cho $m(G)$ là số bản đồ tốt $f$. Chứng minh rằng nếu mỗi đỉnh của $V$ tiếp giáp với ít nhất một đỉnh khác, thì $n \le m(G) \le n!$.
(1) \quad \sum_{v \in V} f(v) = |E|;
$$ (2) Nếu một màu tùy ý một số đỉnh thành màu đỏ, tồn tại một đỉnh màu đỏ $v$, sao cho $f(v)$ không lớn hơn số đỉnh tiếp giáp với $v$ không được tô màu thành màu đỏ. Cho $m(G)$ là số bản đồ tốt $f$. Chứng minh rằng nếu mỗi đỉnh của $V$ tiếp giáp với ít nhất một đỉnh khác, thì $n \le m(G) \le n!$.