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