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

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

==המשפט==
יהי <math>G=(V,E)</math> גרף.

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

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

תמיד <math>\tau(G)\le\nu(G)</math>, שכן כל שידוך תמיד קטן שווה מכל כיסוי (כי מכל קשת חייב להיות לפחות קודקוד אחד שישתתף בכיסוי). משפט קניג קובע שאם הגרף דו-צדדי, גם <math>\tau(G)=\nu(G)</math>.

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

==הוכחה==
יהי <math>T</math> כיסוי מינימלי בגרף הדו צדדי <math>(A\cup B, E)</math>. נמצא שידוך בגודל <math>|T|</math>. זה יוכיח <math>\tau(G)\ge\nu(G)</math>, וביחד עם <math>\tau(G)\le\nu(G)</math> כפי שהוזכר לעיל, ינבע <math>\tau(G)=\nu(G)</math>.

נסמן <math>A_1=A\cap T, A_2=A\setminus T,B_1=B\setminus T, B_2=B\cap T</math>. נסמן ב-<math>G_1</math> את תת-הגרף המושרה על <math>A_1\cup B_1</math>. אז נראה שיש זיווג שמרווה את A1 (כלומר כל קודקוד ב-A1 נוגע בקשת שמשתתפת בזיווג). נעשה זאת בעזרת משפט החתונה של הול.

תהי <math>x \subset A_1</math>. נטען ש <math>T':=B_2\uplus (A_1 \setminus x)\uplus N_1(x)</math> (כאשר <math>N_1(x)</math> הם השכנים של x ב-G1) הוא כיסוי של G. אכן, כל קשת ב-G נחתכת על T (כי הוא כיסוי) שהוא <math>A_1\cup B_2</math>, ולכן יש לה קצה או ב-<math>B_2</math>, או ב-<math>A_1\setminus x</math>, או ב-x ואז הקצה השני ב<math>N_1(x)</math>. כיוון ש-T הוא כיסוי מינימלי, <math>|T'|\ge|T|</math>. מצד שני, מתקיים <math>|T'|=|B_2|+|A_1|-|x|+|N_1(x)|</math> וכן <math>|T|=|A_1|+|B_2|</math>. מצירוף כל אלה מתקבל: <math>|N_1(x)|\ge |x|</math>

הראנו את תנאי הול על <math>G_1</math>. ממשפט החתונה של הול, יש בו זיווג המרווה את <math>A_1</math>. משיקולי סימטריה יש גם ב-<math>G_2</math> (הגרף המושרה על <math>A_1\cup B_1</math>) יש זיווג המרווה את <math>B_2</math>. כיוון שהם זרים, איחודם הוא זיווג המרווה את <math>A_1\cup B_2</math> ובפרט גודלו לפחות <math>|T|</math> כרצוי.

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

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

==קישורים חיצוניים==
[https://mathworld.wolfram.com/Koenig-EgevaryTheorem.html משפט קניג באתר mathworld]
* 

==הערות שוליים==

קטגוריה:משפטים בתורת הגרפים