גרף מרחיב

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש

במתמטיקה, גרף מרחיב (מכונה גם אקספנדר) הוא גרף "קשיר ביותר", במובן זה שכדי לפרק אותו לשני רכיבי קשירות גדולים יש להוציא ממנו מספר רב של צלעות. לגרפים מרחיבים שהדרגה שלהם קטנה יש שימושים רבים בקומבינטוריקה ובמדעי המחשב.

מכיוון שכל גרף סופי הוא מרחיב במידה מסוימת, עיקר העניין הוא בסדרות של גרפים שכולם מרחיבים במידה קבועה. למרות שמבחינה הסתברותית רוב הגרפים הם מרחיבים, לא קל לבנות משפחות כאלה במפורש.

הגדרה קומבינטורית[עריכת קוד מקור | עריכה]

גרף רגולרי  \ X=(V,E) בעל n קדקדים ודרגה k נקרא c-מרחיב אם לכל קבוצה של קדקדים  \ A\subset V מתקיים  \ |\partial A|\geq c\left ( 1-\frac{|A|}{n} \right ) |A| . כאשר מסמנים ב  \ \partial A את קבוצת הקדקדים שאינם ב A אבל מחוברים לקדקד ששייך ל A.

קל לראות שכל גרף קשיר הוא c-מרחיב עבור c>0 קטן מספיק. לכן מתייחס לפעמים השם "גרף מרחיב" למשפחה אינסופית של גרפים שכולם מרחיבים עם אותו קבוע c (ואותו k), ולא לגרף בודד.

הגדרה ספקטרלית[עריכת קוד מקור | עריכה]

בהינתן גרף רגולרי כאמור לעיל, מטריצת השכנות שלו היא מטריצה בגודל  \ n\times n כך שהתא במיקום  \ (i,j) מכיל את הערך 1 אם קודקוד i מחובר לקודקוד j, ואת הערך 0 אחרת. הערך העצמי המקסימלי של מטריצת שכנות של גרף k-רגולרי הוא תמיד k ואם הגרף דו צדדי, גם (-k) הוא ערך עצמי. ערכים עצמיים אלה נקראים טריביאלים. אומרים שהגרף הוא \alpha-מרחיב (במובן הספקטרלי) אם לכל ערך עצמי לא טריביאלי מתקיים  \ |\lambda |<k-\alpha .

הגדרה זו של גרפים מרחיבים שקולה להגדרה הקודמת, כלומר לכל k ולכל  \ \alpha >0 יש  \ c>0 כך שכל גרף שהוא \alpha-מרחיב לפי ההגדרה הספקטרלית, הוא גם c-מרחיב בהגדרה הקומבינטורית ולהפך.

קיום ובניה של גרפים מרחיבים[עריכת קוד מקור | עריכה]

על ידי שיקולי ספירה קל להראות שיש גרפים מרחיבים. ליתר דיוק, אם k>5 ואם מגרילים גרף מקרי k-רגולרי על n קדקדים, אז כאשר n שואף לאינסוף, ההסתברות שהגרף הוא \tfrac{1}{2}-מרחיב שואפת ל-1. בפרט, יש גרפים מרחיבים מכל סדר גדול מספיק.

בניה מפורשת של גרפים מרחיבים, לעומת זאת, איננה בעיה קלה. הבניה הראשונה ניתנה על ידי גריגורי מרגוליס בשנת 1975. הגרפים שנבנו היו גרפי קיילי של חבורות מטריצות מעל שדות סופיים. ההוכחה שגרפים אלה הם אכן מרחיבים משתמשת בתורת ההצגות (האינסוף ממדית!) של חבורות לי פשוטות.

בשנת 1988 אלכס לובוצקי ופיטר סרנק בנו דוגמה מפורשת לגרפי רמנוג'אן שהם אקספנדרים אופטימליים. הבנייה נעזרה בהוכחה של השערת רמנוג'אן על ידי פייר דלין בתורה של תבניות מודולריות, כתוצאה מהוכחת השערות ווייל.

כיום ידועות מספר שיטות לבניית גרפים מרחיבים. השיטות המודרניות נעזרות בתחום הקומבינטוריקה האריתמטית, ונסמכות על עבודות של הלפגוט, בורגיין-גמבורד-סרנק, בורגיין-ואריו ו-גרין-טאו-ברוליארד.

שימושים של גרפים מרחיבים[עריכת קוד מקור | עריכה]

לגרפים מרחיבים שימושים רבים במתמטיקה ובמדעי המחשב. להלן מבחר דוגמאות: