מבני נתונים ואלגוריתמים - מחברת קורס/גרפים/אלגוריתמי זרימה/תרגילים/יריד תעסוקה 1/שאלה

ליריד התעסוקה של האוניברסיטה הגיעו $\displaystyle m$ סטודנטים, $\displaystyle 1,\ldots m$, ו$\displaystyle n$ חברות, $\displaystyle 1,\ldots n$. נניח שכל סטודנט מוכן לעבוד בחברה אחת או יותר, וכל חברה מוכנה להעסיק סטודנט אחד או יותר, אך כל סטודנט יכול לעבוד בחברה אחת לכל היותר, וכל חברה יכולה להעסיק סטודנט אחד לכל היותר.

נתון מערך רצון התעסוקה W, שבו $\displaystyle r$ זוגות. אם הזוג (i, j) מופיע בW, אז המשמעות היא שסטודנט $\displaystyle i$ מוכן לעבוד בחברה $\displaystyle j$, וחברה $\displaystyle j$ מוכנה להעסיק את סטודנט $\displaystyle i$.

רוצים למצוא את השמת הסטודנטים לחברות כך שמספר רב ככל האפשר של סטודנטים יעבדו. אנא הסבר כיצד לכתוב אלגוריתם יעיל המקבל את המערך $\displaystyle W$, ומוציא מערך גדול ככל האפשר W', כך שיתקיימו התנאים הבאים:

1. אם הזוג (i, j) מופיע בW', אז הוא גם מופיע בW.
2. אם הזוג (i, j) מופיע בW', אז אין זוג אחר בW' שאברו הראשון $\displaystyle i$.
3. אם הזוג (i, j) מופיע בW', אז אין זוג אחר בW' שאברו השני $\displaystyle j$.

רמז בנה גרף שבו יש צומת לכל סטודנט, צומת לכל חברה, צומת $\displaystyle s$, וצומת $\displaystyle t$. חשוב מהן קשתות הגרף. חשוב איזו בעיית זרימה תפתור את הבעיה כאן.