ขั้นตอนวิธีโบรน-เคอร์โบสท์

**ขั้นตอนวิธีโบรน-เคอร์โบสท์** () เป็นขั้นตอนวิธีการหากลุ่มพรรคพวกที่ใหญ่ที่สุดในกราฟไม่ระบุทิศทาง (undirected graph) ซึ่งก็คือการระบุสับเซตทั้งหมดของจุดยอด (vertex) ประกอบด้วยคุณสมบัติสองประการคือ แต่ละคู่ของจุดยอดของสับเซตที่ถูกระบุแต่ละครั้งจะต้องถูกเชื่อมโดยเส้นเชื่อมเสมอและ ไม่มีสับเซตใดที่จะมีจุดยอดเพิ่มเติมถูกเพิ่มเข้าไปในสับเซตขณะที่มันเป็นการเชื่อมต่อที่บริบูรณ์ (complete connectivity) ขั้นตอนวิธีโบรน-เคอร์โบสท์ ถูกออกแบบโดย แยป เคอร์โบสท์ และ แคนรีด โบรน สองนักวิทยาศาสตร์ชาวดัตช์ ซึ่งตีพิมพ์เรื่องนี้ในปี ค.ศ.1973 แม้ว่าขั้นตอนวิธีอื่น ๆ สำหรับการแก้ปัญหากลุ่มพรรคพวก (clique problem) จะมีเวลาการทำงานดีกว่าในทางทฤษฎีสำหรับข้อมูลขาเข้าที่เป็นเซตอิสระขนาดใหญ่สุด (maximal independent set) จำนวนน้อย ๆ แต่ขั้นตอนวิธีโบรน-เคอร์โบสท์ และการปรับปรุงจากขั้นตอนวิธีนี้ถูกรายงานบ่อยครั้งว่ามีประสิทธิภาพดีกว่าแบบอื่น ๆ ในทางปฏิบัติ ขั้นตอนวิธีนี้มีชื่อเสียงและถูกนำไปใช้อย่างกว้างขวางในการใช้งานที่ต้องใช้ขั้นตอนวิธีเกี่ยวกับกราฟ เช่น เคมีการคำนวณ (computational chemistry)

ขั้นตอนวิธีที่เกิดขึ้นในช่วงเดียวกันของอัคโคยันลู (Akkoyunlu) ในปี ค.ศ.1973 ซึ่งแม้ว่าอาจจะถูกนำเสนอในรูปแบบที่ต่างออกไป แต่ก็จะมีลักษณะที่เหมือนกับขั้นตอนวิธีโบรน-เคอร์โบสท์ เมื่อถูกสร้างเป็นต้นไม้ค้นหาแบบเวียนเกิดที่เหมือนกัน

## แบบไม่มีแกนหลัก

รูปแบบพื้นฐานของขั้นตอนวิธีโบรน-เคอร์โบสท์ คือขั้นตอนวิธีการย้อนรอยแบบเวียนเกิด (recursive backtracking) ที่ค้นหากลุ่มพรรคพวกที่ใหญ่ที่สุดในกราฟ *G* โดยทั่วไป กำหนดให้มีสามเซต *R* *P* และ *X* แล้วมันจะทำการหากลุ่มพรรคพวกที่ใหญ่ที่สุด ที่มีทุกจุดยอดอยู่ใน *R* บางจุดยอดใน *P* และไม่มีจุดยอดใดเลยในเซต *X* โดยภายในการเรียกการเวียนเกิด เซต *P* และ *X* จะถูกจำกัดไว้สำหรับจุดยอดที่สร้างเป็นกลุ่มพรรคพวกเมื่อถูกรวมเข้ากับเซต *R* ซึ่งจุดยอดเหล่านี้เท่านั้นที่จะถูกใช้เป็นส่วนหนึ่งของข้อมูลขาออก หรือป้องกันกลุ่มพรรคพวกบางกลุ่มที่จะถูกนำไปเป็นข้อมูลขาออก

