กราฟของ Tietze
| กราฟของ Tietze | |
|---|---|
 กราฟ Tietze | |
| จุดยอด | 12 |
| ขอบ | 18 |
| รัศมี | 3 |
| เส้นผ่านศูนย์กลาง | 3 |
| เส้นรอบวง | 3 |
| ออโตมอร์ฟิซึม | 12 ( D ) |
| หมายเลขสี | 3 |
| ดัชนีสี | 4 |
| คุณสมบัติ | คิวบิกสแนร์ค |
| ตารางกราฟและพารามิเตอร์ | |
ใน สาขา คณิตศาสตร์ของทฤษฎีกราฟกราฟของ Tietzeเป็นกราฟลูกบาศก์แบบไม่มี ทิศทางที่มี 12 จุดยอดและ 18 ขอบ ตั้งชื่อตามHeinrich Franz Friedrich Tietzeผู้ซึ่งแสดงให้เห็นในปี 1910 ว่าแถบโมเบียสสามารถแบ่งออกเป็นหกส่วนที่สัมผัสกันทั้งหมด – สามส่วนตามขอบของแถบและสามส่วนตามเส้นกึ่งกลาง – และด้วยเหตุนี้กราฟที่ฝัง อยู่ ในแถบโมเบียสอาจต้องใช้หกสี[ 1 ] ส่วนของขอบของบริเวณที่ Tietze แบ่งย่อย (รวมถึงส่วนตามขอบของแถบโมเบียสเอง) ก่อให้เกิดการฝังของกราฟ Tietze
ความสัมพันธ์กับกราฟของปีเตอร์เซน
กราฟของ Tietze อาจสร้างขึ้นจากกราฟ Petersenโดยการแทนที่จุดยอดจุดหนึ่งด้วยรูปสามเหลี่ยม[ 2 ] [ 3 ] เช่นเดียวกับกราฟ Tietze กราฟ Petersen สร้างขอบเขตของพื้นที่สัมผัสกันหกแห่ง แต่บนระนาบเชิงโปรเจกทีฟแทนที่จะเป็นแถบโมเบียส หากเจาะรูจากส่วนย่อยของระนาบเชิงโปรเจกทีฟนี้ ล้อมรอบจุดยอดจุดเดียว จุดยอดที่ถูกล้อมรอบจะถูกแทนที่ด้วยรูปสามเหลี่ยมของขอบเขตพื้นที่รอบรู ทำให้ได้โครงสร้างกราฟ Tietze ที่อธิบายไว้ก่อนหน้านี้
ความเป็นแฮมิลตัน
ทั้งกราฟของ Tietze และกราฟของ Petersen เป็นกราฟที่ไม่ใช่แฮมิลโทเนียนสูงสุด กล่าวคือไม่มีวัฏจักรแฮมิลโทเนียนแต่จุดยอดสองจุดใดๆ ที่ไม่ติดกันสามารถเชื่อมต่อกันด้วยเส้นทางแฮมิลโท เนียน ได้[ 2 ]กราฟของ Tietze และกราฟของ Petersen เป็น กราฟลูกบาศก์ที่ไม่ใช่แฮมิลโทเนียน ที่เชื่อมต่อกันด้วยจุดยอด 2 จุด เพียงสองกราฟเท่านั้น ที่มีจุดยอด 12 จุดหรือน้อยกว่า[ 4 ]
ต่างจากกราฟของ Petersen กราฟของ Tietze ไม่ใช่กราฟไฮโปแฮมิลโทเนียนกล่าวคือ การลบจุดยอดสามเหลี่ยมหนึ่งในสามจุดจะทำให้ได้กราฟที่เล็กลง แต่ยังคงไม่ใช่กราฟแฮมิลโทเนียน
การลงสีขอบและการจับคู่ที่สมบูรณ์แบบ
การระบายสีขอบของกราฟ Tietze ต้องใช้สี่สี นั่นคือ ดัชนีสีของมันคือ 4 หรือกล่าวอีกนัยหนึ่ง ขอบของกราฟ Tietze สามารถแบ่งออกเป็นสี่คู่แต่ไม่น้อยกว่านั้น
กราฟของ Tietze ตรงกับส่วนหนึ่งของคำจำกัดความของsnark : เป็นกราฟลูกบาศก์ที่ไม่มีสะพานและไม่สามารถระบายสีขอบด้วย 3 สีได้ อย่างไรก็ตาม ผู้เขียนส่วนใหญ่จำกัด snark ไว้เฉพาะกราฟที่ไม่มี 3-cycle ดังนั้นกราฟของ Tietze จึงไม่ถือว่าเป็น snark โดยทั่วไป ถึงกระนั้น มันก็เป็นไอโซมอร์ฟิกกับกราฟ J snark ดอกไม้จำนวนอนันต์ ที่ R. Isaacsแนะนำในปี 1975 [ 5 ]
ต่างจากกราฟ Petersen กราฟ Tietze สามารถครอบคลุมได้ด้วยการจับคู่ที่สมบูรณ์แบบ สี่คู่ คุณสมบัตินี้มีบทบาทสำคัญในการพิสูจน์ว่าการทดสอบว่ากราฟสามารถครอบคลุมได้ด้วยการจับคู่ที่สมบูรณ์แบบสี่คู่หรือไม่นั้นเป็น ปัญหา NP - complete [ 6 ]
คุณสมบัติเพิ่มเติม
กราฟของ Tietze มีจำนวนสี 3, ดัชนีสี 4, เส้นรอบวง 3 และเส้นผ่านศูนย์กลาง 3 จำนวนความเป็นอิสระคือ 5 กลุ่มออโตมอร์ฟิซึม ของกราฟนี้ มีอันดับ 12 และสมมาตรกับกลุ่มไดเฮดรัล D₆ เป็น กลุ่มสมมาตรของรูปหกเหลี่ยมปกติ (รวมทั้งการหมุนและการสะท้อน) กลุ่มนี้มีวงโคจรขนาด 3 สองวงและวงโคจรขนาด 6 หนึ่งวงบนจุดยอด ดังนั้นกราฟนี้จึงไม่ใช่กราฟที่ถ่ายทอดจุดยอดได้
แกลเลอรี่
จำนวนสีของกราฟ Tietze คือ 3
ดัชนีสีของกราฟ Tietze คือ 4
กราฟ Tietze มีจุดตัด 2 จุด และเป็นกราฟระนาบ 1จุด
การฝังตัวแบบสามมิติของกราฟ Tietze
ดูเพิ่มเติม
- กราฟ Dürerและกราฟ Franklinเป็นกราฟลูกบาศก์ที่มี 12 จุดยอดอีกสองชนิด
หมายเหตุ
- ↑ Tietze, Heinrich (1910), "Einige Bemerkungen zum Problem des Kartenfärbens auf einseitigen Flächen " [ Some remarks on the problems of map colouring on one-side surfaces ] (PDF) , DMV Annual Report , 19 : 155– 159
- 1 2 Clark, L.; Entringer, R. (1983), "กราฟที่ไม่ใช่แฮมิลโทเนียนสูงสุดที่เล็กที่สุด", Periodica Mathematica Hungarica , 14 (1): 57– 68, doi : 10.1007/BF02023582 , S2CID 122218690
- ↑ ไวส์สไตน์, เอริก ดับเบิลยู. "กราฟของทีซ " แมทเวิลด์ .
- ↑ปุณณิม, นรงค์; แสนพลภัทร, วรพร; ไทยแท, เสริมศรี (2007), "กราฟลูกบาศก์แฮมิลโทเนียนเกือบสมบูรณ์" (PDF) , วารสารนานาชาติวิทยาการคอมพิวเตอร์และความปลอดภัยเครือข่าย , 7 (1): 83– 86
- ↑ Isaacs, R. (1975), "ตระกูลอนันต์ของกราฟไตรวาเลนต์ที่ไม่ใช่กราฟธรรมดาซึ่งไม่สามารถระบายสีแบบ Tait ได้", Amer. Math. Monthly , 82 (3), Mathematical Association of America: 221– 239, doi : 10.2307/2319844 , JSTOR 2319844 .
- ↑ Esperet, L.; Mazzuoccolo, G. (2014), "เกี่ยวกับกราฟลูกบาศก์ที่ไม่มีสะพานซึ่งเซตขอบไม่สามารถครอบคลุมได้ด้วยการจับคู่ที่สมบูรณ์แบบสี่คู่", Journal of Graph Theory , 77 (2): 144– 157, arXiv : 1301.6926 , doi : 10.1002/jgt.21778 , MR 3246172 , S2CID 15284123 .