גרף מרחיב
מתוך ויקיפדיה, האנציקלופדיה החופשית
במתמטיקה, גרף מרחיב הוא גרף (לרוב עם מעט צלעות) שהוא "מאוד קשיר" במובן זה שאי אפשר להוציא מעט צלעות ולפרק את הגרף לשני מרכיבי קשירות גדולים. לגרפים מרחיבים שימושים רבים במתמטיקה ובמדעי המחשב. למרות שניתן בקלות להראות שגרפים מרחיבים קיימים (ולמעשה אפילו רוב הגרפים הם מרחיבים), בניות מפורשות של גרפים מרחיבים אינן קלות. הבניה המפורשת הראשונה של גרפים מרחיבים נעשתה על ידי גריגורי מרגוליס.
תוכן עניינים |
[עריכה] הגדרה קומבינטורית
גרף רגולרי
בעל n קדקדים ודרגה k נקרא (n,k,c) מרחיב אם לכל קבוצה של קדקדים
מתקיים
. כאשר מסמנים ב
את קבוצת הקדקדים שאינם ב A אבל מחוברים לקדקד ששייך ל A.
קל לראות שלכל גרף קשיר יש c>0 כך שהגרף הוא (n,k,c) מרחיב. העניין בגרפים מרחיבים הוא מציאת משפחה אינסופית של גרפים שכולם מרחיבים עם אותו קבוע c (ולרוב, אותו k).
[עריכה] הגדרה ספקטרלית
בהנתן גרף רגולרי כמו קודם, מטריצת השכנות שלו היא מטריצה בגודל
כך שבמקום
יש 1 אם קדקד i מחובר לקדקד j ו 0 אחרת. למטריצת שכנות של גרף k רגולרי תמיד יש ערך עצמי k ואם הגרף דו צדדי, יש לה גם ערך עצמי -k. ערכים עצמיים אלה נקראים טריביאלים. אומרים שהגרף הוא
מרחיב (במובן הספקטרלי) אם לכל ערך עצמי לא טריביאלי מתקיים
.
הגדרה זו של גרפים מרחיבים שקולה להגדרה הקודמת, כלומר לכל k ולכל
יש
כך שכל גרף שהוא
מרחיב לפי ההגדרה הספקטרלית, הוא גם
מרחיב בהגדרה הקומבינטורית ולהפך.
[עריכה] קיום ובניה של גרפים מרחיבים
על ידי שיקולי ספירה קל להראות שיש גרפים מרחיבים. ליתר דיוק, אם k>5 ואם מגרילים גרף מקרי k רגולרי על n קדקדים, אז כאשר n שואף לאינסוף, ההסתברות שהגרף הוא
מרחיב שואפת ל 1. בפרט, יש גרפים מרחיבים מכל סדר גדול מספיק.
בניה מפורשת של גרפים מרחיבים, לעומת זאת, איננה בעיה קלה. הבניה הראשונה ניתנה על ידי גריגורי מרגוליס בשנת 1975. הגרפים שנבנו היו גרפי קיילי של חבורות מטריצות מעל שדות סופיים. ההוכחה שגרפים אלה הם אכן מרחיבים משתמשת בתורת ההצגות (האינסוף ממדית!) של חבורות לי פשוטות.
[עריכה] שימושים של גרפים מרחיבים
לגרפים מרחיבים שימושים רבים במתמטיקה ובמדעי המחשב. להלן מבחר דוגמאות:
- בניה של מרחבים מטריים סופיים שקשה לשכן במרחבים אוקלידיים.
- בנית קודים לתיקון שגיאות.
- אלגוריתמי דהרנדומיזציה רבים משתמשים בגרפים מרחיבים.
- בניות של פונקציות ערבול בקריפטוגרפיה.
- הוכחת משפט ה-PCP משתמשת בגרפים מרחיבים.

