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

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש
גרף לא מכוון בו מצוינות דרגות הקודקודים

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

גרף שדרגות כל הצמתים בו שוות ל־k נקרא גרף k־רגולרי, ונהוג לומר שדרגתו של הגרף היא k.

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

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

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

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

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

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

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

דרגת כניסה[עריכת קוד מקור | עריכה]

דרגת הכניסה (אנגלית: indegree) של צומת הינה סך הקשתות אשר הקצה שלהן המשויך לצומת הינו מסוג "ראש".

דרגת הכניסה מסומנת ב־ \,\deg^+(v) .

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

דרגת היציאה (אנגלית: outdegree) של צומת הינה סך הקשתות אשר הקצה שלהן המשויך לצומת הינו מסוג "זנב".

דרגת היציאה מסומנת ב - \,\deg^-(v) .

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

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

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

צומת 1 2 3 4
דרגת כניסה 0 2 2 1
דרגת יציאה 2 0 2 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 \qquad \,\deg^-(v_i) = |\{v_j\}| : e_{ij} \in E

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