דרגה (תורת הגרפים) – הבדלי גרסאות

{{פירוש נוסף|נוכחי=דרגה בהקשר של [[תורת הגרפים]]|ראו=[[דרגה (פירושונים)]]}}

ב[[תורת הגרפים]], '''דרגה''' של [[צומת (תורת הגרפים)|צומת]] מתארת את מספר הקשתות המקושרות לצומת מסוים. זהו המידע הבסיסי ביותר שאפשר למסור על צומת ב[[גרף (תורת הגרפים)|גרף]], משום שהוא מתאר את תמונת העולם המקומית של הקודקודים שלו. דרגה של צומת <math>\,v</math> מסומנת כ־<math>\,\deg(v)</math>.

 

== גרפים בלתי-מכוונים ==

[[קובץ:6n-graf.svg|ממוזער|שמאל|150px|גרף בלתי-מכוון בעל 6 צמתים ו־7 קשתות]]

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

 

===דוגמה===

[[קובץ:Directed graph.svg|ממוזער|שמאל|150px|גרף מכוון בעל 4 צמתים ו־5 קשתות]]

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

 

== ערכי דרגה מיוחדים ==

[[קובץ:Depth-first-tree.png|ממוזער|שמאל|גרף בלתי מכוון בו הצמתים 4, 5, 6, 7, 10, 11, ו־12 הם עלים]]

* אם לצומת יש דרגה 0, הוא נקרא '''צומת מבודד'''.

* אם לצומת יש דרגה 1, הוא נקרא '''עלה'''. בכל [[עץ (תורת הגרפים)|עץ]] לא טריוויאלי יש לפחות שני עלים.