דרגה (תורת הגרפים) – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
מ תבנית, עיצוב |
מ עיצוב |
||
שורה 2:
ב[[תורת הגרפים]], '''דרגה''' של [[צומת (תורת הגרפים)|צומת]] מתארת את מספר הקשתות המקושרות לצומת מסוים. זהו המידע הבסיסי ביותר שאפשר למסור על צומת ב[[גרף (תורת הגרפים)|גרף]], משום שהוא מתאר את תמונת העולם המקומית של הקודקודים שלו. דרגה של צומת <math>\,v</math> מסומנת כ־<math>\,\deg(v)</math>.
גרף שדרגות כל הצמתים בו שוות ל־k נקרא גרף k־[[גרף רגולרי|רגולרי]], ונהוג לומר
== גרפים בלתי-מכוונים ==
שורה 67:
ניתן להגדיר פורמלית את דרגתו של צומת <math> \ v_i</math> בגרף בלתי-מכוון <math>\ G=(V, E)</math> כש־<math>\ V</math> הוא אוסף הצמתים ו־<math>\ E</math> הוא אוסף הקשתות, באופן הבא:
<center><math>\,\deg(v_i) = |\{v_j\}| : e_{ij} \in E</math></center>
כלומר, הגודל של קבוצת כל הצמתים <math> \ v_j</math> שקיימת קשת בינם לבין <math> \ v_i</math>.
שורה 73:
באופן דומה ניתן להגדיר את דרגות הכניסה והיציאה בגרף מכוון:
<center><math>\,\deg^+(v_i) = |\{v_j\}| : e_{ji} \in E \qquad \,\deg^-(v_i) = |\{v_j\}| : e_{ij} \in E</math></center>
| |||