הלמה של שפרנר

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש

הלמה של שפרנר עוסקת בצביעות של משולשים והוכחה על ידי המתמטיקאי הגרמני עמנואל שפרנר ב-1928.

הצגת הבעיה[עריכת קוד מקור | עריכה]

בהינתן טריאנגולציה של משולש למשולשים יותר קטנים, נניח כי קיימת תלת צביעה של קודקודי הטריאנגולציה בשלושה צבעים כך ששלושת קודקודי המשולש הגדול צבועים בצבעים שונים וגם כל קודקוד פנימי צבוע באחד משני הצבעים בהם צבועים קודקודי המשולש הגדול שנמצאים בקצות הצלע עליה מונח הקודקוד הפנימי, אז עבור לפחות אחד מהמשולשים הקטנים – קודקודיו צבועים בשלושה צבעים שונים.

Sperner2d.svg

באופן פורמלי, נסמן את קדקודי המשולש הגדול ב V_{1},V_{2},V_{3} ונדרוש שהקודקוד V_{i} צבוע בצבע i\in\{1,2,3\}. המשפט טוען שאם הקדקודים שעל צלע המשולש הגדול בין V_{i} ל V_{j} צבועים באחד משני הצבעים i,j, אז קיים משולש קטן "צבעוני" כלומר כל אחד מקודקודיו צבוע בצבע שונה.

הוכחה[עריכת קוד מקור | עריכה]

נסמן ב K את מספר המשולשים הקטנים הצבעוניים. נוכיח ש K אי־זוגי ובפרט אינו 0. נסתכל על קבוצת המשולשים הקטנים T_{1},T_{2},...,T_{n} הכולל גם את המשולש המשלים של המשולש הגדול כאשר פורסים אותו על ספירה וקדקודיו הם V_{1},V_{2},V_{3}, נכנה שני משולשים מקבוצה זו "חברים" אם הם שכנים וקודקודיהם צבועים בצבעים {1,2}.

לכל משולש "צבעוני" (מלבד המשולש המשלים) יש חבר אחד ויחיד, למשולשים שצבועים בצבעים {1,2} יש שני חברים, ולכל השאר (מלבד אולי המשולש המשלים) – אין "חברים" כלל. בפרט מבין המשולשים הקטנים רק ל"צבעוניים" יש מספר אי זוגי של חברים. נשים לב ש:

  1. למשולש המשלים יש מספר אי זוגי של "חברים" כי לאורך הצלע בין V_{1} ל V_{2} הצבע מתחלף 1 \leftrightarrow  2 מספר אי זוגי של פעמים וכל פעם כזו מוסיפה חבר.
  2. סכום מספר החברים של כל המשולשים T_{1},T_{2},...,T_{n} הוא זוגי כי כל יחס "חברות" נספר פעמיים.

נובע כי K אי־זוגי כנדרש.

ראו גם[עריכת קוד מקור | עריכה]

הערות שוליים[עריכת קוד מקור | עריכה]

  1. ^ (Christos H. Papadimitriou, On the Complexity of the Parity Argument and Other Inefficient Proofs of Existence. J. Comput. Syst. Sci. 48(3): 498-532 (1994

לקריאה נוספת[עריכת קוד מקור | עריכה]

  • Noam Nisan, Tim Roughgarden, Eva Tardos, Vijay V. Vazirani, Algorithmic Game Theory, New York: Cambridge University Press, 2007. ISBN 978-0-521-87282-9

קישורים חיצוניים[עריכת קוד מקור | עריכה]