ในทฤษฎีกราฟคลิก( / ˈ k l iː k /หรือ/ ˈ k l ɪ k / ) คือเซตย่อยของจุดยอดในกราฟแบบไม่มีทิศทางโดยที่จุดยอดที่แตกต่างกันสองจุดในคลิกนั้นจะต้องอยู่ติดกันกล่าวคือ คลิกของกราฟเป็นกราฟย่อยแบบเหนี่ยวนำของกราฟนั้น ซึ่งเป็น กราฟ สมบูรณ์คลิกเป็นหนึ่งในแนวคิดพื้นฐานของทฤษฎีกราฟและถูกนำไปใช้ในปัญหาทางคณิตศาสตร์และการสร้างกราฟอื่นๆ อีกมากมาย คลิกยังได้รับการศึกษาในวิทยาศาสตร์คอมพิวเตอร์ ด้วย : งานของการค้นหาว่ามีคลิกที่มีขนาดที่กำหนดในกราฟ หรือไม่ ( ปัญหาคลิก ) เป็น ปัญหา NP-completeแต่ถึงแม้จะมีความยากลำบากนี้ ก็มีการศึกษาอัลกอริทึมมากมายสำหรับการค้นหาคลิก ${\displaystyle G}$${\displaystyle G}$

แม้ว่าการศึกษาเกี่ยวกับกราฟย่อยที่สมบูรณ์จะย้อนกลับไปอย่างน้อยถึงการปรับปรุงทฤษฎีของแรมซีย์ในเชิงทฤษฎี^กราฟโดยErdős & Szekeres (1935) [ ^{1 ]}แต่คำว่า"คลิก"มาจากLuce & Perry (1949)ซึ่งใช้กราฟย่อยที่สมบูรณ์ในเครือข่ายสังคมเพื่อจำลองคลิกของผู้คน กล่าวคือ กลุ่มคนที่ทุกคนรู้จักกันและกัน คลิกมีแอปพลิเคชันอื่นๆ อีกมากมายในวิทยาศาสตร์และโดยเฉพาะอย่างยิ่งในชีวสารสนเทศ

กลุ่มจุดยอด (clique ) Cในกราฟแบบไม่มีทิศทางG = (V, E) คือเซตย่อยของจุดยอด C ⊆ Vโดยที่จุดยอดที่แตกต่างกันสองจุดทุกจุดจะอยู่ติดกัน เงื่อนไขนี้เทียบเท่ากับเงื่อนไขที่ว่ากราฟย่อยที่เกิดจากCในGเป็นกราฟสมบูรณ์ในบางกรณี คำว่ากลุ่มจุดยอด (clique) อาจหมายถึงกราฟย่อยโดยตรงก็ได้

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

กลุ่มคลิกสูงสุดของกราฟGคือกลุ่มคลิกที่ไม่มีกลุ่มคลิกใดที่มีจำนวนจุดยอดมากกว่ากลุ่มคลิกสูงสุดนั้น นอกจากนี้จำนวนกลุ่มคลิกω ( G )ของกราฟGคือจำนวนจุดยอดในกลุ่มคลิกสูงสุดของกราฟ G

จำนวนจุดตัดของ กราฟ Gคือจำนวนกลุ่มย่อยที่น้อยที่สุดที่รวมกันแล้วครอบคลุมขอบทั้งหมดของกราฟ G

จำนวนคลิกคัฟเวอร์ของกราฟGคือจำนวนคลิกน้อยที่สุดของกราฟGซึ่งผลรวมของคลิกคัฟเวอร์เหล่านั้นสามารถครอบคลุมเซตของจุดยอดVของกราฟ ได้

การตัดผ่านคลิกสูงสุดของกราฟคือเซตย่อยของจุดยอดที่มีคุณสมบัติว่าคลิกสูงสุดแต่ละคลิกของกราฟมีจุดยอดอย่างน้อยหนึ่งจุดในเซตย่อย^{[ 2 ]}

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

แนวคิดที่เกี่ยวข้องคือ ไบคลิก (biclique)ซึ่งเป็นกราฟย่อยแบบสองส่วนสมบูรณ์มิติแบบสองส่วนของกราฟคือจำนวนไบคลิกขั้นต่ำที่จำเป็นในการครอบคลุมขอบทั้งหมดของกราฟ

ผลลัพธ์ทางคณิตศาสตร์ที่เกี่ยวข้องกับกลุ่มคลิก ได้แก่ ดังต่อไปนี้

