בשאלה זו שני סעיפים, א–ב, שאין ביניהם קשר. יש לענות על שני הסעיפים.
בשאלה זו שני סעיפים, א–ב, שאין ביניהם קשר. יש לענות על שני הסעיפים.
סעיף א. להלן גרף G=(V,E) שאינו מכוון: הצומת a מחובר בקשת לכל אחד מהצמתים b, c, d, e, ואין בגרף קשתות נוספות.
סעיף ב. מהנדס העיר הגדיר את המעבר בין השכונות a,b,c,d,e,f על פי הגרף המכוון שלהלן, שקשתותיו:
a→b, a→d, a→e, a→f, b→d, c→a, d→a, e→a, f→c
לגרף G=(V,E) שאינו מכוון, שבתחילת השאלה: i. האם הגרף קשיר? נמקו. ii. האם הגרף דו-צדדי? נמקו. iii. האם הגרף מלא (שלם)? נמקו. iv. האם הגרף הוא עץ? נמקו.
מהנדס העיר הגדיר את המעבר בין השכונות a,b,c,d,e,f על פי הגרף המכוון שבתחילת השאלה. i. שרטטו מטריצת סמיכויות. ii. האם הגרף הוא גרף קשיר חזק? נמקו. iii. תושב העיר צריך להגיע משכונה אחת לשכונה אחרת. לשם כך עליו לבדוק אם קיים מסלול בין שתי השכונות ואם קיים, הוא רוצה למצוא מסלול כלשהו המגיע לאותה שכונה. מהו האלגוריתם שעליו להשתמש בו למטרות אלה? הסבירו. iv. הפעילו את האלגוריתם שכתבתם עליו בסעיף הקודם כדי למצוא את המסלול משכונה b לשכונה c. כתבו את המסלול שמצאתם. יש לבצע מעקב מפורט בכל שלב בהתאם לאלגוריתם שהפעלתם.
שאלות ותגובות על השאלה
🎓 לא הבנתם משהו? קבלו הסבר נוסף ממרצה לתכנות
שאלו כאן — ותקבלו מענה מוסמך.