קליקה (תורת הגרפים)

גרף בעל 2 קליקות בגודל 4 (כחול כהה), 19 קליקות בגודל 3 (כחול בהיר), 42 קליקות מגודל 2 (קשתות) ו-23 קליקות בגודל אחד (קודקודים). מספר הקליקה של הגרף הוא 4.

בתורת הגרפים, קליקה היא קבוצת קודקודים בגרף בלתי מכוון, אשר כל זוג קודקודים שונים בה מחובר על ידי קשת; כלומר, תת-הגרף המושרה על ידה מהווה גרף שלם.

הגדרות

• קליקה בגרף בלתי מכוון $G=(V,E)$ היא תת-קבוצה $C\subseteq V$ כך שבין כל זוג קודקודים שונים בקבוצה קיימת קשת.
• קליקה מקסימלית או קליקה מרבית בגרף בלתי מכוון $G$ היא קליקה שלא ניתנת להרחבה על ידי הוספת קודקוד נוסף לקבוצה, כלומר קליקה אשר לא חלקית לקליקה גדולה יותר.
• קליקת מקסימום בגרף בלתי מכוון $G$ היא קליקה, כך שלא קיימת בגרף קליקה בעלת מספר קודקודים גדול יותר.
• מספר הקליקה בגרף בלתי מכוון $G$ מסומן $\omega (G)$ ושווה לגודל המקסימלי של קליקה ב־$G$.

בעיית הקליקה

במדעי המחשב, בעיית הקליקה היא הבעיה החישובית שבמציאת קליקת מקסימום בגרף בלתי מכוון נתון. בעיה זו היא בעיה NP-שלמה, ומהווה אחת מ-21 הבעיות ה-NP-שלמות של קארפ.

לבעיה זו פותחו מספר אלגוריתמים בעלי זמן ריצה מעריכי, אולם קיימים לבעיה גם פתרונות בעלי זמן ריצה פולינומי בסוגי גרף מסוימים, כגון גרף מישורי וגרף מושלם.

ראו גם

• משפט רמזי

קישורים חיצוניים

• קליקה, באתר MathWorld (באנגלית)