גרף מרחיב

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