קליקה (תורת הגרפים)
בתורת הגרפים, קליקה היא קבוצת קודקודים בגרף בלתי מכוון, אשר כל זוג קודקודים שונים בה מחובר על ידי קשת; כלומר, תת-הגרף המושרה על ידה מהווה גרף שלם.[1]
הגדרותעריכה
- קליקה בגרף בלתי מכוון היא תת-קבוצה כך שבין כל זוג קודקודים שונים בקבוצה קיימת קשת.
- קליקה מקסימלית או קליקה מרבית בגרף בלתי מכוון היא קליקה שלא ניתנת להרחבה על ידי הוספת קודקוד נוסף לקבוצה, כלומר קליקה אשר לא חלקית לקליקה גדולה יותר.
- קליקת מקסימום בגרף בלתי מכוון היא קליקה, כך שלא קיימת בגרף קליקה בעלת מספר קודקודים גדול יותר.
- מספר הקליקה בגרף בלתי מכוון מסומן ושווה לגודל המקסימלי של קליקה ב־ .
בעיית הקליקהעריכה
במדעי המחשב, בעיית הקליקה היא הבעיה החישובית שבמציאת קליקת מקסימום בגרף בלתי מכוון נתון. בעיה זו היא בעיה NP-שלמה, ומהווה אחת מ-21 הבעיות ה-NP-שלמות של קארפ.
לבעיה זו פותחו מספר אלגוריתמים בעלי זמן ריצה מעריכי, אולם קיימים לבעיה גם פתרונות בעלי זמן ריצה פולינומי בסוגי גרף מסוימים, כגון גרף מישורי וגרף מושלם.