למת לחיצות הידיים

בגרף יש מספר זוגי של צמתים (הצמתים 2, 4, 5, 6) בעלי דרגה אי זוגית. וסכום הדרגות של הצמתים הוא 14=2+3+2+3+3+1 שהוא פעמיים מספר הקשתות

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

הלמה היא תוצאה של נוסחת סכום הדרגות (שנקראת לפעמים גם למת לחיצת הידיים), לכל גרף הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle G} מתקיים:

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \sum_{v\in V}deg(v)=2|E|}

כאשר $E$ מציין את מספר הקשתות, $V$ מציין מספר הצמתים של $G$ ו- $deg(v)$ מציין את הדרגה של הצומת $v$ .

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

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

הוכחה

נוכיח קודם את נוסחת סכום הדרגות ובאמצעותה נוכיח את הלמה:

נספור בשתי דרכים שונות את מספר הזוגות $(v,e)$ כאשר $e$ מסמל קשת ו- $v$ הוא צומת ש- $e$ יוצאת ממנו, כל צומת $v$ נמצא ב-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle deg(v)} זוגות (שכן יוצאות מהצומת הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle deg(v)} קשתות), לכן מספר הזוגות הוא סכום כל דרגות הצמתים בגרף. אולם, ניתן לספור גם לפי הקשתות, כל קשת הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle e} נמצאת ב-2 זוגות (עם כל אחד מהקצוות של הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle e} ), ולכן מספר הזוגות הוא גם פעמיים מספר הקשתות. כלומר קיבלנו את השוויון הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \sum_{v\in V}deg(v)=2|E|} .

נוכיח באמצעות השוויון הקודם את הלמה:

נניח בשלילה שיש מספר אי זוגי הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle k} של צמתים אי זוגיים בגרף לא מכוון כלשהו, סכום כל הדרגות של הצמתים האי זוגיים הוא אי זוגי (כיוון שחיברנו מספרים אי זוגיים מספר אי זוגי של פעמים), סכום הדרגות של הצמתים בעלי דרגה זוגית הוא זוגי (חיבור מספרים זוגיים תמיד יוצא מספר זוגי). לכן הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \sum_{v\in V}deg(v)} הוא מספר אי זוגי (כחיבור של מספר זוגי ומספר אי זוגי). אבל מתקיים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \sum_{v\in V}deg(v)=2|E|} . בסתירה לכך שצד שמאל של השוויון הוא אי זוגי, ולכן מספר הצמתים האי זוגיים בכל גרף לא מכוון הוא זוגי.

גרפים רגולריים

מנוסחת סכום הדרגות נקבל שלכל גרף $r$ -רגולרי בעל הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} צמתים יש הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle nr/2} קשתות^[1]. אם הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle r} אי זוגי, מספר הקשתות בגרף חייב להתחלק ב-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle r} . כלומר, אם הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle r} אי זוגי בגרף יש מספר זוגי של צמתים.

גרפים אינסופיים

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

הערות שוליים

^ Aldous, Joan M.; Wilson, Robin J. (2000), "Theorem 2.2", Graphs and Applications: an Introductory Approach, Undergraduate Mathematics Series, The Open University, Springer-Verlag, p. 44, ISBN 978-1-85233-259-4

הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0

31430345למת לחיצות הידיים

[1] Aldous, Joan M.; Wilson, Robin J. (2000), "Theorem 2.2", Graphs and Applications: an Introductory Approach, Undergraduate Mathematics Series, The Open University, Springer-Verlag, p. 44, ISBN 978-1-85233-259-4

[1]

למת לחיצות הידיים

תוכן עניינים

הוכחה

גרפים רגולריים

גרפים אינסופיים

הערות שוליים

תפריט ניווט

למת לחיצות הידיים

הוכחה

גרפים רגולריים

גרפים אינסופיים

הערות שוליים

תפריט ניווט

חיפוש