גרף מלא

מתוך ויקיפדיה, האנציקלופדיה החופשית

יש לך הודעות חדשות (השווה לגרסה הקודמת).

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

גרף מלא נקרא לעתים קליקה או גרף שלם.

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

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


מקור: http://he.wikipedia.org../../../%D7%92/%D7%A8/%D7%A3/%D7%92%D7%A8%D7%A3_%D7%9E%D7%9C%D7%90.html
שפות אחרות