รงคเลขของกราฟเคย์เลย์ผลบวก
- ชื่อนักเรียนผู้จัดทำโครงงานวิทยาศาสตร์
ต้นกล้า วิบูลย์เลิศวัฒนะ, กฤติน วามานนท์, เมธาวิน พูลเพิ่ม
- อาจารย์ที่ปรึกษาโครงงานวิทยาศาสตร์
จักรพล สาใจ, พร้อมพงศ์ กวีกิจธนา
- โรงเรียนที่กำกับดูแลโครงงานวิทยาศาสตร์
- ปีที่จัดทำโครงงานวิทยาศาสตร์
บทคัดย่อโครงงานวิทยาศาสตร์
ทฤษฎีกราฟเป็นสาขาวิชาแขนงหนึ่งของคณิตศาสตร์ที่มีประโยชน์และน่าสนใจเป็นอย่างมาก ทว่ายังไม่ได้รับความสนใจอย่างที่ควร ทั้งที่สามารถนำไปประยุกต์ใช้ได้อย่างหลากหลาย เช่น การระบายสีแผนที่ จัดรูปแบบการส่งพัสดุ การจัดการคลื่นสัญญาณโทรศัพท์ ฯลฯ
คณะผู้จัดทำจึงสนใจและศึกษารูปแบบกราฟหนึ่งที่มีเงื่อนไขและความซับซ้อนเป็นอย่างยิ่ง คือ กราฟเคย์เลย์ (Cayley graph) หรือเราอาจจะรู้จักในอีกหลาย ๆ ชื่อ เช่น Cayley color graph, Cayley diagram, group diagram หรือ color group ซึ่งคือกราฟที่ถูกเข้ารหัสโครงสร้างทางนามธรรมของกลุ่ม (group) โดยที่นิยามนั้นถูกกำหนดโดย ทฤษฎีของเคย์เลย์ (Cayley’s theorem) และโครงงานในครั้งนี้เรามีวัตถุประสงค์เพื่อศึกษาขอบเขตของรงคเลข (chromatic number) และจำนวนคลีก (clique number) ของกราฟเคย์เลย์ผลบวก มากไปกว่านั้น เรายังยกตัวอย่าง กราฟเคย์เลย์ผลบวกที่มีรงคเลขที่สอดคล้องกับขอบเขต
ในการหาขอบเขตของรงคเลขและจำนวนคลีกนั้น เราศึกษาเฉพาะกราฟเคย์เลย์ผลบวกที่มีจำนวนจุดยอด ได้แก่ จำนวนจุดยอดเป็นจำนวนเฉพาะคี่ และเซตของการระบายสีที่มีสมาชิกมากกว่าหรือเท่ากับ 1 เท่านั้น
ผลการดำเนินงานทั้งหมดดังนี้
ทฤษฎีบท ถ้า p เป็นจำนวนเฉพาะคี่ แล้ว χ(Cay^+(Z_p, {a}), a ∈ Z_p) = 2
ทฤษฎีบท ถ้า p เป็นจำนวนเฉพาะคี่ แล้ว χ(Cay^+(Z_p, {a,b}), a,b ∈ Z_p) = 2
ทฤษฎีบท Cay^+(Z_p, {a_1, a_2, a_3}) เมื่อ a_1, a_2, a_3 ∈ A จะมีกราฟบริบูรณ์ที่จุด {u_1, u_2, u_3} โดยที่
2u_1 ≡ a_2 + a_3 – a_1(mod p)
2u_2 ≡ a_1 + a_3 – a_2(mod p)
2u_3 ≡ a_1 + a_2 – a_3(mod p)
ทฤษฎีบท ถ้า p เป็นจำนวนเฉพาะคี่ แล้ว χ(Cay^+(Z_p, {a, b, c}), a,b,c ∈ Z_p) = 3
ทฤษฎีบท ถ้า p เป็นจำนวนเฉพาะคี่ แล้ว ω(Cay^+(Z_p, {a, b, c, d}), a,b,c,d ∈ Z_p) = 3
ทฤษฎีบท ถ้า p เป็นจำนวนเฉพาะคี่ แล้ว 3 ≤ χ(Cay^+(Z_p, {a, b, c, d}), a,b,c,d ∈ Z_p) ≤ 4
ทฤษฎีบท ถ้า p เป็นจำนวนเฉพาะคี่ แล้ว ω(Cay^+(Z_p, Z_p – {a_i})) = (p+1)/2
ทฤษฎีบท ถ้า p เป็นจำนวนเฉพาะคี่ แล้ว χ(Cay^+(Z_p, Z_p – {a_i})) = (p+1)/2