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