Khác biệt giữa bản sửa đổi của “Thành viên:Wild Lion/Nháp”

*[[Đồ thị lưới]]

*[[Đồ thị siêu khối]]

*[[Đồ thị Petersen]]

*[[Đồ thị bánh xe]] <math> W_7 </math>

 

 

*Với đồ thị chu trình <math>C_n</math>, ta có thể biểu diễn nó trên mặt phẳng Euclid dưới dạng đa giác đều có ''n'' cạnh, mỗi cạnh có độ dài một đơn vị.

::Giả sử <math>Q_n</math> là đồ thị cạnh đơn vị, ta chứng minh rằng <math>Q_{n+1}</math> cũng là đồ thị cạnh đơn vị.

::Thật vậy, <math>Q_{n+1}</math> cấu trúc bởi hai đồ thị <math>Q_n</math> với từng cặp đỉnh tương ứng của chúng được nối với nhau. Như vậy ta có thể vẽ <math>Q_{n+1}</math> dưới dạng đồ thị cạnh đơn vị bằng cách sau:

 

== 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.

 

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]]