גרף רגולרי – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
מ ניסוח, עיצוב |
מ הגהה |
||
שורה 1:
{{בעבודה|ללא קטגוריה=}}[[קובץ:2-regulární graf na 6 vrcholech.svg|ממוזער|200px|<center>גרף <math>2</math>-רגולרי</center>]]
ב[[תורת הגרפים]], '''גרף רגולרי''' (באנגלית: "''Regular graph''") הוא [[גרף (תורת הגרפים)|גרף]] שבו [[דרגה (תורת הגרפים)|דרגת]] כל הקודקודים שווה, כלומר מספר הקשתות היוצאות מכל [[קודקוד]], הוא קבוע. גרף מכוון רגולרי מקיים תנאים חזקים יותר ובו [[דרגה (תורת הגרפים)#גרפים מכוונים|דרגת הכניסה]]
גרף רגולרי שבו דרגת כל הקודקודים היא <math>k</math> נקרא גרף <math>k</math>-רגולרי או גרף רגולרי מדרגה <math>k</math>.
שורה 11:
== גרף רגולרי-חזק ==
[[קובץ:Petersen1 tiny.svg|ממוזער|[[גרף פטרסן]] הוא דוגמה ל[[גרף רגולרי מדרגה 3]] {{אנ|Cubic graph}} - שהוא גם גרף רגולרי-חזק|טקסט=]]גרף רגולרי-חזק הוא גרף רגולרי שבו לכל זוג של קודקודים שכנים (כלומר, יש בין הקודקודים קשת) יש <math>\lambda</math> של שכנים משותפים, ולכל זוג קודקודים לא שכנים יש <math>\mu</math> שכנים משותפים.
גרף רגולרי-חזק לעיתים מסומן ב-<math>srg(v,k,\lambda,\mu)</math> (<math>v</math> מסמן את מספר הקודקודים בגרף, <math>k</math> מסמן את הדרגה המשותפת לכל הקודקודים). לדוגמה, [[גרף פטרסן]] {{אנ|Petersen graph}} הוא גרף רגולרי-חזק שבו <math>10</math> קודקודים, דרגת כל הצמתים היא <math>3</math>, לכל זוג של קודקודים שכנים אין אף שכן משותף ולכל זוג קודקודים לא שכנים יש שכן משותף בודד. כלומר, ניתן לסמן אותו <br />{{תורת הגרפים}}
|