גרף דו-צדדי

מתוך המכלול, האנציקלופדיה היהודית
קפיצה לניווט קפיצה לחיפוש
שגיאה ביצירת תמונה ממוזערת:
דוגמה לגרף דו-צדדי

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

גרף דו-צדדי מלא הוא גרף דו-צדדי, אשר מכיל את כל הקשתות האפשריות.

גרפים דו-צדדיים מועילים במידול בעיות התאמה. למשל, אם יש לנו קבוצה הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \ P} של אנשים וקבוצה של עבודות ואנו רוצים לבצע חלוקת עבודה, נוכל בתור מודל לתאר את האנשים והעבודות כגרף דו-צדדי שקבוצת קודקודים אחת בו היא הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \ P} והשנייה , ויש קשת בין אדם המתאים לעבודה מסוימת ועבודה זו.

תכונות

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

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

ויקישיתוף ראו מדיה וקבצים בנושא זה בוויקישיתוף.

  • גרף דו-צדדי, באתר MathWorld (באנגלית)   המזהה לא מולא ולא נמצא בוויקינתונים, נא למלא את הפרמטר.


סמל המכלול גמרא 2.PNG
הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0