Một không gian metric hữu hạn, kí hiệu là $(X,d)$, bao gồm một tập hữu hạn điểm $X$ và một hàm khoảng cách $d(.)$ thoả mãn 3 tính chất sau:

  1. $d(x,y) = d(y,x)$ với mọi $x,y\in X$.
  2. $d(x,y) = 0$ khi và chỉ khi $x=y$.
  3. $d(x,y) \leq d(x,z) + d(y,z) $ với mọi $x,y,z\in X$.

    Cho một không gian metric hữu hạn $(X,d)$ có $n$ điểm. Với mỗi số nguyên $i \in \mathbb{Z}$, ta gọi $i$ là một số nguyên công hiệu nếu tồn tại $x,y\in X$ sao cho $d(x,y) \in [2^{i}, 2^{i+1}]$. Ngược lại, ta gọi $i$ là một số nguyên vô hiệu.

    Câu hỏi: Chứng minh rằng có không quá $2(n-1)$ số nguyên công hiệu.

    Ý nghĩa của câu hỏi: trong một không gian metric, chỉ có $O(n)$ khoảng cách là khác nhau đáng kể, trong số $\Omega(n^2)$ khoảng cách khả dĩ.

    Gợi ý lời giải: Gọi $I$ là tập các số nguyên công hiệu. Gọi $J$ là tập con tối đại (maximal) của $I$ sao cho với bất kì $i_0\not= i_1\in J$, $|i_1-i_0| \geq 2$. Ta có nhận xét: $|I| \leq 2|J|$.

    Việc còn lại là chứng minh $J$ có tối đa $n-1$ phần tử. Ta xây dựng một đồ thị có trọng số cạnh $F$ với tập đỉnh $X$ và tập cạnh như sau: với mỗi phần tử $j\in J$, gọi $(x,y)$ là hai điểm mà $d(x,y)\in [2^j,2^{j+1}]$, ta thêm cạnh $(x,y)$ với trọng số $w(x,y) = d(x,y)$ vào đồ thị $F$.

    Lemma 1: $F$ là đồ thị không có chu trình.

     
    Chứng minh: Gọi $C$ là một chu trình của $F$, và $(x,y)$ là cạnh có trọng số lớ nhất. Dựa vào cách xây dựng tập $J$, ta có thể chứng minh được:

    $w(x,y) > \sum_{e\in E(C)\setminus \{(x,y)\}}w(e)$

    Từ điều kiện $d(.)$ là một hàm khoảng cách, ta suy ra $w(x,y) \leq \sum_{e\in E(C)\setminus \{(x,y)\}}w(e)$, từ đó ta thu được phản chứng.


    Do $F$ không có chu trình, nó có tối đa $n-1$ cạnh, mỗi cạnh ứng với một phần tử của $J$. Do đó, $|J|\leq n-1$ (dpcm).

    Facebook Comments

    « Older entries § Newer entries »