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

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

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

גרף שדרגות כל הצמתים בו שוות ל-${\displaystyle k}$ נקרא גרף ${\displaystyle k}$-רגולרי, ונהוג לומר שדרגתו של הגרף היא ${\displaystyle k}$.

בגרף בלתי מכוון, הדרגה של צומת היא מספר הקשתות היוצאות ממנו. במקרה כזה, לולאה נספרת כשתי קשתות, כפי שרואה אותה מעגל קטן סביב הצומת. מכאן נובע, כי דרגת צומת אשר בו קיימת לולאה הנה ${\displaystyle 2}$.

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

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

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

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

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

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

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

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

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

$${\displaystyle \,\deg(v_{i})=\left|\left\{v_{j}\in V:(v_{i},v_{j})\in E\right\}\right|}$$

כלומר, הגודל של קבוצת כל הצמתים ${\displaystyle v_{j}}$ שקיימת קשת בינם לבין ${\displaystyle \ v_{i}}$.

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

${\displaystyle \,\deg ^{+}(v_{i})=\left|\left\{v_{j}\in V:(v_{j},v_{i})\in E\right\}\right|\qquad \,\deg ^{-}(v_{i})=\left|\left\{v_{j}\in V:(v_{i},v_{j})\in E\right\}\right|}$

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

סדרת הדרגות של גרף לא מכוון עם ${\displaystyle n}$ צמתים היא סדרה לא עולה של דרגות הצמתים של הגרף.

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

סדרה נקראת גרפית אם קיים גרף שהיא סדרת הדרגות שלו. בעיית סדרת הדרגות היא למצוא גרף (או את כל הגרפים) שסדרת הדרגות שלו שווה לסדרה נתונה כלשהי. קיים אפיון של הסדרות הגרפיות (אנ')^[1] המוביל לאלגוריתם החלטה בזמן פולינומי האם סדרה נתונה היא גרפית והגרף הוא גרף פשוט (אם הגרף יכול להכיל לולאות וקשתות מקבילות ניתן לבנות גרף שכזה לכל סדרה לא יורדת שסכומה זוגי, ולא ניתן לבנות גרף שכזה לכל סדרה שסכומה אי-זוגי (נובע ישירות מלמת לחיצות הידיים)).

• דרגה, באתר MathWorld (באנגלית)