הצגת המקור של הדף "גרף דו-צדדי"

[[קובץ:Simple-bipartite-graph.svg|שמאל|ממוזער|250px|דוגמה לגרף דו-צדדי]]
ב[[תורת הגרפים]], '''גרף דו-צדדי''' (נקרא גם '''גרף דו-חלקי''') הוא [[גרף (תורת הגרפים)|גרף]] שבו ניתן לחלק את הקודקודים לשתי [[קבוצות זרות]], כך שלא קיימת קשת בין שני קודקודים השייכים לאותה הקבוצה.

'''גרף דו-צדדי מלא''' הוא גרף דו-צדדי, אשר מכיל את כל הקשתות האפשריות. גרף כזה מסומן <math>K_{m,n}</math> (אם יש לו n קודקודים בצד אחד ו-m בשני) ויש לו mn קשתות.

גרפים דו-צדדיים מועילים במידול בעיות התאמה. למשל, אם יש לנו קבוצה <math>\ P</math> של אנשים וקבוצה <math>\ J</math> של עבודות ואנו רוצים לבצע [[חלוקת העבודה|חלוקת עבודה]], נוכל בתור מודל לתאר את האנשים והעבודות כגרף דו-צדדי שקבוצת קודקודים אחת בו היא <math>\ P</math> והשנייה <math>\ J</math>, ויש קשת בין אדם המתאים לעבודה מסוימת ועבודה זו.

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

==קישורים חיצוניים==
{{ויקישיתוף בשורה}}
* {{MathWorld}}

{{תורת הגרפים}}

[[קטגוריה:תורת הגרפים]]