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

Đồ 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 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 ${\displaystyle W_{7}}$

Chứng minh

• Với đồ thị chu trình ${\displaystyle 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 ${\displaystyle Q_{n}}$ là đồ thị cạnh đơn vị theo n.

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

n=2, ${\displaystyle 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ử ${\displaystyle Q_{n}}$ là đồ thị cạnh đơn vị, ta chứng minh rằng ${\displaystyle Q_{n+1}}$ cũng là đồ thị cạnh đơn vị.

Thật vậy, ${\displaystyle Q_{n+1}}$ cấu trúc bởi hai đồ thị ${\displaystyle 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ẽ ${\displaystyle 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ị ${\displaystyle 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ị ${\displaystyle 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 ${\displaystyle Q_{n}}$ có ${\displaystyle 2^{n}}$ đỉnh và ${\displaystyle 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à:

${\displaystyle {\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à:

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

Chú thích

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.