Đối vui: Tìm thứ tự tuyến tính

Một thứ tự tuyến tính (linear order) là một dãy có thứ tự của $n$ phần tử trong tập $[n] = \{1,2,...,n\}$. Nói cách khác, một thứ tự tuyến tính chỉ đơn giản là một hoán vị của tập $n$ phần tử này.

Ví dụ tập có 4 phần tử $\{1,2,3,4\}$, một (trong những) thứ tự tuyến tính của tập này là $(2,3,1,4)$.

Câu hỏi: Chứng minh rằng có thể tìm được một tập $\Sigma$ có $\lceil n/2 \rceil$ thứ tự tuyến tính sao cho với bất kì hai hai phần tử $i\not= j $ nào trong tập $[n]$, luôn tồn tại một thứ tự tuyến tính $\sigma \in \Sigma$ sao cho $i$ và $j$ liền kề nhau trong $\sigma$.

Ví dụ: với $n = 4$ thì tập hai tuyến tính cần tìm là $(2,1,3,4)$ và $(1,4,2,3)$.

Gợi ý lời giải: Bài toán có thể được quy về: cho một đồ thị đầy đủ $K_n$ với $n$ đỉnh, tìm một tập $\lceil n/2 \rceil$ đường đi Hamilton (Hamiltonian path) sao cho mỗi cạnh của đồ thị đầy đủ thuộc ít nhất một trong số các đường đi Hamilton đó. (Xem hình minh hoạ dưới đây.)


Hình 1: đồ thị $K_6$ (a) có thể phủ bởi 3 đường đi Hamilton trong hình (b), (c) và (d): mỗi cạnh thuộc đúng một đường đi.

Để tìm các đường đi Hamilton, xét trường hợp $n$ chẵn ($n= 2k$); trường hợp $n$ lẻ làm tương tự. Vẽ đồ thị $K_{2k}$ lồng trên một đa giác điều $2k$ đỉnh (như hình 1(a)). Nhận thấy mỗi cạnh của đồ thị hoặc là song song với $(i,i+1)$, hoặc là vuông góc với $(i,i+3)$ với một chỉ số $i$ nào thoả mãn $1 \leq i \leq k$. Ngoài ra, tập các cạnh hoặc song song với $(i,i+1)$ hoặc vuông góc với $(i,i+3)$ tạo thành một dường đi Hamilton. (Ví dụ trong hình 1(b) bao gồm các cạnh màu xanh là các cạnh song song với $(1,2)$ và các cạnh màu đỏ là các cạnh vuông góc với $(1,4)$.)

Như vậy, với mỗi $i \in [1,k]$, ta có một đường đi Hamilton là tập các cạnh song song với $(i,i+1)$ hoặc vuông góc với $(i,i+3)$; ta có tất cả $k = n/2$ dường đi Hamilton như vậy. (dpcm)


Facebook Comments

Reply

Your email address will not be published. Required fields are marked *