การเวียนเกิดนี้เริ่มต้นโดยกำหนดให้เซต *R* และ *X* เป็นเซตว่าง และให้ *P* เป็นเซตของจุดยอดของกราฟ โดยภายในการเรียกการเวียนเกิดแต่ละครั้ง จะมีการพิจารณาจุดยอดใน *P* ถ้าไม่มีจุดยอดใด ๆ เลย ก็จะให้ *R* เป็นกลุ่มพรรคพวกที่ใหญ่ที่สุด (ในกรณีที่ *X* เป็นเซตว่าง) หรือให้ย้อนรอย สำหรับแต่ละจุดยอด *v* ที่ถูกเลือกจาก *P* มันจะทำการเรียกการเวียนเกิด ซึ่ง *v* ถูกเพิ่มเข้าไปใน *R* และ *P* กับ *X* ถูกจำกัดไว้สำหรับเพื่อนบ้านของ *v* เขียนว่า *N(v)* ซึ่งจะหาและรายงานส่วนเพิ่มของกลุ่มพรรคพวกของ *R* ซึ่งประกอบด้วย *v* หลังจากนั้นจะทำการย้าย *v* จาก *P* ไปยัง *X* และทำต่อไปเรื่อย ๆ กับจุดยอดต่อไปใน *P*
รหัสเทียมของขั้นตอนวิธีสามารถเขียนได้ดังนี้

```
BronKerbosch1(R,P,X):
        ถ้า P และ X เป็นเซตว่างทั้งคู่:
            รายงานว่า R เป็นกลุ่มพรรคพวกที่ใหญ่ที่สุด
        สำหรับทุก ๆ จุดยอด v ในเซต P:
            BronKerbosch1(R ⋃ {v}, P ⋂ N(v), X ⋂ N(v))
            P := P \ {v}
            X := X ⋃ {v}
```


## แบบมีแกนหลัก

รูปแบบพื้นฐานของขั้นตอนวิธีดังที่ได้อธิบายข้างต้น จะไม่มีประสิทธิภาพในกรณีที่กราฟมีกลุ่มพรรคพวกที่ไม่ได้ใหญ่ที่สุดอยู่จำนวนมาก มันจะทำให้เกิดการเรียกการเวียนเกิดทุกกลุ่มพรรคพวก ไม่ว่าจะใหญ่ที่สุดหรือไม่ก็ตาม เพื่อที่จะประหยัดเวลาและให้ขั้นตอนวิธีดังกล่าวย้อนรอยได้อย่างรวดเร็วในแขนงของต้นไม้ค้นหาที่ไม่มีพรรคพวกที่ใหญ่ที่สุดอยู่ โบรนและเคอร์โบสท์ได้นำเสนอขั้นตอนวิธีที่ต่างออกไปเกี่ยวกับ **จุดยอดแกนหลัก** (pivot vertex) *u* ซึ่งถูกเลือกจาก *P* (หรือกล่าวโดยทั่วไปคือ จาก *P* ⋃&hairsp;*X*&hairsp;) กลุ่มพรรคพวกที่ใหญ่ที่สุดใด ๆ ต้องประกอบด้วย *u* หรือ จุดยอดหนึ่งที่ไม่ใช่เพื่อนบ้านของ *u* นอกนั้น กลุ่มพรรคพวกสามารถที่จะขยายโดยเพิ่ม *u* เข้าไป ดังนั้น เฉพาะ *u* และจุดยอดที่ไม่ใช่เพื่อนบ้านของมันต้องถูกทดสอบเพื่อเป็นตัวเลือกสำหรับจุดยอด *v* ที่จะถูกรวมเข้ากับ *R* ในแต่ละครั้งของการเรียกการเวียนเกิด ในรหัสเทียมถ้าแกนหลัก (pivot) ถูกเลือกเพื่อลดจำนวนการเรียกการเวียนเกิดให้เหลือน้อยที่สุดแล้ว จะลดเวลาการทำงานลงได้มากเมื่อเทียบกับแบบไม่ใช้แกนหลัก
รหัสเทียมแสดงขั้นตอนวิธีโบรน-เคอร์โบสท์แบบมีแกนหลัก

```
BronKerbosch2(R,P,X):
        ถ้า P และ X เป็นเซตว่างทั้งคู่:
            รายงานว่า R เป็นกลุ่มพรรคพวกที่ใหญ่ที่สุด
        เลือกแกนหลักเป็นจุดยอด u ใน P U X
        สำหรับทุก ๆ จุดยอด v ใน P \ N(u):
            BronKerbosch2(R ⋃ {v}, P ⋂ N(v), X ⋂ N(v))
            P := P \ {v}
            X := X ⋃ {v}
```


## แบบมีการลำดับจุดยอด

