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