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