בשאלה זו שני סעיפים, א–ב, שאין ביניהם קשר. יש לענות על שני הסעיפים.
סעיף א. נתון גרף G = (V,E) מכוון, המיוצג על ידי רשימת הסמיכויות הבאה:
a → d → c → b
b → d → c
c → d → a
d
סעיף ב. גרף דו-צדדי הוא גרף בו ניתן לחלק את הצמתים שבו לשתי קבוצות זרות, כך שלא קיימת קשת בין שני צמתים השייכים לאותה הקבוצה.
הגרפים הדו-צדדיים G1 ו-G2 (קשתות לא מכוונות):
G1: A-B, A-C, B-D, C-E, C-F
G2: A-B, A-C, A-E, C-F, E-F
הגרף G3, שאינו דו-צדדי (7 צמתים A–G, קשתות לא מכוונות):
G3: A-B, A-E, B-C, B-G, C-E, D-E, D-F, D-G, E-F, G-F
שרטטו את הגרף G המיוצג ע"י רשימת הסמיכויות.
הפעילו אלגוריתם סריקה לעומק (DFS) על הגרף G החל בצומת a. שרטטו את העץ הפורש DFS.
הפעילו אלגוריתם סריקה לרוחב (BFS) על הגרף G החל בצומת c. שרטטו את העץ הפורש BFS.
גרף דו-צדדי הוא גרף בו ניתן לחלק את הצמתים שבו לשתי קבוצות זרות, כך שלא קיימת קשת בין שני צמתים השייכים לאותה הקבוצה. לפניכם 2 גרפים דו-צדדיים. הראו את שתי קבוצות הצמתים עבור כל גרף.
לפניכם גרף שאינו דו-צדדי. מהו מספר הקשתות המינימלי שיש להסיר כדי שהגרף יהיה דו-צדדי? כתבו אילו קשתות יש להסיר והציגו את שתי הקבוצות.
שאלות ותגובות על השאלה
🎓 לא הבנתם משהו? קבלו הסבר נוסף ממרצה לתכנות
שאלו כאן — ותקבלו מענה מוסמך.