גרף רגולרי
פעולות נוספות
בתורת הגרפים, גרף רגולרי (באנגלית: Regular graph) הוא גרף שבו דרגת כל הקודקודים שווה, כלומר מספר הקשתות היוצאות מכל קודקוד קבוע. גרף מכוון רגולרי מקיים תנאים חזקים יותר ובו דרגת הכניסה ודרגת היציאה של כל הקודקודים שוות.[1] כלומר <math>d^+(i)=d^-(i)=k</math> לכל קודקוד <math>i</math>.
גרף רגולרי שבו דרגת כל הקודקודים היא <math>k</math> נקרא גרף <math>k</math>-רגולרי או גרף רגולרי מדרגה <math>k</math>.
לדוגמה, <math>K_n</math> (גרף שלם בעל <math>n</math> קודקודים) הוא גרף <math>(n-1)</math>-רגולרי.
אם <math>k</math> אי-זוגי, נובע מלמת לחיצות הידיים שבגרף <math>k</math>-רגולרי יהיו מספר זוגי של קודקודים.
הייחודיות של הגרפים הרגולריים טמונה בעובדה שסדרת הדרגות שלהם קבועה.
תכונות אלגבריות עריכה
נסמן ב-<math>A</math> את מטריצת הסמיכויות של הגרף <math>G</math>. <math>G</math> הוא גרף <math>k</math>-רגולרי אם ורק אם <math>\textbf{j}=(1, \dots ,1)</math> הוא וקטור עצמי של <math>A</math> ששייך לערך העצמי <math>k</math>.[2]
יהיו <math>\lambda_0 >\lambda_1\geq \cdots\geq\lambda_{n-1}</math> הערכים העצמיים של <math>A</math>, <math>G</math> גרף <math>k</math>-רגולרי אם ורק אם מתקיים <math>k=\lambda_0</math> ו-<math>\sum_{i=0}^{n-1}\lambda_i^2=n\lambda_0</math> (כאשר <math>n</math> הוא מספר הצמתים ב-<math>G</math>).[2]
גרף רגולרי הוא קשיר אם ורק אם לערך העצמי <math>k=\lambda_0</math> יש ריבוי אלגברי 1.[3] הטענה ניתנת להכללה: מספר הרכיבים הקשירים של הגרף שווה לריבוי האלגברי של הערך העצמי <math>k=\lambda_0</math>.[2]
גרף רגולרי-חזק עריכה
גרף רגולרי-חזק הוא גרף רגולרי שבו לכל זוג של קודקודים שכנים (כלומר, יש בין הקודקודים קשת) יש <math>\lambda</math> שכנים משותפים, ולכל זוג קודקודים לא שכנים יש <math>\mu</math> שכנים משותפים.
גרף רגולרי-חזק לעיתים מסומן ב-<math>srg(v,k,\lambda,\mu)</math> (<math>v</math> מסמן את מספר הקודקודים בגרף, <math>k</math> מסמן את הדרגה המשותפת לכל הקודקודים).
לדוגמה, גרף פטרסן (אנ') הוא גרף רגולרי-חזק שבו <math>10</math> קודקודים, דרגת כל הצמתים היא <math>3</math>, לכל זוג של קודקודים שכנים אין אף שכן משותף ולכל זוג קודקודים לא שכנים יש שכן משותף בודד. כלומר, ניתן לסמן אותו כך: <math>srg(10,3,0,1)</math>.
קישורים חיצוניים עריכה
- גרף רגולרי, באתר MathWorld (באנגלית)
- גרף רגולרי-חזק, באתר MathWorld (באנגלית)
הערות שוליים עריכה
- ^ שגיאת לואה ביחידה יחידה:Citation/CS1/Configuration בשורה 1739<includeonly></includeonly>: attempt to index field '?' (a nil value).
- ^ 1 2 3 Stanic, Zoran, 2, Regular Graphs : A Spectral Approach, Berlin/Boston, GERMANY, 2017, עמ' 15-16, ISBN 978-3-11-035128-6
- ^ צד אחד של ההוכחה נובע ממשפט פרון-פרובניוס.
| נושאים בתורת הגרפים | ||
|---|---|---|
| הגדרות | צומת • קשת • דרגה • מסלול • מרחק | |
| מבנים | גרף • גרף ממושקל • מעגל • גרף מקרי • היפרגרף • מולטיגרף • עץ • קומפלקס | |
| בניות וטיפוסים | גרף משלים • גרף קיילי • גרף שלם • גרף תחרות • עץ פורש • רשת זרימה • שידוך | |
| תכונות | גרף n-צביע • גרף דו-צדדי • גרף מישורי • גרף מרחיב • גרף רגולרי • גרף קשיר • עץ בינומי • עץ פורש מינימלי | |