Khác biệt giữa bản sửa đổi của “Thành viên:Wild Lion/Nháp”
Nội dung được xóa Nội dung được thêm vào
Dòng 80:
:::vẽ một đồ thị <math>Q_n</math> dưới dạng đồ thị cạnh đơn vị, rồi vị tự nó đi một khoảng cách đúng bằng một, được đồ thị <math>Q'_n</math>, cuối cùng ta nối các đỉnh tương ứng của hai đồ thị này lại.
== Bài toán đếm số khoảng cách đơn vị ==
Năm 1946, Paul Erdos đề ra bài toán cho tập ''n'' điểm bất kì, có nhiều nhất bao nhiêu điểm trong số chúng có khoảng cách bằng một đơn vị. Trong [[lí thuyết đồ thị]], vấn đề này được phát biểu: một đồ thị cạnh đơn vị với ''n'' đỉnh có nhiều nhất bao nhiêu cạnh.
[[Đồ thị siêu khối]] <math>Q_n</math> có <math>2^n</math> đỉnh và <math>n\cdot 2^{n-1}</math> cạnh. Điều đó chứng tỏ là một đồ thị cạnh đơn vị với ''n'' đỉnh, có ít nhất là:
::<math>\frac{n}{2}\cdot log(n)</math>
cạnh.
Năm 1984, Joel Spencer, Endre Szemorédi và William Trotter đưa ra một cận dưới cho đáp số của bài toán trên là:
::<math>n^{\frac{4}{3}}</math>.
[[de:Einheitsdistanz-Graph]]
| |||