เป็นอีกวิธีสำหรับการปรับปรุงรูปแบบพื้นฐานของขั้นตอนวิธีโบรน-เคอร์โบสท์เกี่ยวกับการไม่เลือกแกนหลักที่ชั้นนอกสุดของการเวียนเกิด และเลือกลำดับของการเรียกการเวียนเกิดแทนเพื่อพยายามลดขนาดของเซต *P* ที่เป็นตัวแทนของจุดยอดภายในแต่ละการเรียกการเวียนเกิดแต่ละรอบลงให้มากที่สุด

ความเสื่อม (degeneracy) ของกราฟ *G* คือจำนวนที่น้อยที่สุดที่ทุกกราฟย่อย (subgraph) ของ *G* มีจุดยอดที่มีระดับขั้น *d* หรือน้อยกว่า ในทุกกราฟจะมีการลำดับความเสื่อม ซึ่งเป็นการลำดับของจุดยอดที่แต่ละจุดยอดจะมีเพื่อนบ้านจำนวน *d* หรือน้อยกว่า ซึ่งมาทีหลังในการลำดับ การลำดับความเสื่อมอาจถูกพบได้ในเวลาเป็นเชิงเส้นโดยการเลือกจุดยอดที่มีระดับขั้นต่ำสุดในจุดยอดที่เหลืออยู่ซ้ำ ๆ ถ้าลำดับของจุดยอด *v* ซึ่งขั้นตอนวิธีโบรน-เคอร์โบสท์ได้วงวนผ่านไป เป็นลำดับความเสื่อมแล้ว เซต *P* ของตัวแทนจุดยอดในแต่ละการเรียก (เพื่อนบ้านของ *v* ซึ่งมาทีหลังในการลำดับ) จะรับประกันว่าจะใช้ขนาดอย่างมาก *d* เซต *X* ซึ่งเก็บจุดยอดที่ถูกแยกออกมาจะประกอบด้วยเพื่อนบ้านก่อนหน้านี้ของ *v* และอาจจะใหญ่กว่า *d* ในการเรียกการเวียนเกิดในขั้นตอนวิธีนี้ชั้นของการเวียนเกิดที่อยู่ต่ำกว่าชั้นบนสุดยังคงต้องใช้แบบมีแกนหลักอยู่
รหัสเทียมของขั้นตอนวิธีนี้มีดังต่อไปนี้

```
BronKerbosch3(G):
        P = V(G)
        R = X = เป็นเซตว่าง
        สำหรับทุก ๆ จุดยอด v ในการลำดับความเสื่อมของ G:
            BronKerbosch2(R ⋃ {v}, P ⋂ N(v), X ⋂ N(v))
            P := P \ {v}
            X := X ⋃ {v}
```

ขั้นตอนวิธีดังกล่าวถูกพิสูจน์แล้วว่ามีประสิทธิภาพสำหรับกราฟที่มีความเสื่อมน้อย ๆ และจากการทดลองแสดงให้เห็นว่ามันทำงานได้ดีในทางปฏิบัติกับเครือข่ายสังคมขนาดใหญ่แบบเบาบาง (sparse social networks) และกราฟอื่น ๆ ในโลกแห่งความเป็นจริง

## ตัวอย่าง
thumb|240px|กราฟที่มีกลุ่มพรรคพวกที่ใหญ่ที่สุด 5 กลุ่ม ประกอบด้วย 4 เส้นเชื่อมและ 1 สามเหลี่ยม
ในกราฟตัวอย่างที่ได้แสดง จะเริ่มขั้นตอนวิธีจากการกำหนดให้ *R* = Ø *P* = {1,2,3,4,5,6} และ *X* = Ø โดยแกนหลัก *u* ควรถูกเลือกจากหนึ่งในจุดยอดที่มีระดับขั้นเป็นสามเพื่อที่จะลดการเรียกการเวียนเกิดลง ยกตัวอย่างเช่น สมมติให้ *u* คือจุดยอด 2 หลังจากนั้นก็จะมีสามจุดยอดเหลืออยู่ใน *P* \ *N(u)* คือจุดยอด 2, 4, และ 6

