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