สมมติว่าเรามีลูกปัด $n$ สีที่แตกต่างกัน (แต่ละสีมีจำนวนไม่จำกัด) เราต้องการนำลูกปัดเหล่านี้มาร้อยเป็นสร้อยข้อมือที่มีสีสันสวยงาม คำถามพื้นฐานแรกๆก็คงหนีไม่พ้นว่า เราต้องใช้ลูกปัดกี่ลูกเพื่อสร้างสร้อยข้อมือที่สวยที่สุด แน่นอนว่าตรงนี้คำตอบก็จะแตกต่างกันออกไปขึ้นกับนิยาม “ความสวย” ของแต่ละคน เช่น หากเราบอกว่าสร้อยที่สวยงามนั้นขอแค่ให้มีสีสันครบทั้ง $n$ สี เช่นนี้แล้วสร้อยของเราก็ต้องมีลูกปัดอย่างน้อย $n$ ลูกเป็นแน่แท้

ครั้งนี้เราจะพิจารณานิยามความงามที่ระบุว่า สำหรับคู่ของลูกปัดสองลูกใดๆที่อยู่ติดกัน เราอยากเห็นสีสันที่แตกต่างกันให้ครบทุกคู่สี ซึ่งในตอนนี้เราจะคำนึงว่าลำดับคู่ลูกปัดจะสลับที่ไม่ได้ กล่าวคือ คู่ลูกปัดสีแดง-เขียว 🔴🟢 นับว่าแตกต่างจากคู่ลูกปัดสีเขียว-แดง 🟢🔴 (กรณีที่สลับที่ได้จะกล่าวถึงในตอนถัดถัดไป)

ตัวอย่างเช่น หากเรามีลูกปัดอยู่ $n=3$ สีได้แก่ แดง, เขียว, น้ำเงิน 🔴🟢🔵 คู่สีทั้งหมดที่แตกต่างกันจะมีอยู่ $n(n-1)=3\times2=6$ คู่สี ซึ่งก็คือ

1. 🔴🟢 แดง-เขียว
2. 🔴🔵 แดง-น้ำเงิน
3. 🟢🔴 เขียว-แดง
4. 🟢🔵 เขียว-น้ำเงิน
5. 🔵🔴 น้ำเงิน-แดง
6. 🔵🟢 น้ำเงิน-เขียว

เราจะต้องใช้ลูกปัดทั้งหมดเป็นจำนวนน้อยที่สุดกี่ลูก และเราจะสร้างสร้อยเส้นนี้ขึ้นมาได้อย่างไร?

ขั้นแรก เราอาจลองแก้ปัญหาอย่างตรงไปตรงมา นั่นคือนำคู่ของลูกปัดข้างต้นทั้ง 6 แบบมาร้อยเรียงเป็นสร้อยข้อมือเลย นั่นคือเราจะใช้ลูกปัดทั้งหมดเป็นจำนวน 12 ลูก และได้สร้อยข้อมือผลลัพธ์เช่นนี้

🔴🟢🔴🔵🟢🔴🟢🔵🔵🔴🔵🟢-(วนกลับไปหา🔴)

แต่ว่าเราจำเป็นต้องใช้ลูกปัดถึง 12 ลูกจริงหรือ? สังเกตว่าผลลัพธ์ข้างต้นนั้นเราใช้ลูกปัดสีน้ำเงินติดกันสองลูก ทั้งที่เราสามารถลดทอนตรงนี้ให้เหลือเพียงแค่ลูกเดียวก็ได้

ยิ่งไปกว่านั้น หากเราลองสลับสับเปลี่ยนลำดับของคู่ลูกปัดที่เราสนใจ เราอาจจับคู่แล้วลดทอนสีที่เหมือนกันในตำแหน่งหัวท้ายระหว่างคู่ไปได้อีก เช่น จากลำดับที่ 1 เรียงไปถึง 6 ตามข้างต้น หากเราเปลี่ยนไปเรียงลำดับเป็น 1-3-2-6-4-5 แทน เราจะได้สร้อยลูกปัด

🔴🟢-🟢🔴-🔴🔵-🔵🟢-🟢🔵-🔵🔴-(วนกลับ)

หรือก็คือ เมื่อกำจัดคู่ของลูกปัดสีซ้ำกันที่อยู่ติดกันออกไป ก็จะได้สร้อย

🔴🟢🔴🔵🟢🔵-(วนกลับไป🔴)

นั่นคือเราจะใช้ลูกปัดเพียงแค่ 6 ลูกเท่านั้น

และนี่ก็ยังเป็นจำนวนลูกปัดที่น้อยที่สุดที่เป็นไปได้อีกด้วย เพราะหากเราใช้ลูกปัดจำนวนน้อยกว่านี้ไปอีก แค่การที่เราจะไล่คู่ลูกปัดในสร้อยข้อมือให้ครบทั้ง 6 กรณีข้างต้นก็เป็นไปไม่ได้เสียแล้ว

