שאלה 4 במסלול אלגוריתמים. בסעיף א בודקים תכונות יסוד (קשירות, דו-צדדיות, שלמות, עציות) של גרף לא מכוון מסוג כוכב. בסעיף ב, שאין לו קשר לסעיף א, מנתחים גרף מכוון של מעברים בין שכונות: משרטטים מטריצת סמיכויות, בודקים קשירות חזקה, ומתארים ומריצים אלגוריתם חיפוש מסלול בין שתי שכונות.
שאלה 4 במסלול אלגוריתמים. בסעיף א בודקים תכונות יסוד (קשירות, דו-צדדיות, שלמות, עציות) של גרף לא מכוון מסוג כוכב. בסעיף ב, שאין לו קשר לסעיף א, מנתחים גרף מכוון של מעברים בין שכונות: משרטטים מטריצת סמיכויות, בודקים קשירות חזקה, ומתארים ומריצים אלגוריתם חיפוש מסלול בין שתי שכונות.
גרף לא מכוון G=(V,E): a במרכז, מחובר ל-b,c,d,e (star graph)
b-a, a-d, a-c, a-e (star, a center)
גרף מכוון (מהנדס העיר) על a,b,c,d,e,f: b->d, a->b, d->a (curved), a->c, c->f, a->e, e->a (curved), f->a (curved via loop from f up to a)
directed edges: b->d, a->b, a->d(curved back a<->d two arcs), a->c, c->a? , a->e, e->a, f->a, c->f? see fidelity_notes
לגרף G=(V,E) שאינו מכוון: (על סמך התרשים - a מחובר ל-b,c,d,e בלבד, ללא צלעות נוספות) i. האם הגרף קשיר? נמקו. ii. האם הגרף דו-צדדי? נמקו. iii. האם הגרף מלא (שלם)? נמקו. iv. האם הגרף הוא עץ? נמקו.
מהנדס העיר הגדיר את המעבר בין השכנות a,b,c,d,e,f על פי הגרף שלהלן (גרף מכוון): i. שרטטו מטריצת סמיכויות. ii. האם הגרף הוא גרף קשיר חזק? נמקו. iii. תושב העיר צריך להגיע מהעיר צריך להגיע לשכונה אחת לשכונה אחרת. לשם כך עליו לבדוק אם קיים מסלול בין שתי השכונות ואם קיים, הוא רוצה למצוא כלשהו מסלול כלשהו המגיע לאותה שכונה. מהו האלגוריתם עליו להשתמש למטרות אלה? הסבירו. iv. הפעילו את האלגוריתם שכתבתם עליו בסעיף הקודם כדי למצוא את המסלול משכונה b לשכונה c. כתבו את המסלול שמצאתם. יש לבצע מעקב מפורט בכל שלב בהתאם לאלגוריתם שהפעלתם.
שאלות ותגובות על השאלה
🎓 לא הבנתם משהו? קבלו הסבר נוסף ממרצה לתכנות
שאלו כאן — ותקבלו מענה מוסמך.