Câu hỏi 39
Một đồ thị đơn được gọi là đồ thị **chia hết** nếu có thể gán nhãn các đỉnh của nó bằng các số nguyên dương sao cho giữa hai đỉnh có cạnh nối khi và chỉ khi nhãn của một đỉnh chia hết cho nhãn của đỉnh kia.
Một đồ thị đơn được gọi là đồ thị **hoán vị** nếu có thể gán nhãn các đỉnh của nó bởi $1, 2, \dots, n$ và tồn tại một hoán vị $\pi$ sao cho giữa hai đỉnh $i, j$ có cạnh nối khi và chỉ khi $i \gt j$ và $\pi(i) \lt \pi(j)$ (đồ thị là vô hướng!)
Chứng minh rằng một đồ thị đơn là đồ thị hoán vị khi và chỉ khi cả đồ thị bù của nó và chính nó đều là đồ thị chia hết.
Một đồ thị đơn được gọi là đồ thị **hoán vị** nếu có thể gán nhãn các đỉnh của nó bởi $1, 2, \dots, n$ và tồn tại một hoán vị $\pi$ sao cho giữa hai đỉnh $i, j$ có cạnh nối khi và chỉ khi $i \gt j$ và $\pi(i) \lt \pi(j)$ (đồ thị là vô hướng!)
Chứng minh rằng một đồ thị đơn là đồ thị hoán vị khi và chỉ khi cả đồ thị bù của nó và chính nó đều là đồ thị chia hết.