פורטל:מתמטיקה/חידה/16/פתרון בונוס – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
אין תקציר עריכה |
|||
שורה 97:
}} משפט זה משחק תפקוד דומה לזה של [[#למה 8|למה 8]] בהוכחה כאן. המשפט אומר שבכל [[גרף מכוון]] שדרגת היציא של כל קודקוד בו היא לפחת 3 קיימים שני מעגלים (מכוונים) שקבוצות קוקודיהם זרות.
קל להסיק את המשפט של תומאסן מהבעיה כאן. כך שלמעשה
במאמרו, תומאסן דן בקריטריונים לכך שבגרף יהיו מספר מעגלים זרים בקודקודיהם במונחים של היציא המינימלית. במאמר אחר{{הערה| N. Alon, Disjoint directed cycles, J. Combinatorial Theory, Ser. B 68 (1996), 167-178}} אלון מקבל תצואה הדוקה יותר לגבי שאלה זאת.
==הערות שוליים==
| |||