תוכן עניינים
20 יחסים: FNP, NP (מחלקת סיבוכיות), Proofs from THE BOOK, מספר כרומטי, מעגל (תורת הגרפים), משפט ארבעת הצבעים, משפט לובאס-קנזר, פרס דייקסטרה, צביעת קשתות, צומת (תורת הגרפים), קוגרף, תורת הגרפים, זרימה לא מתאפסת, גרף מושלם, גרף מיתרי, גרף פרש, גרף דו-צדדי, הלמה של שפרנר, הדס שכנאי, הוכחה באפס ידיעה.
FNP
בתורת הסיבוכיות, מחלקת הסיבוכיות FNP היא ההרחבה לבעיית הפונקציה של מחלקת בעיות ההכרעה NP.
לִרְאוֹת גרף n-צביע וFNP
NP (מחלקת סיבוכיות)
במדעי המחשב, NP היא מחלקת סיבוכיות חשובה, שמכילה בעיות הנקראות "בעיות הכרעה", המוגדרות על ידי השאלה: בהינתן קלט, האם הוא מקיים תכונה נתונה? (דוגמה: הקלט יכול להיות מספר טבעי, והתכונה: המספר הוא זוגי, או ראשוני).
לִרְאוֹת גרף n-צביע וNP (מחלקת סיבוכיות)
Proofs from THE BOOK
Proofs from THE BOOK הוא ספר הוכחות מתמטיות מאת מרטין אייגנר וגונטר זיגלר.
לִרְאוֹת גרף n-צביע וProofs from THE BOOK
מספר כרומטי
#הפניה גרף n-צביע.
לִרְאוֹת גרף n-צביע ומספר כרומטי
מעגל (תורת הגרפים)
בתורת הגרפים, מעגל (באנגלית: Cycle graph או Circular graph) הוא גרף המורכב ממסלול לא-ריק המתחיל ומסתיים באותו צומת, כאשר הצמתים היחידים שחוזרים על עצמם הם הצומת הראשון והצומת האחרון.
לִרְאוֹת גרף n-צביע ומעגל (תורת הגרפים)
משפט ארבעת הצבעים
משפט ארבעת הצבעים הוא תוצאה בולטת בהיסטוריה של הטופולוגיה הקומבינטורית ושל תורת הגרפים.
לִרְאוֹת גרף n-צביע ומשפט ארבעת הצבעים
משפט לובאס-קנזר
בתורת הגרפים, משפט לובאס-קנזר הוא משפט מתמטי שקובע את מספר הצביעה של גרף קנזר.
לִרְאוֹת גרף n-צביע ומשפט לובאס-קנזר
פרס דייקסטרה
פרס אדסחר ו.
לִרְאוֹת גרף n-צביע ופרס דייקסטרה
צביעת קשתות
הגרף השלם על שמונה קודקודים צביעת קשתות של גרף היא השמה של צבעים לקשתות הגרף כך שלשום קודקוד אין זוג קשתות הנוגעות בו וצבועות באותו הצבע.
לִרְאוֹת גרף n-צביע וצביעת קשתות
צומת (תורת הגרפים)
גרף לא מכוון בעל 6 קודקודים ו-7 קשתות בתורת הגרפים, צומת או קודקוד (באנגלית: Vertex) הוא יחידת היסוד ממנה מורכב הגרף.
לִרְאוֹת גרף n-צביע וצומת (תורת הגרפים)
קוגרף
בתורת הגרפים, קוגרף הוא גרף הנוצר מקודקודים בודדים על ידי הפעלות של איחוד זר ואופרטור הגרף המשלים (גרף שיש בו קשת אםם אין קשת בגרף המקורי).
לִרְאוֹת גרף n-צביע וקוגרף
תורת הגרפים
תורת הגרפים היא ענף של המתמטיקה העוסק בתכונותיהם של גרפים.
לִרְאוֹת גרף n-צביע ותורת הגרפים
זרימה לא מתאפסת
זרימה לא מתאפסת בגרף מכוון מעל חבורה אבלית היא השמה של אברי החבורה (פרט לאפס) לקשתות של הגרף כך שבכל קודקוד סכום הקשתות היוצאות יהיה שווה לסכום הקשתות הנכנסות.
לִרְאוֹת גרף n-צביע וזרימה לא מתאפסת
גרף מושלם
בתורת הגרפים, גרף מושלם הוא גרף שבו בכל תת גרף מושרה, גודל הקליקה המקסימלית שווה למספר הצביעה של תת-הגרף.
לִרְאוֹת גרף n-צביע וגרף מושלם
גרף מיתרי
בתורת הגרפים, גרף מיתרי הוא גרף שבו כל מעגל באורך 4 או יותר מכיל מיתר, שהוא צלע המחברת בין שני צמתים לא-רצופים במעגל.
לִרְאוֹת גרף n-צביע וגרף מיתרי
גרף פרש
דרגה שלו. גרף פרש הוא גרף שצמתיו מייצגים משבצות של לוח שחמט, וקשתותיו מייצגות מסעים חוקיים של פרש (כלומר שני קודקודים מחוברים אם ורק אם פרש יכול לעבור בצעד יחיד בין המשבצות שהם מייצגים).
לִרְאוֹת גרף n-צביע וגרף פרש
גרף דו-צדדי
דוגמה לגרף דו-צדדי בתורת הגרפים, גרף דו-צדדי (נקרא גם גרף דו-חלקי) הוא גרף שבו ניתן לחלק את הקודקודים לשתי קבוצות זרות, כך שלא קיימת קשת בין שני קודקודים השייכים לאותה הקבוצה.
לִרְאוֹת גרף n-צביע וגרף דו-צדדי
הלמה של שפרנר
הלמה של שפרנר עוסקת בצביעות של משולשים והוכחה על ידי המתמטיקאי הגרמני עמנואל שפרנר ב-1928.
לִרְאוֹת גרף n-צביע והלמה של שפרנר
הדס שכנאי
הדס שכנאי היא מדענית מחשב ישראלית ופרופסור בטכניון.
לִרְאוֹת גרף n-צביע והדס שכנאי
הוכחה באפס ידיעה
במדעי המחשב ובקריפטוגרפיה, הוכחה באפס ידיעה או פרוטוקול אפס ידיעה, היא מערכת הוכחה אינטראקטיבית, שבה צד אחד (מוכיח או טוען) משכנע את הצד השני (מוודא) באמיתות טענה, בסבירות מכרעת (לא באופן מוחלט), מבלי לחשוף כל מידע בנוגע לטענה עצמה, שאי-אפשר היה להשיגו באמצעים אחרים (פרט לעצם נכונותה של הטענה).
לִרְאוֹת גרף n-צביע והוכחה באפס ידיעה
אזכור
ידוע גם בשם צביעת קודקודים, צביעת גרף, צביעה של גרף, צביעה של גרפים.