แล้วสำหรับ $n$ ที่ใหญ่กว่านี้หล่ะ? อย่างเช่นที่ $n=5$ สำหรับลูกปัดสี 🔴🟠🟡🟢🔵 ซึ่งจะมีลูกปัดทั้งหมด $5\times4=20$ คู่สีที่แตกต่างกัน แล้วเราจะยังใช้ลูกปัดเพียงแค่ 20 ลูกได้อยู่หรือเปล่า? คำตอบก็คือได้ เพราะเราสามารถจัดเรียงลูกปัดในสร้อยตามโครงสร้างนี้

1. 🔴🟠🔴🟡🔴🟢🔴🔵-(ต่อบรรทัดถัดไป)
2. 🟠🟡🟠🟢🟠🔵-…
3. 🟡🟢🟡🔵-…
4. 🟢🔵-(วนกลับบรรทัดแรก)

หรือพูดอีกอย่างก็คือ ในบรรทัดที่ 1 เราจะจัดการกรณีลูกปัดสีแดง 🔴 ให้หมดก่อน นั่นคือเริ่มจากการนำลูกปัดสีแดงจำนวน 4 ลูกวางไว้เป็นฐาน แล้วจึงนำลูกปัดสีอื่นๆที่เหลือมาวางแทรกระหว่างลูกปัดสีแดง (ลูกปัด 🔵 สีสุดท้ายวางปิดท้ายบรรทัด) หลังจากนั้นก็ไล่แบบเดียวกันกับลูกปัดสีอื่นๆที่เหลือ ซึ่งก็คือสีส้ม 🟠 สีเหลือง 🟡 และสีเขียว 🟢 ตามลำดับ ส่วนสีน้ำเงิน 🔵 นั้นไม่ต้องทำเพราะทุกบรรทัดช่วยกันทำให้เรียบร้อยแล้ว

วิธีการข้างต้นนี้ก็ดูเรียบง่ายและมีโครงสร้างที่ชัดเจนดี และจะเห็นได้ไม่ยากว่าเราสามารถขยายแนวคิดนี้ไปยัง $n$ ใดๆได้อีกด้วย

แต่ถ้าเกิดเราไม่อยากได้ผลลัพธ์ที่ดูเป็นโครงสร้างแบบแผนชัดเจนเกินไปเช่นนี้หล่ะ? หากเราต้องการสร้อยลูกปัดที่ดูเหมือนถูก “สุ่ม” แต่ก็ยังรับประกันว่ามีคู่สีลูกปัดครบ เราสามารถออกแบบวิธีการร้อยลูกปัดได้อยู่หรือเปล่า?

เราอาจเริ่มจากการสังเกตว่า ในบรรทัด 🔴 นั้นเราสามารถสลับตำแหน่งของลูกปัดสีอื่นๆที่แทรกระหว่างลูกปัดสีแดงได้ และเราก็สามารถทำอย่างนี้กับบรรทัดอื่นๆได้เช่นกัน นอกจากนี้ เรายังสามารถสลับลำดับแต่ละบรรทัดได้ด้วย (เพราะแต่ละบรรทัดลงท้ายด้วย 🔵 เหมือนกัน) … แต่การสลับตำแหน่งเพียงเท่านี้ก็อาจจะยังไม่ใช่ขั้นตอนวิธีที่ดีมากนักสำหรับผลลัพธ์แบบสุ่ม (เนื่องจากเรายังจะเจอลูกปัดสีแดงติดกันเป็นพืดอยู่)

เทคนิคหนึ่งที่น่าสนใจก็คือการมองปัญหานี้ให้เป็นกราฟ โดยให้ลูกปัดแต่ละสีเป็นจุดยอดของกราฟ ให้เส้นเชื่อมเป็นการเลือกลูกปัดลูกถัดไป แล้วสร้างกราฟบริบูรณ์แบบมีทิศทางขึ้นมา ดังนั้นหนึ่งในวิธีร้อยลูกปัดลงสร้อยข้อมือก็คือหนึ่งในวงจรออยเลอร์ของกราฟนี้

เพราะว่ากราฟเป็นกราฟแบบมีทิศทางที่เชื่อมโยงกันหมดและทุกจุดยอดมีดีกรีเข้าเท่ากับดีกรีออก จึงทำให้กราฟนี้มีวงจรออยเลอร์อย่างแน่นอน

I. แปลงปัญหาเป็นกราฟมีทิศทาง II. หาวงจรออยเลอร์ III. ได้คำตอบเป็นสร้อยลูกปัด

และหากเราใช้ขั้นตอนวิธีสำหรับหาวงจรออยเลอร์ (เช่น ขั้นตอนวิธีของไฮเออร์โฮลเซอร์) โดยเลือกเดินผ่านเส้นเชื่อมแบบสุ่ม เราก็จะได้สร้อยลูกปัดที่ดูสุ่มแต่ก็ยังรับประกันสมบัติที่ว่ามีคู่สีที่แตกต่างกันปรากฏครบถ้วนทุกคู่พอดี

Originally published on: Facebook

neizod

author