• ทฤษฎีบทของ Turánให้ขอบเขตล่างของขนาดคลิกในกราฟหนาแน่น^{[ 3 ]} หากกราฟมีขอบมากพอ ก็จะต้องมีคลิกขนาดใหญ่ ตัวอย่างเช่น กราฟทุกกราฟที่มีจุดยอดและขอบมากกว่าจะต้องมีคลิกสามจุดยอด${\displaystyle n}$${\displaystyle \scriptstyle \left\lfloor {\frac {n}{2}}\right\rfloor \cdot \left\lceil {\frac {n}{2}}\right\rceil }$
• ทฤษฎีบทของแรมซีย์ระบุว่ากราฟทุกกราฟหรือกราฟส่วนเติมเต็ม ของกราฟนั้น จะมีคลิกที่มีจำนวนจุดยอดอย่างน้อยเท่ากับจำนวนลอการิทึม^{[ 4 ]}
• จากผลการศึกษาของMoon & Moser (1965)กราฟที่มีจุดยอด 3n จุดจะมีคลิกสูงสุดได้มากที่สุด 3n ^คลิกกราฟที่ตรงตามขอบเขตนี้คือกราฟ Moon–Moser K _3,3,...ซึ่งเป็นกรณีพิเศษของกราฟ Turánที่เกิดขึ้นเป็นกรณีสุดขั้วในทฤษฎีบทของ Turán
• ข้อสันนิษฐานของ Hadwigerซึ่งยังไม่ได้รับการพิสูจน์ แสดงให้เห็นว่าขนาดของกลุ่มย่อยที่ใหญ่ที่สุดในกราฟ ( จำนวน Hadwiger ) มีความสัมพันธ์กับจำนวนสีที่ใช้ ในกราฟ นั้น
• การคาดเดา ของErdős–Faber–Lovászเกี่ยวข้องกับการระบายสีกราฟกับกลุ่มต่างๆ
• ข้อสันนิษฐาน ของErdős–Hajnalกล่าวว่า ตระกูลของกราฟที่กำหนดโดยลักษณะเฉพาะของกราฟที่ต้องห้ามนั้นจะมีคลิกขนาดใหญ่หรือโคคลิก ขนาด ใหญ่

กราฟประเภทสำคัญหลายประเภทสามารถกำหนดหรือจำแนกลักษณะได้โดยพิจารณาจากคลิกของกราฟเหล่านั้น:

• กราฟคลัสเตอร์คือกราฟที่ส่วนประกอบที่เชื่อมต่อกันเรียกว่าคลิก (clique)
• กราฟบล็อกคือกราฟที่ส่วนประกอบที่เชื่อมต่อกันสองทางเรียกว่าคลิก
• กราฟคอร์ดัล (Chordal graph ) คือกราฟที่จุดยอดสามารถเรียงลำดับตามลำดับการกำจัดที่สมบูรณ์แบบ (perfect elimination ordering) ซึ่งเป็นลำดับที่จุดยอดข้างเคียงของแต่ละจุดยอดvที่มาทีหลังvในลำดับนั้นจะรวมกันเป็นกลุ่ม (clique)
• โคกราฟคือกราฟที่ซับกราฟแบบเหนี่ยวนำทั้งหมดมีคุณสมบัติที่ว่า กลุ่มคลิกสูงสุดใดๆ จะตัดกับเซตอิสระสูงสุด ใดๆ ที่จุดยอดเดียว
• กราฟช่วง (Interval graph)คือกราฟที่คลิกสูงสุด (maximal cliques) สามารถเรียงลำดับได้ในลักษณะที่ว่า สำหรับแต่ละจุดยอดvคลิกที่มีv อยู่ภายใน จะต้องอยู่ติดกันในลำดับการเรียง
• กราฟเส้นคือ กราฟที่ขอบของกราฟสามารถถูกคลุมด้วยคลิกที่ไม่ซ้ำกันระหว่างขอบ โดยที่แต่ละจุดยอดจะอยู่ในกลุ่มคลิกเพียงสองกลุ่มในกลุ่มคลิกเหล่านั้น
• กราฟสมบูรณ์คือ กราฟที่จำนวนคลิกเท่ากับจำนวนสีในทุกกราฟย่อยที่เกิดจากการเหนี่ยวนำ
• กราฟแยกส่วน (Split graph)คือกราฟที่คลิกบางคลิกมีจุดปลายอย่างน้อยหนึ่งจุดของทุกขอบ
• กราฟที่ปราศจากสามเหลี่ยมคือกราฟที่ไม่มีกลุ่มก้อนใดๆ นอกจากจุดยอดและขอบของกราฟเท่านั้น

