שאלה זו מופיעה בשאלון תחת הכותרת "מבוא לחקר ביצועים", אך סעיף א שלה הוא שאלה עצמאית וטהורה בתורת הגרפים (הסעיף השני של השאלה בשאלון המקורי, סעיף ב, עוסק בבעיית שינוע/סימפלקס ואינו נכלל כאן — אין קשר בין שני הסעיפים במקור). G=(V,E) הוא גרף מכוון המיוצג על ידי מטריצת הסמיכויות שלפניך (נקודות זוכות: הערכה חלקית, כמחצית מנקודות השאלה המקורית, כיוון שרק חצי מהשאלה נכלל).
שאלה זו מופיעה בשאלון תחת הכותרת "מבוא לחקר ביצועים", אך סעיף א שלה הוא שאלה עצמאית וטהורה בתורת הגרפים (הסעיף השני של השאלה בשאלון המקורי, סעיף ב, עוסק בבעיית שינוע/סימפלקס ואינו נכלל כאן — אין קשר בין שני הסעיפים במקור). G=(V,E) הוא גרף מכוון המיוצג על ידי מטריצת הסמיכויות שלפניך (נקודות זוכות: הערכה חלקית, כמחצית מנקודות השאלה המקורית, כיוון שרק חצי מהשאלה נכלל).
מטריצת הסמיכויות של הגרף המכוון G, קודקודים a,b,c,d,e.
a b c d e
a [ 0 0 1 1 0 ]
b [ 1 0 0 1 0 ]
c [ 0 0 0 0 1 ]
d [ 0 1 0 0 0 ]
e [ 1 0 0 0 0 ]
(שורה=מקור, עמודה=יעד; קשתות: a->c, a->d, b->a, b->d, c->e, d->b, e->a)
סרטט את הגרף G המיוצג על ידי מטריצת הסמיכויות שלפניך.
מצא את רכיבי הקשירות החזקה (Strong Connected Components — רכ"חים) בגרף שבנית. עבור כל רכ"ח שמצאת רשום את קבוצת הקודקודים שלו.
קבע מהו המספר המקסימלי של קשתות שאפשר להוסיף מבלי לשנות את מספר הרכ"חים שבגרף הנתון, והגרף עדיין יכיל את אותו מספר רכ"חים שמצאת בסעיף א(2). מהי הקשת שמצאת, או מה הן הקשתות?
שאלות ותגובות על השאלה
🎓 לא הבנתם משהו? קבלו הסבר נוסף ממרצה לתכנות
שאלו כאן — ותקבלו מענה מוסמך.