משפט קניג (תורת הגרפים)

משפט קניג הוא משפט בתורת הגרפים, העוסק בכיסוי מינימלי ובשידוך מקסימלי. הוא קובע שבגרף דו צדדי הם שווים. המשפט התגלה על ידי דנש קניג ונקרא על שמו.

דוגמה למשפט קניג. כיסוי מינימלי באדום, שידוך מקסימלי בכחול

המשפט

יהי ${\displaystyle G=(V,E)}$ גרף.

כיסוי קודקודים היא קבוצת קודקודים ${\displaystyle T\subset V}$ המקיימת שלכל קשת ${\displaystyle e\in E}$ יש קודקוד ${\displaystyle v\in T}$ כך ש-${\displaystyle v\in e}$. כיסוי מינימלי הוא כיסוי שאין כיסוי עם פחות קודקודים ממנו. מסמנים ${\displaystyle \tau (G)}$ להיות גודל הכיסוי המקסימלי.

שידוך הוא קבוצת קשתות ${\displaystyle M\subset E}$ המקיימת שלכל קודקוד ${\displaystyle v\in V}$ יש לכל היותר קשת אחת ${\displaystyle e\in M}$ כך ש-${\displaystyle v\in e}$. שידוך מקסימלי הוא שידוך שאין שידוך עם יותר קשתות ממנו. מסמנים ${\displaystyle \nu (G)}$ להיות גודל השידוך המקסימלי.

תמיד ${\displaystyle \tau (G)\leq \nu (G)}$, שכן כל שידוך תמיד קטן שווה מכל כיסוי (כי מכל קשת חייב להיות לפחות קודקוד אחד שישתתף בכיסוי). משפט קניג קובע שאם הגרף דו-צדדי, גם ${\displaystyle \tau (G)=\nu (G)}$.

נשים לב שמציאת שידוך מקסימלי ניתנת לפתרון פולינומי, בעוד שבעיית כיסוי הקודקודים היא NP קשה. לכן, משפט קניג מוכיח שעבור גרף דו צדדי הבעיה איננה NP קשה.

הוכחה

יהי ${\displaystyle T}$ כיסוי מינימלי בגרף הדו צדדי ${\displaystyle (A\cup B,E)}$. נמצא שידוך בגודל ${\displaystyle |T|}$. זה יוכיח ${\displaystyle \tau (G)\geq \nu (G)}$, וביחד עם ${\displaystyle \tau (G)\leq \nu (G)}$ כפי שהוזכר לעיל, ינבע ${\displaystyle \tau (G)=\nu (G)}$.

נסמן ${\displaystyle A_{1}=A\cap T,A_{2}=A\setminus T,B_{1}=B\setminus T,B_{2}=B\cap T}$. נסמן ב-${\displaystyle G_{1}}$ את תת-הגרף המושרה על ${\displaystyle A_{1}\cup B_{1}}$. אז נראה שיש זיווג שמרווה את A1 (כלומר כל קודקוד ב-A1 נוגע בקשת שמשתתפת בזיווג). נעשה זאת בעזרת משפט החתונה של הול.

תהי ${\displaystyle x\subset A_{1}}$. נטען ש ${\displaystyle T':=B_{2}\uplus (A_{1}\setminus x)\uplus N_{1}(x)}$ (כאשר ${\displaystyle N_{1}(x)}$ הם השכנים של x ב-G1) הוא כיסוי של G. אכן, כל קשת ב-G נחתכת על T (כי הוא כיסוי) שהוא ${\displaystyle A_{1}\cup B_{2}}$, ולכן יש לה קצה או ב-${\displaystyle B_{2}}$, או ב-${\displaystyle A_{1}\setminus x}$, או ב-x ואז הקצה השני ב${\displaystyle N_{1}(x)}$. כיוון ש-T הוא כיסוי מינימלי, ${\displaystyle |T'|\geq |T|}$. מצד שני, מתקיים ${\displaystyle |T'|=|B_{2}|+|A_{1}|-|x|+|N_{1}(x)|}$ וכן ${\displaystyle |T|=|A_{1}|+|B_{2}|}$. מצירוף כל אלה מתקבל: ${\displaystyle |N_{1}(x)|\geq |x|}$

הראנו את תנאי הול על ${\displaystyle G_{1}}$. ממשפט החתונה של הול, יש בו זיווג המרווה את ${\displaystyle A_{1}}$. משיקולי סימטריה יש גם ב-${\displaystyle G_{2}}$ (הגרף המושרה על ${\displaystyle A_{1}\cup B_{1}}$) יש זיווג המרווה את ${\displaystyle B_{2}}$. כיוון שהם זרים, איחודם הוא זיווג המרווה את ${\displaystyle A_{1}\cup B_{2}}$ ובפרט גודלו לפחות ${\displaystyle |T|}$ כרצוי.

הכללות

ניתן להכליל את המשפט למקרים בהם הגרף ממושקל:

• קשתות ממושקלות: נניח שלכל קשת משקל אי שלילי. משקל של שידוך הוא סכום משקלי הקשתות. כיסוי ממושקל הוא פונקציה מהקודקודים למספרים אי שליליים, כך שסכום הקודקודים בקצות כל קשת הוא לפחות משקל הקשת. משקל של כיסוי כזה הוא סכום המשקלים. אז בגרף דו צדדי, משקל הכיסוי המינימלי שווה למשקל השידוך המקסימלי.
• קודקודים ממושקלים: נניח שלכל קודקוד משקל אי שלילי. משקל של כיסוי הוא סכום משקלי הקודקודים. שידוך ממושקל הוא פונקציה מהקשתות למספרים אי שליליים, כך שסכום הקשתות שיוצאות מקודקוד הוא לכל היותר משקל הקודקוד. משקל של שידוך כזה הוא סכום המשקלים. אז בגרף דו צדדי, משקל הכיסוי הקסימליי שווה למשקל השידוך המינימלי.

שני המשפטים נובעים ממשפט הדואליות החזק^[1].

קישורים חיצוניים

משפט קניג באתר mathworld

• משפט קניג, באתר MathWorld (באנגלית)

הערות שוליים