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