นอกจากนี้ โครงสร้างทางคณิตศาสตร์อื่นๆ อีกมากมายก็เกี่ยวข้องกับคลิกในกราฟด้วย เช่น

• คอมเพล็กซ์คลิกของกราฟGคือคอมเพล็กซ์เชิงซิมพลิเชียลนามธรรมX ( G ) โดยมีซิมเพล็กซ์สำหรับทุกคลิกในG
• กราฟซิมเพล็กซ์เป็นกราฟแบบไม่มีทิศทาง κ( G ) ที่มีจุดยอดสำหรับคลิกทุกอันในกราฟGและขอบที่เชื่อมต่อคลิกสองอันที่แตกต่างกันเพียงจุดยอดเดียว เป็นตัวอย่างของกราฟมัธยฐานและเกี่ยวข้องกับพีชคณิตมัธยฐานบนคลิกของกราฟ: มัธยฐานm ( A , B , C ) ของคลิกสามอันA , BและCคือคลิกที่มีจุดยอดอยู่ในคลิกอย่างน้อยสองอันจาก^คลิก A , BและC ^{[ 5} ]
• ผลรวมคลิก (Clique-sum)เป็นวิธีการรวมกราฟสองกราฟเข้าด้วยกันโดยการผสานตามคลิกที่ใช้ร่วมกัน
• ความกว้างของคลิก (Clique-width)เป็นแนวคิดเกี่ยวกับความซับซ้อนของกราฟในแง่ของจำนวนป้ายกำกับจุดยอดที่แตกต่างกันขั้นต่ำที่จำเป็นในการสร้างกราฟจากผลรวมที่ไม่ทับซ้อนกัน การเปลี่ยนป้ายกำกับ และการดำเนินการที่เชื่อมต่อจุดยอดทุกคู่ที่มีป้ายกำกับที่กำหนด กราฟที่มีความกว้างของคลิกเท่ากับหนึ่งคือผลรวมที่ไม่ทับซ้อนกันของคลิกต่างๆ นั่นเอง
• จำนวนจุดตัดของกราฟ คือจำนวนคลิกขั้นต่ำที่จำเป็นในการครอบคลุมขอบทั้งหมดของกราฟ
• กราฟคลิกของกราฟ คือกราฟจุดตัดของกลุ่มคลิกสูงสุดของกราฟนั้น

แนวคิดที่เกี่ยวข้องอย่างใกล้ชิดกับกราฟย่อยสมบูรณ์ ได้แก่การแบ่งย่อยของกราฟสมบูรณ์และไมเนอร์ของกราฟ สมบูรณ์ โดยเฉพาะอย่างยิ่งทฤษฎีบทของ Kuratowskiและทฤษฎีบทของ Wagnerอธิบายลักษณะของกราฟระนาบด้วยการแบ่งย่อยสมบูรณ์ที่ต้องห้ามและ การแบ่งย่อย แบบทวิภาคสมบูรณ์และไมเนอร์ ตามลำดับ

ในวิทยาการคอมพิวเตอร์ปัญหาคลิกคือปัญหาการคำนวณในการหาคลิกสูงสุด หรือคลิกทั้งหมดในกราฟที่กำหนด ปัญหานี้เป็น ปัญหา NP-complete ซึ่ง เป็นหนึ่งใน 21 ปัญหาNP-complete ของ Karp ^{[ 6 ]}นอกจากนี้ยังไม่สามารถคำนวณได้ด้วยพารามิเตอร์คงที่และยากที่จะประมาณค่าอย่างไรก็ตาม มีการพัฒนา อัลกอริทึม มากมาย สำหรับการคำนวณคลิก โดยบางอัลกอริทึมทำงานในเวลาเลขชี้กำลัง (เช่นอัลกอริทึม Bron–Kerbosch ) หรือบางอัลกอริทึมก็เฉพาะเจาะจงสำหรับตระกูลกราฟ เช่นกราฟระนาบหรือกราฟสมบูรณ์ซึ่งสามารถแก้ปัญหาได้ในเวลาพหุนาม

