Câu hỏi 84
Một đồ thị đơn hữu hạn $G$ có $n$ đỉnh được gọi là chia hết nếu có thể gán cho mỗi đỉnh $s$ của $G$ một số $n_{s}$ sao cho hai đỉnh phân biệt luôn có hai số phân biệt và hai đỉnh bất kì $s$ và $s^{\prime}$ được nối bởi một cạnh khi và chỉ khi $n_{s} \mid n_{s^{\prime}}$ hoặc $n_{s^{\prime}} \mid n_{s}$.
Một đồ thị đơn hữu hạn $G$ có $n$ đỉnh được gọi là hoán vị được nếu có thể đánh số các đỉnh của $G$ từ $1$ đến $n$ và tồn tại một hoán vị $\sigma$ của $\{1, \ldots, n\}$ sao cho các đỉnh mang số $i$ và $j$ được nối bởi một cạnh khi và chỉ khi $(i-j)(\sigma(i)-\sigma(j))\lt 0$.
Chứng minh rằng đồ thị $G$ là hoán vị được khi và chỉ khi $G$ và đồ thị bù của nó đều chia hết.
Một đồ thị đơn hữu hạn $G$ có $n$ đỉnh được gọi là hoán vị được nếu có thể đánh số các đỉnh của $G$ từ $1$ đến $n$ và tồn tại một hoán vị $\sigma$ của $\{1, \ldots, n\}$ sao cho các đỉnh mang số $i$ và $j$ được nối bởi một cạnh khi và chỉ khi $(i-j)(\sigma(i)-\sigma(j))\lt 0$.
Chứng minh rằng đồ thị $G$ là hoán vị được khi và chỉ khi $G$ và đồ thị bù của nó đều chia hết.