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

Đồ 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.

Đồ 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.

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

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

• Đồ thị chu trình
• Đồ thị lưới
• Đồ thị siêu khối
• Đồ thị Heawood
• Đồ thị Petersen
• Đồ thị bánh xe $W_{7}$

Chứng minh

• Với đồ thị chu trình $C_{n}$, 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ị.
• Ta chứng minh quy nạp đồ thị siêu khối $Q_{n}$ là đồ thị cạnh đơn vị theo n.

n=1, $Q_{1}$ có dạng một đoạn thẳng độ dài bằng một.

n=2, $Q_{2}$ có dạng một hình thoi bất kì với độ dài cạnh bằng một.

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

Thật vậy, $Q_{n+1}$ cấu trúc bởi hai đồ thị $Q_{n}$ 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ẽ $Q_{n+1}$ dưới dạng đồ thị cạnh đơn vị bằng cách sau:

Đồ thị cạnh đơn vị G₂ được biểu diễn bằng cách tịnh tiến đồ thị cạnh đơn vị G một khoảng có độ dài một đơn vị; trong hình vẽ mũi tên màu đỏ chỉ sự tịnh tiến.

vẽ một đồ thị $Q_{n}$ 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ị $Q'_{n}$, cuối cùng ta nối các đỉnh tương ứng của hai đồ thị này lại. Trong ví dụ minh họa sau, đồ thị cạnh đơn vị G₂ được biểu diễn bằng cách tịnh tiến đồ thị cạnh đơn vị G₁ một khoảng có độ dài một đơn vị. Trong hình vẽ mũi tên màu đỏ chỉ sự tịnh tiến.

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 $Q_{n}$ có $2^{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}}$.

Liên kết ngoài

• Venkatasubramanian, Suresh, “Problem 39: Distances among Point Sets in R² and R³”, The Open Problems Project, Bản gốc lưu trữ ngày 30 tháng 8 năm 2006, truy cập ngày 8 tháng 12 năm 2011.
• Weisstein, Eric W., "Unit-Distance Graph", MathWorld.