Đồ thị Turán

Đồ thị Turán T(n,r) là một đồ thị nhiều phía đầy đủ tạo thành bằng cách chia n đỉnh thành r tập con, với kích thước gần nhau nhất có thể, và nối hai đỉnh bằng một cạnh nếu và chỉ nếu chúng thuộc hai tập con khác nhau. Cụ thể, nếu đặt s = n mod r thì đồ thị Turán gồm s tập con chứa ⌈n/r⌉ đỉnh, và r − s tập con với ⌊n/r⌋ phần tử. Tức là, nó là một đồ thị r phía đầy đủ, với mỗi đỉnh có bậc n − ⌈n/r⌉ hoặc n − ⌊n/r⌋. Tổng số cạnh của T(n,r) là

Đồ thị Turán
Đồ thị Turán T(13,4)
Đặt tên theo	Pál Turán
Đỉnh	n
Cạnh	$\sim {\frac {(r-1)n^{2}}{2r}}$
Bán kính	$\left\{{\begin{array}{ll}\infty &r=1\\2&r\leq n/2\\1&\mathrm {kh{\acute {a}}c} \end{array}}\right.$
Đường kính	$\left\{{\begin{array}{ll}\infty &r=1\\1&r=n\\2&\mathrm {kh{\acute {a}}c} \end{array}}\right.$
Chu vi nhỏ nhất	$\left\{{\begin{array}{ll}\infty &r=1\vee (n\leq 3\wedge r\leq 2)\\4&r=2\\3&\mathrm {kh{\acute {a}}c} \end{array}}\right.$
Sắc số	r
Ký hiệu	T(n,r)
Danh sách đồ thị và thông số

${\frac {1}{2}}(n^{2}-s\lceil n/r\rceil ^{2}-(r-s\lfloor n/r\rfloor ^{2})={\frac {(r-1)(n^{2}-s^{2})}{2r}}+{\binom {s}{2}}\leq {\frac {(r-1)n^{2}}{2r}}.$

Đồ thị Turán là một đồ thị chính quy, nếu n chia hết cho r.

Định lý Turán

Đồ thị Turán được đặt tên theo nhà toán học Hungary Pál Turán, người tạo ra chúng để chứng minh định lý Turán, một kết quả quan trọng trong lý thuyết đồ thị cực trị.

Bằng nguyên lý Dirichlet, mỗi tập chứa r + 1 đỉnh trong đồ thị Turán chứa hai đỉnh trong một tập con phân hoạch; vì thế, đồ thị Turán không chứa clique nào có kích thước r + 1. Theo định lý Turán, đồ thị Turan có số cạnh tối đa trong số tất cả những đồ thị n đỉnh mà không có clique r + 1. Keevash và Sudakov chỉ ra rằng đồ thị Turán cũng là đồ thị bậc n không có clique r + 1 duy nhất mà trong đó mọi tập con chứa αn đỉnh bao gồm ít nhất

${\frac {r\,{-}\,1}{3r}}(2\alpha -1)n^{2}$

cạnh, nếu α đủ gần với 1. Định lý Erdős–Stone mở rộng định lý Turán bằng giới hạn số cạnh của một đồ thị không chứa đồ thị con nào là đồ thị Turán. Bằng định lý này, những chặn tương tự trong lý thuyết đồ thị cực trị có thể được chứng minh cho bất kỳ đồ thị con nào, dựa trên sắc số của đồ thị con.

Trường hợp đặc biệt

Một bát diện đều, có các cạnh và đỉnh tạo thành K_2,2,2, là một đồ thị Turán T(6,3). Những đỉnh không được nối nằm trong cùng một tập phân hoạch và được tô cùng màu trong hình chiếu này.

Một số giá trị của tham số r của đồ thị Turán dẫn đến một số đồ thị nổi bật từng được nghiên cứu độc lập.

Đồ thị Turán T(2n,n) có thể được xây dựng bằng cách bỏ một cặp ghép hoàn hảo từ một đồ thị đầy đủ K_2n. Đồ thị này là 1-bộ khung của một cross-polytope n chiều; ví dụ, đồ thị T(6,3) = K_2,2,2 là một đồ thị của hình bát diện đều. Nếu n cặp đôi đến một buổi tiệc và mỗi người bắt tay với tất cả người khác trừ bạn trai hay bạn gái của người đó, thì đồ thị biểu diễn những cái bắt tay chính là đồ thị Turán T(2n,n); vì thế nó còn được gọi là đồ thị tiệc cocktail.

Đồ thị Turán T(n,2) là một đồ thị hai phía đầy đủ và là một đồ thị Moore nếu n chẵn. Nếu r là ước của n, đồ thị Turán là đối xứng và chính quy mạnh, mặc dù một số tác giả xem đồ thị Turán là trường hợp tầm thường của tính chính quy mạnh và loại chúng khỏi định nghĩa của đồ thị chính quy mạnh.

Đồ thị Turán T(n,⌈n/3⌉) có 3^a2^b clique cực đại, trong đó 3a + 2b = n và b ≤ 2; mỗi clique cực đại có thể tạo bằng cách chọn một đỉnh từ mỗi tập phân hoạch. Moon và Moser chứng minh rằng đây là số clique cực đại lớn nhất có thể trong tất cả đồ thị n đỉnh bất kể số cạnh; những đồ thị này còn được gọi là đồ thị Moon–Moser.

Tính chất khác

Mọi đồ thị Turán là một cograph; tức là nó có thể được xây dựng từ các đỉnh bằng một chuỗi các phép hợp rời nhau và phần bù. Cụ thể, ta có thể bắt đầu bằng cách xây dựng mỗi tập riêng biệt của đồ thị như là một hợp rời các đỉnh riêng biệt. Sau đó, đồ thị cần tạo là phần bù của hợp rời của phần bù các tập phân hoạch đó.

Chao và Novacky chứng minh rằng đồ thị Turán là duy nhất về mặt màu sắc: không đồ thị nào khác có cùng đa thức màu. Nikiforov dùng đồ thị Turán để cho ra một chặn dưới cho tổng của trị riêng thứ k của một đồ thị và phần bù của nó.

Một đồ thị G với n đỉnh là một đồ thị con của một đồ thị Turán T(n,r) khi và chỉ khi G có một cách tô màu công bằng với r màu. Sự phân hoàn đồ thị Turán thành r tập khác nhau tương ứng với sự phân hoạch G theo màu. Cụ thể hơn, đồ thị Turán T(n,r) là đồ thị n đỉnh cực đại duy nhất với một phép tô màu công bằng với r màu.

Liên kết ngoài

• Weisstein, Eric W., "Cocktail Party Graph", MathWorld.
• Weisstein, Eric W., "Octahedral Graph", MathWorld.
• Weisstein, Eric W., "Turán Graph", MathWorld.