גרף דו-צדדי
בתורת הגרפים, גרף דו-צדדי (נקרא גם גרף דו-חלקי) הוא גרף שבו ניתן לחלק את הקודקודים לשתי קבוצות זרות, כך שלא קיימת קשת בין שני קודקודים השייכים לאותה הקבוצה.
גרף דו-צדדי מלא הוא גרף דו-צדדי, אשר מכיל את כל הקשתות האפשריות.
גרפים דו-צדדיים מועילים במידול בעיות התאמה. למשל, אם יש לנו קבוצה של אנשים וקבוצה של עבודות ואנו רוצים לבצע חלוקת עבודה, נוכל בתור מודל לתאר את האנשים והעבודות כגרף דו-צדדי שקבוצת קודקודים אחת בו היא והשנייה , ויש קשת בין אדם המתאים לעבודה מסוימת ועבודה זו.
תכונות
- גרף הוא דו-צדדי אם ורק אם אין בו מעגל באורך אי-זוגי.
- גרף הוא דו-צדדי אם ורק אם הוא 2-צביע.
- משפט החתונה מספק אפיון של גרפים דו-צדדיים שבהם ניתן לבחור קבוצה של קשתות לא נוגעות שמכסות את כל צומתי הגרף.
- כל עץ הוא גרף דו-צדדי.
קישורים חיצוניים
- גרף דו-צדדי, באתר MathWorld (באנגלית)
| נושאים בתורת הגרפים | ||
|---|---|---|
| הגדרות | צומת • קשת • דרגה • מסלול • מרחק | |
| מבנים | גרף • גרף ממושקל • מעגל • גרף מקרי • היפרגרף • מולטיגרף • עץ • קומפלקס | |
| בניות וטיפוסים | גרף משלים • גרף קיילי • גרף שלם • גרף תחרות • עץ פורש • רשת זרימה • שידוך | |
| תכונות | גרף n-צביע • גרף דו-צדדי • גרף מישורי • גרף מרחיב • גרף רגולרי • גרף קשיר • עץ בינומי • עץ פורש מינימלי | |
גרף דו-צדדי25967821Q174733