Xem mã nguồn của Đồ thị cạnh đơn vị

[[Hình:Petersen graph, unit distance.svg|thumb|150px|phải|[[Đồ 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:Hypercubestar.svg|thumb|150px|Hình vẽ của [[đồ thị siêu khối]] ''Q''<sub>4</sub> 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]] <math> W_7 </math>

{{hidden begin|title=Chứng minh}}

*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ị.
*Ta chứng minh quy nạp đồ thị siêu khối <math>Q_n</math> là đồ thị cạnh đơn vị theo ''n''.
::''n''=1, <math>Q_1</math> có dạng một đoạn thẳng độ dài bằng một.
::''n''=2, <math>Q_2</math> có dạng một [[hình thoi]] bất kì với độ dài cạnh bằng một.
::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:

[[Hình:UDG G2 from G1.png|vừa|170px|trái|Đồ thị cạnh đơn vị ''G''<sub>2</sub> đượ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ị <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. Trong ví dụ minh họa sau, đồ thị cạnh đơn vị ''G''<sub>2</sub> được biểu diễn bằng cách tịnh tiến đồ thị cạnh đơn vị ''G''<sub>1</sub> 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.
{{hidden end}}

== 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. Đó 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à:
::<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>.

==Chú thích==
{{Tham khảo}}

== Liên kết ngoài ==
*{{chú thích
 | author = Venkatasubramanian, Suresh
 | contribution = Problem 39: Distances among Point Sets in '''R'''<sup>2</sup> and '''R'''<sup>3</sup>
 | title = The Open Problems Project
 | url = http://maven.smith.edu/~orourke/TOPP/P39.html
 | access-date = 2011-12-08
 | archive-date = 2006-08-30
 | archive-url = https://web.archive.org/web/20060830093723/http://maven.smith.edu/~orourke/TOPP/P39.html
 }}.
*{{mathworld|urlname=Unit-DistanceGraph|title=Unit-Distance Graph}}

[[Thể loại:Lý thuyết đồ thị]]
[[Thể loại:Vấn đề chưa được giải quyết trong toán học]]