ขอบเขตล่างของการแบ่งกลุ่มที่ดีที่สุดบนกราฟบริบูรณ์ถ่วงน้ำหนัก
- ชื่อนักเรียนผู้จัดทำโครงงานวิทยาศาสตร์
ปพณ ละเภท
- อาจารย์ที่ปรึกษาโครงงานวิทยาศาสตร์
ธรรมนูญ ผุยรอด
- โรงเรียนที่กำกับดูแลโครงงานวิทยาศาสตร์
- ปีที่จัดทำโครงงานวิทยาศาสตร์
บทคัดย่อโครงงานวิทยาศาสตร์
นิยามให้ ‘การแบ่งกลุ่มที่ดีที่สุด’ ในการแบ่งกลุ่มจุดยอดของกราฟ G ออกเป็น k ส่วนคือ V_1,V_2,…,V_k ซึ่งแต่ละส่วนมีการกำหนดจำนวนจุดยอดไว้ (ต้องมากกว่า 1 จุด) เป็นการแบ่งกลุ่มซึ่งทำให้ค่าของฟังก์ชัน
F_G (V_1,V_2,…,V_k )=min┬█(i∈[1,k]@v∈V_i )(∑_█(u∈V_i@u≠v)▒〖w_G (u,v) 〗) (1/(|V_i |-1))
มีค่ามากที่สุดในบรรดาการแบ่งกลุ่มทั้งหมดที่เป็นไปได้ และให้ M_n (G) แทนค่าของ F_G (V_1,V_2,…,V_k ) ของการแบ่งกลุ่มที่ดีที่สุด เมื่อกำหนดให้แต่ละกลุ่ม V_1,V_2,…,V_k มีจุดยอดกลุ่มละ n จุด
เป้าหมายของโครงงานนี้ คือการหาขอบเขตล่างของค่า M_n (G) ดังกล่าวในรูปของตัวแปรอื่นๆ ซึ่งจะกำหนดในภายหลัง
จากการค้นคว้าข้อมูลจากงานวิจัยด้าน Graph Partitioning Problem ในอดีต ไม่พบงานวิจัยที่มีฟังก์ชันเป้าหมายตัวเดียวกันกับโครงงานนี้