גרף רגולרי – הבדלי גרסאות

תוכן שנמחק תוכן שנוסף
מ ניסוח, עיצוב
מ הגהה
שורה 1:
{{בעבודה|ללא קטגוריה=}}[[קובץ:2-regulární graf na 6 vrcholech.svg|ממוזער|200px|<center>גרף <math>2</math>-רגולרי</center>]]
ב[[תורת הגרפים]], '''גרף רגולרי''' (באנגלית: "''Regular graph''") הוא [[גרף (תורת הגרפים)|גרף]] שבו [[דרגה (תורת הגרפים)|דרגת]] כל הקודקודים שווה, כלומר מספר הקשתות היוצאות מכל [[קודקוד]], הוא קבוע. גרף מכוון רגולרי מקיים תנאים חזקים יותר ובו [[דרגה (תורת הגרפים)#גרפים מכוונים|דרגת הכניסה]] ודרגתו[[דרגה (תורת הגרפים)#גרפים מכוונים|דרגת היציאה]] של כל הקודקודים שוות<ref>{{Cite book|url=https://archive.org/details/graphtheoryitsen00chen/page/29|title=Graph Theory and its Engineering Applications|last=Chen|first=Wai-Kai|publisher=World Scientific|year=1997|isbn=978-981-02-1859-1|location=|pages=[https://archive.org/details/graphtheoryitsen00chen/page/29 29]}}</ref>. כלומר <math>d^+(i)=d^-(i)=k</math> לכל קודקוד <math>i</math>.
 
גרף רגולרי שבו דרגת כל הקודקודים היא <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>, לכל זוג של קודקודים שכנים אין אף שכן משותף ולכל זוג קודקודים לא שכנים יש שכן משותף בודד. כלומר, ניתן לסמן אותו על ידיכך: <math>srg(10,3,0,1)</math>.
 
<br />{{תורת הגרפים}}