הצגת המקור של הדף "משפט תומאסן על מעגלים זרים"

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

==גרסאות הדוקות יותר==
הוכחתו של תומאסן מראה שאפשר לבחור את <math>f</math> להיות
<math display="block">f(k)=(k+1)!</math>
תוצאה זאת רחוקה מלהיות הדוקה. תומסון מראה כי לכל <math>f</math> מתאימה מתקיים:
<math display="block">f(k)\geq 2k-1.</math> הוא גם משער שאפשר לבחור את <math>f</math> להיות
<math display="block">f(k)=2k-1.</math>
[[נוגה אלון|אלון]] התקרב להוכחת השערה זאת והוכיח שאפשר לבחור את <math>f</math> להיות
<math display="block">f(k)=64k.</math>
עבור ערכים קטנים של <math>k</math> אפשר לקבל תוצאות טובות יותר. לדוגמה, ההוכחה של תומאסן מראה כי עבור <math>k=2</math> אפשר לבחור את <math>f(k)</math> להיות 3.

במילים אחרות:

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

==שימושים==
המשפט משמש בין היתר לפתרון בעיה על פירוק של גרף לתת-קבוצות. הבעיה עלתה בקבוצת ה[[פייסבוק]] "חפירות על מתמטיקה"{{הערה|[https://www.facebook.com/groups/305092099620459/permalink/2280813702048279/ כאן]}} ונפתרה על ידי [[נוגה אלון]]. הבעיה מדברת על שיבוץ תלמידים לכיתות. לפי תנאי הבעיה נאמר לכל אחד מהתלמידים שהוא יכול לבחור <math>k</math> חברים, ומובטח לו שלפחות אחד מהם יהיה איתו בכיתה. השאלה היא האם קבוצה של תלמידים יכולה לתאם את הבחירות שלהם כך שבהכרח ישובצו בכיתה אחת. קל להראות שאם <math>k<3</math> אז התשובה היא כן. אלון הוכיח באמצעות משפט תומאסן (עבור <math>n=2</math>) שאם <math>k\geq 3</math> אז התשובה היא לא.{{הערה|[https://www.tau.ac.il/~nogaa/PDFS/coalition.pdf High School Coalitions]|כיוון=שמאל}}

==ראו גם==
* [[פורטל:מתמטיקה/חידה/16|חידת הכתה המופרעת]] - חידה קשורה ב[[פורטל:מתמטיקה|פורטל מתמטיקה]] של ה[[הוויקיפדיה העברית|וויקיפדיה העברית]].

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

[[קטגוריה:משפטים בתורת הגרפים]]