การระบายสีกราฟเคย์เลย์ผลบวก
- ชื่อนักเรียนผู้จัดทำโครงงานวิทยาศาสตร์
ต้นกล้า วิบูลย์เลิศวัฒนะ, กฤติน วามานนท์, เมธาวิน พูลเพิ่ม
- อาจารย์ที่ปรึกษาโครงงานวิทยาศาสตร์
จักรพล สาใจ, พร้อมพงศ์ กวีกิจธนา
- โรงเรียนที่กำกับดูแลโครงงานวิทยาศาสตร์
- ปีที่จัดทำโครงงานวิทยาศาสตร์
บทคัดย่อโครงงานวิทยาศาสตร์
ในการศึกษาโครงงานครั้งนี้เราศึกษาเกี่ยวกับการระบายสีของกราฟเคย์เลย์ผลบวก ซึ่งปัญหาการระบายสีกราฟนั้นเป็นปัญหาเกี่ยวกับการระบายสีจุดยอดหรือเส้นเชื่อมที่ประชิดกันโดยใช้สีที่แตกต่างกัน โดยผู้วิจัยมีวัตถุประสงค์ในการศึกษาดังนี้ 1. เพื่อศึกษาการระบายสีจุดยอดและเส้นของกราฟเคย์เลย์ผลบวก 2. เพื่อหาขอบเขตของรงคเลขของจุดยอด ดัชนีรงคของเส้น และจำนวนคลีกของกราฟเคย์เลย์ผลบวก 3. เพื่อวิเคราะห์ขอบเขตดังกล่าว โดยการหากราฟเคย์เลย์ผลบวกที่มีรงคเลข ดัชนีรงค และจำนวนคลีก โดยมีขอบเขตที่ศึกษาดังนี้ 1. เซตของการระบายสีเป็นเซตใด ๆ ที่มีสมาชิกมากกว่า 1 และมีจำนวนจุดยอดเป็นจำนวนเฉพาะคี่ 2. เซตของการระบายสีเป็นเซตของยูนิตในกรณีที่จำนวนจุดยอดเป็นจำนวนนับที่มีค่ามากกว่า 1 ใด ๆ
ในการศึกษาครั้งนี้ ผู้วิจัยดำเนินงานโดยใช้วิธีการทางคณิตศาสตร์เพื่อพิสูจน์ข้อสังเกตต่าง ๆ ในกราฟเคย์เลย์ผลบวก จนสามารถสรุปผลได้เป็นทฤษฎีบทของการระบายสีของกราฟเคย์เลย์ผลบวก และสมบัติบางประการที่เกี่ยวข้อง อีกทั้งทางผู้วิจัยได้เขียนโปรแกรมสร้างและวิเคราะห์กราฟเคย์เลย์ผ่าน MATLAB เพื่อพิสูจน์และสนับสนุนทฤษฎีบทที่ได้มา ดังนี้
ทฤษฎีบท ถ้า 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
ทฤษฎีบท สำหรับจำนวนนับ n ที่มากกว่า 1 ใด ๆ จะได้ว่า χ′(G_n) = |U_n| = ϕ(n)