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