משפט תומאסן על מעגלים זרים – הבדלי גרסאות

{{לפשט}}

'''משפט תומסון''' הוא [[משפט (מתמטיקה)|משפט]] ב[[תורת הגרפים]] שאומר שאם ה[[דרגה (תורת הגרפים)|דרגה]] היוצאת של כל קודקוד ב[[גרף מכוון]] נתון גדולה מספיק אז בגרף יש מספר גדול כרצונינו של [[מעגל (תורת הגרפים)|מעגל]]ים זרים בקודקודיהם. המשפט הוכח בשנת [[1983]] על ידי [[קרטן תומסון]].{{הערה| C. Thomassen, Disjoint cycles in digraphs, Combinatorica 3 (1983), 393-396.|כיוון=שמאל}} בשנת [[1996]] הוכיח [[נוגה אלון]] גרסה הדוקה יותר של המשפט.{{הערה| N. Alon, Disjoint directed cycles, J. Combinatorial Theory, Ser. B 68 (1996), 167-178|כיוון=שמאל}} מלבד שימושים בתורת הגרפים, למשפט גם שימוש ב[[תורת המשחקים]].

 

עבור כל גרף מכוון <math>\Gamma</math> כך שדרגת היציאה של כל קודקוד ב- <math>\Gamma</math> היא לפחות <math>3</math>, קימים לפחות <math>2</math> מעגלים מכוונים ב-<math>\Gamma</math> הזרים בקודקודיהם.

==הערות שוליים==

{{הערות שוליים}}