אנו יכולים גם לקרוא לתיאוריית לחיצת היד כמשפט סכום התואר או לחיצת היד Lemma. תיאוריית לחיצת היד קובעת שסכום התואר של כל הקודקודים של גרף יהיה כפול ממספר הקצוות שמכיל הגרף הזה. הייצוג הסמלי של תורת לחיצת היד מתואר כדלקמן:
כאן,
'd' משמש לציון דרגת הקודקוד.
'v' משמש לציון הקודקוד.
'e' משמש לציון הקצוות.
משפט לחיצת יד:
יש כמה מסקנות במשפט לחיצת היד, שיש להסיק, המתוארות כך:
בכל גרף:
- חייבים להיות מספרים זוגיים לסכום המדרגה של כל הקודקודים.
- אם יש דרגות אי-זוגיות לכל הקודקודים, אזי סכום המדרגות של הקודקודים האלה חייב תמיד להישאר זוגי.
- אם יש כמה קודקודים בעלי דרגה אי זוגית, אז מספר הקודקודים הללו יהיה זוגי.
דוגמאות לתיאוריית לחיצת היד
ישנן דוגמאות שונות לתיאוריית לחיצת ידיים, וחלק מהדוגמאות מתוארות כך:
דוגמה 1: כאן, יש לנו גרף שדרגת כל קודקוד היא 4 ו-24 קצוות. כעת נגלה את מספר הקודקודים בגרף זה.
פִּתָרוֹן: בעזרת הגרף לעיל, קיבלנו את הפרטים הבאים:
תואר של כל קודקוד = 24
מספר הקצוות = 24
כעת נניח את מספר הקודקודים = n
בעזרת משפט לחיצת היד, יש לנו את הדברים הבאים:
סכום המעלה של כל הקודקודים = 2 * מספר הקצוות
כעת נכניס את הערכים הנתונים לנוסחת לחיצת היד לעיל:
n*4 = 2*24
n = 2*6
n = 12
לפיכך, בגרף G, מספר הקודקודים = 12.
דוגמה 2: כאן, יש לנו גרף שיש לו 21 קצוות, 3 קודקודים של מדרגה 4, וכל שאר הקודקודים של מדרגה 2. כעת נגלה את המספר הכולל של קודקודים בגרף זה.
פִּתָרוֹן: בעזרת הגרף לעיל, קיבלנו את הפרטים הבאים:
מספר קודקודים של מעלות 4 = 3
מספר הקצוות = 21
לכל שאר הקודקודים יש תואר 2
כעת נניח את מספר הקודקודים = n
בעזרת משפט לחיצת היד, יש לנו את הדברים הבאים:
סכום המדרגה של כל הקודקודים = 2 * מספר הקצוות
כעת נכניס את הערכים הנתונים לנוסחת לחיצת היד לעיל:
3*4 + (n-3) * 2 = 2*21
12+2n-6 = 42
2n = 42 - 6
2n=36
n = 18
לפיכך, בגרף G, המספר הכולל של הקודקודים = 18.
דוגמה 3: כאן, יש לנו גרף שיש לו 35 קצוות, 4 קודקודים בדרגה 5, 5 קודקודים בדרגה 4 ו-4 קודקודים בדרגה 3. כעת נגלה את מספר הקודקודים בעלי תואר 2 בגרף זה.
פִּתָרוֹן: בעזרת הגרף לעיל, קיבלנו את הפרטים הבאים:
מספר הקצוות = 35
מספר קודקודים של מעלות 5 = 4
מספר מעלות 4 קודקודים = 5
מספר מעלות 3 קודקודים = 4
כעת נניח את מספר מעלות 2 קודקודים = n
בעזרת משפט לחיצת היד, יש לנו את הדברים הבאים:
סכום המדרגה של כל הקודקודים = 2 * מספר הקצוות
כעת נכניס את הערכים הנתונים לנוסחת לחיצת היד לעיל:
4*5 + 5*4 + 4*3 + n*2 = 2*35
20 + 20 + 12 + 2n = 70
52+2n = 70
2n = 70-52
2n = 18
n = 9
לפיכך, בגרף G, מספר קודקודים של מעלות 2 = 9.
מצביע הפנייה
דוגמה 4: כאן, יש לנו גרף בעל 24 קצוות, והדרגה של כל קודקוד היא k. כעת נגלה את המספר האפשרי של קודקודים מהאפשרויות הנתונות.
- חֲמֵשׁ עֶשׂרֵה
- עשרים
- 8
- 10
פִּתָרוֹן: בעזרת הגרף לעיל, קיבלנו את הפרטים הבאים:
מספר הקצוות = 24
תואר של כל קודקוד = k
כעת נניח את מספר הקודקודים = n
בעזרת משפט לחיצת היד, יש לנו את הדברים הבאים:
סכום המדרגה של כל הקודקודים = 2 * מספר הקצוות
כעת נכניס את הערכים הנתונים לנוסחת לחיצת היד לעיל:
N*k = 2*24
K = 48/כ
חובה שמספר שלם יכיל את המידה של כל קודקוד.
אז אנחנו יכולים להשתמש רק בסוגי הערכים של n במשוואה שלמעלה שמספקת לנו ערך שלם של k.
כעת, נבדוק את האפשרויות הנתונות לעיל על ידי הצבתן במקום n אחת אחת כך:
- עבור n = 15, נקבל k = 3.2, שאינו מספר שלם.
- עבור n = 20, נקבל k = 2.4, שאינו מספר שלם.
- עבור n = 8, נקבל k = 6, שהוא מספר שלם, וזה מותר.
- עבור n = 10, נקבל k = 4.8, שאינו מספר שלם.
לפיכך, האפשרות הנכונה היא אפשרות C.