שידוך (תורת הגרפים) – הבדלי גרסאות

בעיית מציאת מספר השידוכים המושלמים ב[[גרף דו-צדדי]] היא שלמה ל-{{משמאל לימין|[[Sharp-P|#P]]}}, בעוד שבעיית ההכרעה המקבילה לה - השאלה האם בגרף דו-צדדי קיים שידוך מושלם - ניתנת לפתרון יעיל, כלומר ידוע שהיא שייכת ל-[[P (סיבוכיות)|P]].

==הערות שוליים==

 

[[קטגוריה:תורת הגרפים]]