การวนซ้ำของวงวนชั้นในของขั้นตอนวิธีสำหรับเมื่อ *v* = 2 ทำการเรียกการเวียนเกิดเมื่อ *R*&nbsp;=&nbsp;{2} *P*&nbsp;=&nbsp;{1,3,5} and *X*&nbsp;=&nbsp;Ø ภายในการเรียกการเวียนเกิดนี้ หนึ่งใน 1 หรือ 5 จะถูกเลือกเป็นแกนหลัก และจะมีการเรียกการเวียนเกิดในระดับที่สอง 2 ครั้ง ครั้งแรกสำหรับจุดยอด 3 และอีกครั้งสำหรับจุดยอดที่ไม่ได้ถูกเลือกเป็นแกนหลัก ในท้ายที่สุดแล้วการเรียกทั้งสองครั้งนี้จะรายงาน 2 กลุ่มพรรคพวกคือ {1,2,5} และ {2,3} หลังจากการคืนการทำงานจากการเรียกเหล่านี้แล้ว จุดยอด 2 จะถูกเพิ่มเข้าไปใน *X* และถูกลบจาก *P*

การวนซ้ำของวงวนชั้นในของขั้นตอนวิธีสำหรับเมื่อ *v* = 4 ทำการเรียกการเวียนเกิดเมื่อ *R*&nbsp;=&nbsp;{4} *P*&nbsp;=&nbsp;{3,5,6} and *X*&nbsp;=&nbsp;Ø (แม้ว่าจุดยอด 2 เป็นของเซต *X* ในการเรียกชั้นนอก มันก็ไม่ใช่เพื่อนบ้านของ *v* และถูกแยกออกจากสับเซตของ *X* ผ่านการเรียกการเวียนเกิด) การเรียกครั้งนี้จะจบลงด้วยการเรียกการเวียนเกิดระดับที่สอง อีก 3 ครั้ง ซึ่งจะรายงาน 3 กลุ่มพรรคพวกคือ {3,4}, {4,5} และ {4,6} หลังจากนั้นจุดยอด 4 จะถูกเพิ่มเข้าไปใน *X* และถูกลบจาก *P*

ในการวนซ้ำครั้งที่สามและครั้งสุดท้ายของวงวนชั้นในสำหรับเมื่อ *v* = 6 ทำการเรียกการเวียนเกิดเมื่อ *R*&nbsp;=&nbsp;{6} *P*&nbsp;=&nbsp;Ø and *X*&nbsp;=&nbsp;{4} เนื่องจากการเรียกครั้งนี้ *P* ว่างเปล่าแล้ว และ *X* ไม่ว่างเปล่า มันจะทำการย้อนรอยในทันทีโดยไม่รายงานกลุ่มพรรคพวกอื่น ๆ อีก เพราะมันไม่สามารถมีกลุ่มพรรคพวกที่ใหญ่ที่สุดที่ประกอบด้วยจุดยอด 6 และไม่มีจุดยอด 4 ประกอบอยู่
ดังนั้นต้นไม้การเรียกของขั้นตอนวิธีดังกล่าวจะมีลักษณะดังนี้
    BronKerbosch2(Ø, {1,2,3,4,5,6}, Ø)
        BronKerbosch2({2}, {1,3,5}, Ø)
            BronKerbosch2({2,3}, Ø, Ø): ให้ผลลัพธ์ {2, 3}
            BronKerbosch2({2,5}, {1}, Ø)
                BronKerbosch2({1,2,5}, Ø, Ø): ให้ผลลัพธ์ {1,2,5}
        BronKerbosch2({4}, {3,5,6}, Ø)
            BronKerbosch2({3,4}, Ø, Ø): ให้ผลลัพธ์ {3,4}
            BronKerbosch2({4,5}, Ø, Ø): ให้ผลลัพธ์ {4,5}
            BronKerbosch2({4,6}, Ø, Ø): ให้ผลลัพธ์ {4,6}
        BronKerbosch2({6}, Ø, {4}): ไม่ให้ผลลัพธ์

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

    BronKerbosch3(G)
        BronKerbosch2({6}, {4}, Ø)
            BronKerbosch2({6,4}, Ø, Ø): ให้ผลลัพธ์ {6,4}
        BronKerbosch2({4}, {3,5}, {6})
            BronKerbosch2({4,3}, Ø, Ø): ให้ผลลัพธ์ {4,3}
            BronKerbosch2({4,5}, Ø, Ø): ให้ผลลัพธ์ {4,5}
        BronKerbosch2({3}, {2}, {4})
            BronKerbosch2({3,2}, Ø, Ø): ให้ผลลัพธ์ {3,2}
        BronKerbosch2({1}, {2,5}, Ø)
            BronKerbosch2({1,2}, {5}, Ø)
                BronKerbosch2({1,2,5}, Ø, Ø): ให้ผลลัพธ์ {1,2,5}
        BronKerbosch2({2}, {5}, {1,3}): ไม่ให้ผลลัพธ์
        BronKerbosch2({5}, Ø, {1,2,4}): ไม่ให้ผลลัพธ์

