גרף שלם

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש
Disambig RTL.svg המונח "קליקה" מפנה לכאן. לערך העוסק בתופעה חברתית, ראו קליקה (חברה).
הגרף השלם K_6

בתורת הגרפים, גרף שלם (או "גרף מלא") \ G=(V,E) הוא גרף אשר כל שני צמתים \ n_1,n_2\in V בו מחוברים על ידי קשת. נהוג לסמן גרף שלם בעל \ n צמתים ב-\ K_n.

גרף שלם הוא הקליקה (clique) של עצמו. קליקה בגרף לא מכוון היא תת-קבוצה של הקודקודים שבה כל שני קודקודים מחוברים בקשת.

בגרף שלם בעל n קודקודים ישנן n(n − 1)/2 קשתות (ראו מספר משולשי: קומבינטוריקה).

בתורת הסיבוכיות הוכח שבעיית מציאת תת-גרף שלם מקסימלי בגרף נתון נכללת בקטגוריה NP-קשה, והצגתה כבעיית הכרעה ("האם קיים תת-גרף שלם מסדר הגדול מ-k?") היא בקטגוריה NP-שלמה.

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

P mathematics.svg ערך זה הוא קצרמר בנושא מתמטיקה. אתם מוזמנים לתרום לוויקיפדיה ולהרחיב אותו.