418531 ภาคต้น 2552/โจทย์ปัญหาอัลกอริทึมแบบตะกละ II/เฉลยข้อ 7

สังเกตได้ว่า cycle ที่มีความยาวเป็น 4 นั้น ถ้าพิจารณาอีกมุมหนึ่งก็คือ vertex 4 vertex ที่มี edge เชื่อมจาก vertex ที่หนึ่งไป vertex ที่สอง จาก vertex ที่สองไป vertex ที่สาม จาก vertex ที่สามไป vertex ที่สี่ และจาก vertex ที่สี่ไป vertex ที่หนึ่งนั่นเอง ดังนั้นถ้าเราใช้เทคนิคแบบ brute force เราจะได้ว่า วัตถุที่เราต้องการค้นหาคือ vertex 4 vertex จากทั้งหมด $n=|V|\,$ vertex ที่มีเงื่อนไขข้างต้นนั่นเอง ดังนั้นเวลาการทำงานของอัลกอริทึมแบบ brute force นี้จะเป็น ${n \choose 4}=O(n^{4})\,$ นั่นเอง แต่เนื่องจากโจทย์ข้อนี้ต้องการให้ได้เวลาการทำงานเป็น $O(n^{3})\,$ ดังนั้น อัลกอริทึมข้างต้นจึงใช้ไม่ได้

เราจะใช้อัลกอริทึมต่อไปนี้แทน

พิจารณา cycle ที่มีความยาวสี่ ต่อไปนี้

จาก cycle ที่มีความยาวสี่ข้างต้น เราจะได้ว่า จากเดิมที่ต้องเลือก vertex 4 vertex มาแล้วหา edge เชื่อมระหว่าง vertex ทั้งสี่นี้ เราสามารถ เลือก vertex มาแค่ 2 vertex ซึ่งการเลือก vertex 2 vertex จาก n vertex จะได้เวลาการทำงานเป็น $O(n^{2})\,$ และโจทย์ต้องการให้ได้เวลาการทำงานทั้งหมดเป็น $O(n^{3})\,$ ดังนั้นถ้าเราสามารถหาอีก 2 vertex ที่เหลือได้ในเวลาการทำงานอีก $O(n)\,$ เราก็จะได้เวลาการทำงานรวมเป็น $O(n^{3})\,$ ตามที่ต้องการ

จากตัวอย่าง โดยไม่เสียความเป็นทั่วไป สมมติให้เราเลือก vertex มาสอง vertex คือ $a\,$ กับ $d\,$ แล้วเราสามารถหา vertex ที่เหลือคือ $b\,$ กับ $c\,$ ได้ดังนี้ พิจารณา adjacency matirx ที่ใช้แทนกราฟนี้ พิจารณาว่า ถ้าเราจะหาอีกสอง vertex ($b,c\,$) ที่มี edge เชื่อมกับ สอง vertex ที่เราเลือกมาแล้ว ($a,d\,$)ได้โดยพิจารณา row ต่าง ๆ ใน matrix ถ้ามี row อย่างน้อย 2 row ที่มีเลข 1 ตรง column $a\,$ กับ $d\,$ พร้อมกัน เราก็จะเลือก vertex ที่อยู่ใน row นั้น(ถ้ามีมากกว่า 2 ให้เลือกสองตัวใด ๆ ก็ได้) ซึ่งการทำแบบจะใช้เวลาอย่างมาก คือสำรวจ row ทุก ๆ row ใน matrix ซึ่งจำนวน row ทั้งหมดจะเท่ากับจำนวน vertex ซึ่งก็คือ $n\,$ นั่นเอง สรุปอัลกอริทึมคือ เลือก vertex 2 vertex จาก n vertex และสำหรับแต่ละคู่ของ vertex ที่เลือกมาข้างต้น เราก็ไล่หาไปตาม row ใน adjacency matrix หาอีกสอง row ที่มีเลข 1 ตรง column ของ vertex สอง vertex ที่เราเลือกข้างต้นตรงกัน เราจะได้ว่า อัลกอริทึมข้างต้นใช้เวลาในการเลือกสอง vertex แรกเป็น $O(n^{2})\,$ และสำหรับแต่ละคู่ของ vertex ที่เลือกใช้เวลาสำรวจ row อีก $O(n)\,$ ดังนั้นเวลาการทำงานทั้งหมดจึงเป็น $O(n^{3})\,$ ตามต้องการ