กราฟ Turán
กราฟ Turán T(13,4)
ตั้งชื่อตาม	ปาล ตูรัน
จุดยอด	${\displaystyle n}$
ขอบ	~${\displaystyle \left(1-{\frac {1}{r}}\right){\frac {n^{2}}{2}}}$
รัศมี	${\displaystyle \left\{{\begin{array}{ll}\infty &r=1\\2&r\leq n/2\\1&{\text{otherwise}}\end{array}}\right.}$
เส้นผ่านศูนย์กลาง	${\displaystyle \left\{{\begin{array}{ll}\infty &r=1\\1&r=n\\2&{\text{otherwise}}\end{array}}\right.}$
เส้นรอบวง	${\displaystyle \left\{{\begin{array}{ll}\infty &r=1\vee (n\leq 3\wedge r\leq 2)\\4&r=2\\3&{\text{otherwise}}\end{array}}\right.}$
หมายเลขสี	${\displaystyle r}$
สัญกรณ์	${\displaystyle T(n,r)}$
ตารางกราฟและพารามิเตอร์

กราฟTuránซึ่งเขียนแทนด้วยเป็นกราฟหลายส่วนสมบูรณ์โดยเกิดจากการแบ่งเซตของจุดยอดออกเป็นเซตย่อยที่มีขนาดเท่ากันมากที่สุดเท่าที่จะเป็นไปได้ แล้วเชื่อมจุดยอดสองจุดด้วยเส้นขอบก็ต่อเมื่อจุดยอดทั้งสองนั้นอยู่ในเซตย่อยที่แตกต่างกัน โดยที่และคือผลหารและเศษเหลือของการหารด้วย(ดังนั้น) กราฟจะมีรูปแบบและจำนวนเส้นขอบคือ ${\displaystyle T(n,r)}$${\displaystyle n}$${\displaystyle r}$${\displaystyle q}$${\displaystyle s}$${\displaystyle n}$${\displaystyle r}$${\displaystyle n=qr+s}$${\displaystyle K_{q+1,q+1,\ldots ,q,q}}$

${\displaystyle \left(1-{\frac {1}{r}}\right){\frac {n^{2}-s^{2}}{2}}+{s \choose 2}}$.

สำหรับกราฟนี้ จำนวนขอบสามารถระบุได้อย่างกระชับยิ่งขึ้นว่ากราฟนี้มีเซตย่อยขนาดและเซตย่อยขนาดแต่ละจุดยอดมีดีกรีหรือ กราฟ นี้เป็นกราฟปกติก็ ต่อเมื่อ หารลงตัวด้วย(นั่นคือเมื่อ) ${\displaystyle r\leq 7}$${\displaystyle \left\lfloor \left(1-{\frac {1}{r}}\right){\frac {n^{2}}{2}}\right\rfloor }$${\displaystyle s}$${\displaystyle q+1}$${\displaystyle r-s}$${\displaystyle q}$${\displaystyle n-q-1}$${\displaystyle n-q}$${\displaystyle n}$${\displaystyle r}$${\displaystyle s=0}$

กราฟ Turán ตั้งชื่อตามPál Turánซึ่งใช้กราฟเหล่านี้ในการพิสูจน์ทฤษฎีบทของ Turánซึ่งเป็นผลลัพธ์ที่สำคัญของทฤษฎีกราฟเอ็กซ์ตรีม

ตามหลักการรังนกพิราบ เซตของ จุดยอด r  + 1 จุดในกราฟ Turán จะมีจุดยอดสองจุดในเซตย่อยของการแบ่งส่วนเดียวกัน ดังนั้น กราฟ Turán จึงไม่มีคลิกขนาด  r  + 1 ตามทฤษฎีบทของ Turán กราฟ Turán มีจำนวนขอบสูงสุดที่เป็นไปได้ในบรรดา กราฟที่ไม่มีคลิก ( r + 1) จุดยอดทั้งหมดที่มี n  จุดยอดKeevash & Sudakov (2003)แสดงให้เห็นว่ากราฟ Turán ยังเป็น กราฟที่ไม่มีคลิก ( r + 1) จุดยอดเพียงกราฟเดียวที่มีอันดับ nซึ่งเซตย่อยของจุดยอด α nจุดยอดครอบคลุมขอบอย่างน้อยถ้า α ใกล้เคียงกับ 1 มากพอ^{[ 1 ]}ทฤษฎีบทErdős–Stoneขยายทฤษฎีบทของ Turán โดยจำกัดจำนวนขอบในกราฟที่ไม่มีกราฟ Turán คงที่เป็นกราฟย่อย จากทฤษฎีบทนี้ สามารถพิสูจน์ขอบเขตที่คล้ายกันในทฤษฎีกราฟสุดขั้วสำหรับกราฟย่อยที่ถูกยกเว้นใดๆ ได้ โดยขึ้นอยู่กับจำนวนสีของกราฟย่อยนั้น ${\displaystyle {\frac {r\,{-}\,1}{3r}}(2\alpha -1)n^{2}}$

การเลือกค่าพารามิเตอร์r หลายค่า ในกราฟ Turán นำไปสู่กราฟที่น่าสนใจหลายแบบ ซึ่งได้รับการศึกษาแยกกันมาแล้ว

กราฟ Turán T (2 n , n ) สามารถสร้างได้โดยการลบการจับคู่ที่สมบูรณ์แบบออกจากกราฟสมบูรณ์K _{2 n}ดังที่Roberts (1969)แสดงให้เห็น กราฟนี้มีboxicityเท่ากับnพอดี บางครั้งเรียกว่ากราฟRoberts ^{[ 2 ]}กราฟนี้ยังเป็นโครงร่าง 1 มิติ ของcross-polytope nมิติด้วย ตัวอย่างเช่น กราฟT (6,3) =  K _2,2,2คือกราฟ octahedralซึ่งเป็นกราฟของทรงแปดเหลี่ยม ปกติ หาก คู่รัก nคู่ไปงานเลี้ยง และแต่ละคนจับมือกับทุกคนยกเว้นคู่ของตน กราฟนี้จะอธิบายเซตของการจับมือที่เกิดขึ้น ด้วยเหตุนี้จึงเรียกว่ากราฟงานเลี้ยงค็อกเทลด้วย

กราฟ Turán T ( n , 2) เป็นกราฟสองส่วนสมบูรณ์และเมื่อnเป็นจำนวนคู่ จะเป็นกราฟ Mooreเมื่อrเป็นตัวหารของnกราฟ Turán จะเป็นกราฟสมมาตรและมีความสม่ำเสมออย่างเข้มแข็งแม้ว่าผู้เขียนบางคนจะถือว่ากราฟ Turán เป็นกรณีง่ายๆ ของความสม่ำเสมออย่างเข้มแข็ง และจึงไม่รวมอยู่ในนิยามของกราฟที่มีความสม่ำเสมออย่างเข้มแข็งก็ตาม

กราฟ Turán สามารถมีคลิกสูงสุดได้จำนวนมากแบบเลขชี้กำลัง ซึ่งหมายความว่ากราฟประเภทนี้ไม่ได้มี^คลิกน้อยตัวอย่างเช่น กราฟ Turán มีคลิกสูงสุด^3a 2b โดยที่ 3a +  2b =  n  และ b ≤  2; คลิกสูงสุดแต่ละคลิกเกิดจากการเลือกจุดยอดหนึ่งจุดจากเซตย่อยของการแบ่งกลุ่ม นี่คือจำนวนคลิกสูงสุดที่มากที่สุดที่เป็นไปได้ในบรรดา กราฟ nจุดยอดทั้งหมด โดยไม่คำนึงถึงจำนวนขอบในกราฟ กราฟเหล่านี้บางครั้งเรียกว่ากราฟMoon–Moser ^{[ 3 ]}${\displaystyle T(n,\lceil n/3\rceil )}$

กราฟ Turán ทุกกราฟเป็นกราฟโคกราฟกล่าวคือ สามารถสร้างขึ้นจากจุดยอดแต่ละจุดโดยใช้ลำดับของ การดำเนิน การรวมและ เติม เต็มที่ไม่ซ้ำกันโดยเฉพาะอย่างยิ่ง ลำดับดังกล่าวสามารถเริ่มต้นได้โดยการสร้างเซตอิสระแต่ละเซตของกราฟ Turán เป็นการรวมที่ไม่ซ้ำกันของจุดยอดที่แยกออกจากกัน จากนั้น กราฟโดยรวมจะเป็นส่วนเติมเต็มของการรวมที่ไม่ซ้ำกันของส่วนเติมเต็มของเซตอิสระเหล่านี้

Chao & Novacky (1982)แสดงให้เห็นว่ากราฟ Turán มีเอกลักษณ์เฉพาะตัวทางสี : ไม่มีกราฟอื่นใดที่มีพหุนามสี เดียวกัน Nikiforov (2005) ใช้กราฟ Turán เพื่อให้ได้ขอบเขตล่างสำหรับผลรวมของค่าลักษณะเฉพาะที่kของกราฟและส่วนเติมเต็ม^{[ 4 ]}

Falls, Powell & Snoeyink (2003)พัฒนาอัลกอริทึมที่มีประสิทธิภาพสำหรับการค้นหากลุ่มยีนออร์โธล็อกในข้อมูลจีโนม โดยแสดงข้อมูลเป็นกราฟและค้นหากราฟย่อย Turán ขนาดใหญ่^{[ 5 ]}

กราฟ Turán ยังมีคุณสมบัติที่น่าสนใจบางอย่างที่เกี่ยวข้องกับทฤษฎีกราฟเชิงเรขาคณิตPór & Wood (2005)ให้ขอบเขตล่างของ Ω(( rn ) ^3/4 ) สำหรับปริมาตร ของการฝังกราฟ Turán ลงในกริดสามมิติใดๆ^{[ 6 ]} Witsenhausen (1974)ตั้งข้อสันนิษฐานว่าผลรวมสูงสุดของระยะทางกำลังสองระหว่าง จุด nจุดที่มีเส้นผ่านศูนย์กลางหนึ่งหน่วยในR ^dจะเกิดขึ้นสำหรับการกำหนดค่าที่เกิดจากการฝังกราฟ Turán ลงบนจุดยอดของซิมเพล็กซ์ปกติ^{[ 7 ]}

กราฟG ที่มี nจุดยอดเป็นกราฟย่อยของกราฟ Turán T ( n , r ) ก็ต่อเมื่อGยอมรับการระบายสีที่เท่าเทียมกันด้วยrสี การแบ่งกราฟ Turán ออกเป็นเซตอิสระสอดคล้องกับการแบ่งGออกเป็นกลุ่มสี โดยเฉพาะอย่างยิ่ง กราฟ Turán เป็น กราฟ nจุดยอดสูงสุดเพียงหนึ่งเดียวที่มีการระบายสีที่เท่าเทียมกันด้วยrสี

วิกิมีเดียคอมมอนส์มีสื่อที่เกี่ยวข้องกับกราฟ Turán

• ไวส์สไตน์, เอริก ดับเบิลยู. "กราฟปาร์ตี้ค็อกเทล" . แมทเวิลด์ .
• ไวส์สไตน์, เอริค ดับเบิลยู. "กราฟทรงแปดเหลี่ยม" . MathWorld .
• ไวส์สไตน์, เอริก ดับเบิลยู. "ทูรัน กราฟ" . แมทเวิลด์ .
• ฐานข้อมูลการออกแบบการครอบคลุม – ฐานข้อมูลไฮเปอร์กราฟสุดขั้วและการออกแบบการครอบคลุมที่ดูแลโดยคลาส มาร์กสตรอม