תוכן עניינים
13 יחסים: NP (מחלקת סיבוכיות), מספר כרומטי, מסלול המילטוני, פונקציה חד-חד-ערכית ועל, פירוק לגורמים, תורת הגרפים, גרף (קומבינטוריקה), גרף (תורת הגרפים), גרף מושלם, גרף קשיר, גרף דו-צדדי, דרגה (תורת הגרפים), ההיררכיה הפולינומית.
NP (מחלקת סיבוכיות)
במדעי המחשב, NP היא מחלקת סיבוכיות חשובה, שמכילה בעיות הנקראות "בעיות הכרעה", המוגדרות על ידי השאלה: בהינתן קלט, האם הוא מקיים תכונה נתונה? (דוגמה: הקלט יכול להיות מספר טבעי, והתכונה: המספר הוא זוגי, או ראשוני).
לִרְאוֹת איזומורפיזם של גרפים וNP (מחלקת סיבוכיות)
מספר כרומטי
#הפניה גרף n-צביע.
לִרְאוֹת איזומורפיזם של גרפים ומספר כרומטי
מסלול המילטוני
מעגל המילטוני על הקשתות של תריסרון מסע הפרש במסלול סגור בתורת הגרפים, מסלול המילטוני הוא מסלול בגרף מכוון או בלתי מכוון העובר בכל צומת בדיוק פעם אחת.
לִרְאוֹת איזומורפיזם של גרפים ומסלול המילטוני
פונקציה חד-חד-ערכית ועל
במתמטיקה, פונקציה חד-חד-ערכית ועל (נקראת גם בִּייקציָה; באנגלית: Bijection) מקבוצה X לקבוצה Y היא פונקציה המתאימה לכל איבר של X איבר אחד ויחיד של Y. פונקציה חח"ע (חד חד ערכית) ועל נקראת "פונקציה הפיכה".
לִרְאוֹת איזומורפיזם של גרפים ופונקציה חד-חד-ערכית ועל
פירוק לגורמים
במתמטיקה, פירוק לגורמים הוא פירוקו של אובייקט מתמטי כגון מספר או פולינום, לרכיבים קטנים יותר, הקרויים גורמים, כך שמכפלת הגורמים זה בזה תתן את האובייקט המקורי.
לִרְאוֹת איזומורפיזם של גרפים ופירוק לגורמים
תורת הגרפים
תורת הגרפים היא ענף של המתמטיקה העוסק בתכונותיהם של גרפים.
לִרְאוֹת איזומורפיזם של גרפים ותורת הגרפים
גרף (קומבינטוריקה)
#הפניה גרף (תורת הגרפים).
לִרְאוֹת איזומורפיזם של גרפים וגרף (קומבינטוריקה)
גרף (תורת הגרפים)
גרף לא מכוון בעל 6 קודקודים ו-7 קשתות גרף מכוון בעל 4 קודקודים ו-5 קשתות בתורת הגרפים, גרף הוא ייצוג מופשט של קבוצה של אובייקטים, כאשר כל זוג אובייקטים בקבוצה עשויים להיות מקושרים זה לזה.
לִרְאוֹת איזומורפיזם של גרפים וגרף (תורת הגרפים)
גרף מושלם
בתורת הגרפים, גרף מושלם הוא גרף שבו בכל תת גרף מושרה, גודל הקליקה המקסימלית שווה למספר הצביעה של תת-הגרף.
לִרְאוֹת איזומורפיזם של גרפים וגרף מושלם
גרף קשיר
גרף לא קשיר: אין מסלול המקשר את הקודקודים A ו-B. לגרף יש שני מרכיבי קשירות. הערה: יש לשים לב שב"הצטלבות" במרכז הגרף אין קודקוד, כך שלמעשה אין זו הצטלבות, אין קשר בין הצלעות בה.
לִרְאוֹת איזומורפיזם של גרפים וגרף קשיר
גרף דו-צדדי
דוגמה לגרף דו-צדדי בתורת הגרפים, גרף דו-צדדי (נקרא גם גרף דו-חלקי) הוא גרף שבו ניתן לחלק את הקודקודים לשתי קבוצות זרות, כך שלא קיימת קשת בין שני קודקודים השייכים לאותה הקבוצה.
לִרְאוֹת איזומורפיזם של גרפים וגרף דו-צדדי
דרגה (תורת הגרפים)
גרף לא מכוון בו מצוינות דרגות הקודקודים בתורת הגרפים, דרגה של צומת מתארת את מספר הקשתות המקושרות לצומת מסוים.
לִרְאוֹת איזומורפיזם של גרפים ודרגה (תורת הגרפים)
ההיררכיה הפולינומית
בתורת הסיבוכיות, ההיררכיה הפולינומית היא אוסף של מחלקות סיבוכיות שמכלילות את המחלקות P, NP ו-co-NP באמצעות אורקל.
לִרְאוֹת איזומורפיזם של גרפים וההיררכיה הפולינומית