คำว่า "clique" ในความหมายเชิงทฤษฎีกราฟ มาจากงานของLuce & Perry (1949)ซึ่งใช้กราฟย่อยสมบูรณ์ในการจำลองclique (กลุ่มคนที่รู้จักกันทั้งหมด) ในเครือข่ายสังคมFestinger (1949)ก็ใช้คำจำกัดความเดียวกันในบทความที่ใช้คำศัพท์ทางเทคนิคที่เข้าใจง่ายกว่า ทั้งสองงานกล่าวถึงการค้นหา clique ในเครือข่ายสังคมโดยใช้เมทริกซ์ สำหรับความพยายามอย่างต่อเนื่องในการจำลอง clique ในเครือข่ายสังคมโดยใช้ทฤษฎีกราฟ โปรดดูAlba (1973) , Peay (1974)และDoreian & Woodard (1994)เป็นต้น

ปัญหาต่างๆ มากมายในสาขาชีวสารสนเทศได้รับการจำลองโดยใช้คลิก ตัวอย่างเช่นBen-Dor, Shamir & Yakhini (1999)จำลองปัญหาการจัดกลุ่ม ข้อมูล การแสดงออกของยีนเป็นการหาจำนวนการเปลี่ยนแปลงขั้นต่ำที่จำเป็นในการแปลงกราฟที่อธิบายข้อมูลให้เป็นกราฟที่เกิดจากการรวมกันแบบไม่ทับซ้อนกันของคลิกTanay, Sharan & Shamir (2002)กล่าวถึง ปัญหา การจัดกลุ่มแบบสองมิติ ที่คล้ายกัน สำหรับข้อมูลการแสดงออกซึ่งกลุ่มต่างๆ จำเป็นต้องเป็นคลิกSugihara (1984)ใช้คลิกเพื่อจำลองช่องว่างทางนิเวศวิทยาในสายใยอาหาร Day & Sankoff (1986)อธิบายปัญหาการอนุมานต้นไม้แห่งวิวัฒนาการว่าเป็นปัญหาการหาคลิกสูงสุดในกราฟที่มีจุดยอดเป็นลักษณะเฉพาะของสายพันธุ์ โดยที่จุดยอดสองจุดจะใช้ขอบร่วมกันหากมีแผนภูมิวิวัฒนาการที่สมบูรณ์แบบซึ่งรวมลักษณะทั้งสองนั้นเข้าด้วยกันSamudrala & Moult (1998)ได้สร้างแบบจำลองการทำนายโครงสร้างโปรตีนว่าเป็นปัญหาของการค้นหาคลิกในกราฟซึ่งจุดยอดแทนตำแหน่งของหน่วยย่อยของโปรตีน และโดยการค้นหาคลิกในเครือข่ายปฏิสัมพันธ์ระหว่างโปรตีนSpirin & Mirny (2003)ได้ค้นพบกลุ่มของโปรตีนที่โต้ตอบกันอย่างใกล้ชิดและมีปฏิสัมพันธ์กับโปรตีนนอกกลุ่มน้อยการวิเคราะห์กราฟกำลังเป็นวิธีการลดความซับซ้อนของเครือข่ายชีวภาพที่ซับซ้อนโดยการค้นหาคลิกและโครงสร้างที่เกี่ยวข้องในเครือข่ายเหล่านี้

ในวิศวกรรมไฟฟ้า Prihar (1956)ใช้คลิกเพื่อวิเคราะห์เครือข่ายการสื่อสาร และPaull & Unger (1959)ใช้คลิกเพื่อออกแบบวงจรที่มีประสิทธิภาพสำหรับการคำนวณฟังก์ชันบูลีนที่ระบุบางส่วน นอกจากนี้ยังมีการใช้คลิกในการสร้างรูปแบบการทดสอบอัตโนมัติ : คลิกขนาดใหญ่ในกราฟความไม่เข้ากันของข้อผิดพลาดที่เป็นไปได้จะให้ขอบเขตล่างของขนาดชุดทดสอบ^{[ 7 ]} Cong & Smith (1993)อธิบายการประยุกต์ใช้คลิกในการค้นหาการแบ่งส่วนแบบลำดับชั้นของวงจรอิเล็กทรอนิกส์เป็นหน่วยย่อยที่เล็กกว่า

ในวิชาเคมีRhodes et al. (2003)ใช้คลิกเพื่ออธิบายสารเคมีในฐานข้อมูลเคมีที่มีความคล้ายคลึงกับโครงสร้างเป้าหมายในระดับสูงKuhl, Crippen & Friesen (1983)ใช้คลิกเพื่อจำลองตำแหน่งที่สารเคมีสองชนิดจะจับกัน

• เกมคลิก

• ไวส์สไตน์, เอริก ดับเบิลยู. , "Clique" , MathWorld
• ไวส์สไตน์, เอริค ดับเบิลยู. , "จำนวนคลิก" , MathWorld