Đồ thị cạnh đơn vị

Bách khoa toàn thư mở Wikipedia
Bước tới: menu, tìm kiếm
Đồ thị Petersen là đồ thị cạnh đơn vị, nó có thể vẽ trong mặt phẳng với độ dài tất cả các cạnh đều bằng một.

Đồ thị cạnh đơn vị (tiếng Anh: unit distance graph) là đồ thị mà ta có thể vẽ nó trong mặt phẳng Euclid với tất cả các cạnh có độ dài bằng một.

Hình vẽ của đồ thị siêu khối Q4 dưới dạng đồ thị cạnh đơn vị.

Một số đồ thị cạnh đơn vị:

Bài toán đếm số khoảng cách đơn vị[sửa | sửa mã nguồn]

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 Q_n2^n đỉnh và n\cdot 2^{n-1} cạnh. Đó là bằng chứng để củng cố giả thiết rằng một đồ thị cạnh đơn vị với n đỉnh, có ít nhất là:

\frac{n}{2}\cdot log(n)

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à:

n^{\frac{4}{3}}.

Chú thích[sửa | sửa mã nguồn]

Liên kết ngoài[sửa | sửa mã nguồn]