גרף דו-צדדי

דוגמה לגרף דו-צדדי

בתורת הגרפים, גרף דו-צדדי (נקרא גם גרף דו-חלקי) הוא גרף שבו ניתן לחלק את הקודקודים לשתי קבוצות זרות, כך שלא קיימת קשת בין שני קודקודים השייכים לאותה הקבוצה.

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

גרפים דו-צדדיים מועילים במידול בעיות התאמה. למשל, אם יש לנו קבוצה $\ P$ של אנשים וקבוצה $\ J$ של עבודות ואנו רוצים לבצע חלוקת עבודה, נוכל בתור מודל לתאר את האנשים והעבודות כגרף דו-צדדי שקבוצת קודקודים אחת בו היא $\ P$ והשנייה $\ J$, ויש קשת בין אדם המתאים לעבודה מסוימת ועבודה זו.

תכונות

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

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

מדיה וקבצים בנושא גרף דו-צדדי בוויקישיתוף

• גרף דו-צדדי, באתר MathWorld (באנגלית)