דרגה של צומת היא מספר הקשתות המקושרות אליו. סימון מקובל הוא \deg(v). זו דרך פשוטה לתאר את "הסביבה" המקומית של צומת בגרף.
גרף שדרגות כל הצמתים בו שוות ל-k נקרא גרף k-רגולרי. נהוג לומר שדרגתו של הגרף היא k.
בגרף בלתי מכוון, דרגת צומת היא מספר הקשתות היוצאות ממנו או הנכנסות אליו, כי בקשת אין כיוון. לולאה (קשת שמתחברת לצומת עצמו) נספרת פעמיים, כי היא נוגעת בצומת בשני קצוות. לכן צומת עם לולאה מקבל דרגה 2 מהלולאה בלבד.
בגרף מכוון לכל קשת יש כיוון: ראש (המקום שאליו האדג') וזנב (המקום ממנו היא יוצאת). לעניין הדרגות סופרים כל סוג קצה בנפרד.
דרגת הכניסה (indegree, כלומר כמה קשתות נכנסות לצומת) מסומנת ב־\deg^+(v).
דרגת היציאה (outdegree, כלומר כמה קשתות יוצאות מהצומת) מסומנת ב־\deg^-(v).
לעיתים מציגים טבלה שמראה את דרגות הכניסה והיציאה של הצמתים בגרף נתון. טבלה כזו מסכמת מי מחובר למי וכמה קשתות נכנסות ויוצאות מכל צומת.
ניתן להגדיר את דרגתו של צומת v_i בגרף בלתי-מכוון פשוט כגודל הקבוצה של הצמתים v_j שעימם קיים קשת (v_i,v_j) ב־E. כלומר דרגה היא מספר הצמתים שאליהם יש קשת מהצומת המדובר.
נוסחת סכום הדרגות אומרת שסכום דרגות כל הצמתים שווה ל־2|E|, כי כל קשת תורמת שתי נגיעות בצמתים. מכאן נובע שא תמיד יש מספר זוגי של צמתים בעלי דרגה אי-זוגית (מסקנה שמוכרכת כ"למת לחיצות הידיים").
סדרת הדרגות של גרף בלתי-מכוון עם n צמתים היא סדרה בסדר יורד של הדרגות של הצמתים. לגרפים איזומורפיים יש את אותה סדרת דרגות. ההפך אינו נכון תמיד: שני גרפים יכולים לחלוק את אותה סדרת דרגות אך לא להיות איזומורפיים.
סדרה שניתן לקבל כ"סדרת דרגות" של גרף נקראת גרפית. קיימת תאוריה שמאפשרת לבדוק בזמן פולינומי אם סדרה נתונה היא גרפית, ולבנות גרף מתאים כאשר זה אפשרי.
דרגה של צומת היא כמה קשתות נוגעות בו. כותבים את זה \deg(v).
גרף שבו לכל הצמתים יש אותה דרגה קוראים לו k-רגולרי.
בגרף בלי כיוונים נספר כמה קשתות נוגעות בצומת. לולאה היא קשת שמחוברת לצומת עצמו. לולאה נספרת פעמיים.
בגרף עם כיוונים לכל קשת יש "ראש" ו"זנב". לכן מחשבים שני סוגי דרגות.
דרגת הכניסה היא כמה קשתות נכנסות לצומת. מסומנת \deg^+(v).
דרגת היציאה היא כמה קשתות יוצאות מהצומת. מסומנת \deg^-(v).
אפשר להציג טבלה שמראה לכל צומת כמה קשתות נכנסות וכמה יוצאות.
אם נסכום את דרגות כל הצמתים נקבל פעמיים את מספר הקשתות. מכאן יש תמיד מספר זוגי של צמתים בדרגות אי-זוגיות.
סדרת דרגות היא רשימה של כל הדרגות מהגדול לקטן. אם אפשר לבנות גרף מרשימה כזו קוראים לה גרפית.
תגובות גולשים