דרגה (תורת הגרפים)

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

יש לך הודעות חדשות (השווה לגרסה הקודמת).

דרגה של צומת היא מונח בתורת הגרפים, שמתאר את מספר הקשתות המקושרות לצומת מסוים. זהו המידע הבסיסי ביותר שאפשר למסור על צומת בגרף, משום שהוא מתאר את תמונת העולם המקומית של הקודקודים שלו. גרף שדרגות כל הצמתים בו שוות שוות ל־k נקרא גרף k־רגולרי, ונהוג לומר שלדרגתו של הגרף היא k. דרגה של צומת $\,v$ מסומנת כ־ $\,\deg(v)$ .

[עריכה] גרפים בלתי-מכוונים

גרף בלתי-מכוון בעל 6 צמתים ו־7 קשתות

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

הדרגות של הצמתים בגרף משמאל מתוארות בטבלה הבאה:

צומת	1	2	3	4	5	6
דרגה	2	3	2	3	3	1

[עריכה] גרפים מכוונים

גרף מכוון בעל 4 צמתים ו־5 קשתות

בגרפים מכוונים, לכל קשת יש שני קצוות שונים: הראש (המסומן על ידי ראש החץ), והזנב (ממנו יוצאת הקשת). כל סוג של קצה נספר בנפרד - הראשים נספרים כדרגת הכניסה (אנגלית: indegree) ומספר הזנבות המקושרים לצומת מסוים מכונה דרגת יציאה (אנגלית: outdegree)

בגרף מכוון, דרגת הכניסה מסומנת כ־ $\,\deg^+(v)$ ודרגת היציאה כ־ $\,\deg^-(v)$ . דרגות הכניסה והיציאה של הצמתים בגרף משמאל מתוארות בטבלה הבאה:

צומת	דרגת כניסה	דרגת יציאה
1	0	2
2	2	0
3	2	2
4	1	1

[עריכה] ערכי דרגה מיוחדים

גרף בלתי מכוון בו הצמתים 4, 5, 6, 7, 10, 11, ו־12 הם עלים

אם לצומת יש דרגה 0, הוא נקרא צומת מבודד.
אם לצומת יש דרגה 1, הוא נקרא עלה. עלים נפוצים במיוחד בעצים.
אם לצומת $\,v$ מתקיים $\,\deg^+(v)=0$ , הצומת נקרא מקור. זאת מאחר והוא מהווה מקור לכל הקשתות היוצאות ממנו.
אם לצומת $\,v$ מתקיים $\,\deg^-(v)=0$ , הצומת נקרא בור.

[עריכה] הגדרה פורמלית

ניתן להגדיר פורמלית את דרגתו של צומת $\ v_i$ בגרף בלתי-מכוון $\ G=(V, E)$ כש־ $\ V$ הוא אוסף הצמתים ו־ $\ E$ הוא אוסף הקשתות, באופן הבא:

$\,\deg(v_i) = |\{v_j\}| : e_{ij} \in E$

כלומר, הגודל של קבוצת כל הצמתים $\ v_j$ שקיימת קשת בינם לבין $\ v_i$ .

באופן דומה ניתן להגדיר את דרגות הכניסה והיציאה בגרף מכוון:

$\,\deg^+(v_i) = |\{v_j\}| : e_{ji} \in E$

$\,\deg^-(v_i) = |\{v_j\}| : e_{ij} \in E$

נוסחת סכום הדרגות קובעת שסכום הדרגות של כל הצמתים בגרף שווה ל: $\sum_{v \in V} \deg(v) = 2|E|$ , זאת מאחר וכל לכל קשת יש שתי קצוות, וכך היא תורמת 2 לסכום הדרגות בגרף. מהנוסחה הזו משתמע שמספר הצמתים בעלי דרגה אי זוגית הוא זוגי, על מנת שהסכום הכולל יהיה זוגי.