## การวิเคราะห์เวลาการทำงานในกรณีแย่สุด
ขั้นตอนวิธีโบรน-เคอร์โบสท์ ไม่ใช่ขั้นตอนวิธีที่ปริมาณข้อมูลส่งออกมีผลต่อเวลาการทำงาน (output-sensitive algorithm) ไม่เหมือนกับขั้นตอนวิธีอื่น ๆ สำหรับปัญหาการหากลุ่มพรรคพวก มันไม่ได้ทำงานเป็นเวลาแบบพหุนาม (polynomial time) ต่อกลุ่มพรรคพวกที่ใหญ่ที่สุดที่ถูกสร้างขึ้น อย่างไรก็ตามมันมีประสิทธิภาพในกรณีแย่สุด โดยจากผลของ มูนและมูสเซอร์ (ค.ศ.1965) กราฟที่มีจุดยอด n จุดยอดใด ๆ จะมีกลุ่มพรรคพวกที่ใหญ่ที่สุดอย่างมาก 3*n*/3 กลุ่ม และมีเวลาการทำงานในกรณีแย่สุด (โดยใช้แบบมีแกนหลักที่จะลดจำนวนการเรียกการเวียนเกิดให้เหลือน้อยที่สุดในแต่ละขั้นตอน) เป็น O(3*n*/3)

สำหรับกราฟเบาบาง (sparse graph) การทำให้ขอบเขตแคบลงนั้นเป็นไปได้ โดยเฉพาะแบบมีการลำดับจุดยอดสามารถทำงานได้ภายในเวลา O(*dn*&hairsp;3*d*/3) เมื่อ *d* เป็นความเสื่อมของกราฟซึ่งเป็นการบ่งบอกถึงความเบาบางของกราฟ กราฟใด ๆ ที่มีความเสื่อมเป็น *d* ซึ่งทำให้ผลรวมของจำนวนกลุ่มพรรคพวกที่ใหญ่ที่สุดเป็น (*n* - *d*&hairsp;)3*d*/3 จะทำให้ขอบเขตแคบมาก

## ความรู้เพิ่มเติมเกี่ยวกับขั้นตอนวิธี
กลุ่มพรรคพวกที่ใหญ่ที่สุด (maximal clique) คือ กลุ่มพรรคพวกที่ไม่สามารถขยายได้โดยการเพิ่มจุดยอดที่ติดกันไปอีกหนึ่งจุดหรือมากกว่านั้นอีกแล้ว ซึ่งหมายความว่าจะไม่มีกลุ่มพรรคพวกที่ปรากฏในเซตของจุดยอดของกลุ่มพรรคพวกที่ใหญ่กว่านี้อีก โดยในวงการวิทยาศาสตร์คอมพิวเตอร์ ขั้นตอนวิธีดังกล่าวเป็นปัญหาในการหากลุ่มพรรคพวกที่ใหญ่ที่สุดจัดเป็นปัญหากลุ่มพรรคพวก ปัญหากลุ่มพรรคพวกถือว่าเป็นปัญหาเอ็นพีบริบูรณ์ (NP-complete) ซึ่งเป็นกลุ่มความซับซ้อนที่ยากที่สุดในเอ็นพี ทำการควบคุมตัวแปรคงที่ได้ยากและยากที่จะประมาณค่า โดยเวลาการทำงานของขั้นตอนวิธีประเภทนี้จะใช้เวลาการทำงานเป็นแบบยกกำลัง (exponential) ซึ่งถือว่าช้ามาก

## ปัญหาที่เกี่ยวข้อง

ปัญหากลุ่มพรรคพวก

## อ้างอิง

* .
* .
* .
* .
* .
* .
* .
* .
* .
* .

## แหล่งข้อมูลอื่น
* Bron-Kerbosh algorithm implementation in Python 
* Finding all cliques of an undirected graph. Seminar notes by Michaela Regneri, January 11, 2007.

หมวดหมู่:ขั้นตอนวิธี
หมวดหมู่:กราฟ