משפט תומאסן על מעגלים זרים – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
יצירת דף עם התוכן "'''משפט תומסון''' הוא משפט מתורת הגרפים שאמר שאם הדרגה היצאת של כל קודקוד בגרף מכוון נתון גדולה מספיק אז בגרף יש מספר גדול כרצונינו של מעגלים זרים בקודקודיהם. המשפט הוכח בשנת 1983 על ידי קרטן תומסון. בשנת 1996 הוכיח נוגה אלון גרסה הדוקה יותר של המשפט. מ..." |
|||
שורה 1:
'''משפט תומסון''' הוא משפט מתורת הגרפים שאמר שאם הדרגה היצאת של כל קודקוד בגרף מכוון נתון גדולה מספיק אז בגרף יש מספר גדול כרצונינו של מעגלים זרים בקודקודיהם. המשפט הוכח בשנת [[1983]] על ידי [[קרטן תומסון]]. בשנת [[1996]] הוכיח [[נוגה אלון]] גרסה הדוקה יותר של המשפט. מלבד שימושים בתורת הגרפים, למשפט גם שימוש בתורת המשחקים.
==ניסוח המשפט==
הניסוח מדיוק של המשפט הו כדילקמן:
קיימת פונקציה <math>f:\N \to \N</math> כך שעבור כל [[מספר טבעי]] <math>n</math> וגרף מכוון <math>\Gamma</math> כך שדרגת היציאה של כל קודקוד ב- <math>\Gamma</math> היא לפחות <math>f(n)</math>, קימים לפחות <math>n</math> מעגלים מכוונים ב-<math>\Gamma</math> שקבוצות קודקודיהם זרים בזוגות.
==גרסאות הדוקות יותר==
==שימוש בתורת המשחקים==
| |||