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

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

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

הגדרות[עריכת קוד מקור | עריכה]

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

בעיית הקליקה[עריכת קוד מקור | עריכה]

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

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

ראו גם[עריכת קוד מקור | עריכה]

קישורים חיצוניים[עריכת קוד מקור | עריכה]

הערות שוליים[עריכת קוד מקור | עריכה]

  1. ^ Clique, באתר MathWorld