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)
סעיף א1
סרטט את הגרף G המיוצג על ידי מטריצת הסמיכויות שלפניך.
סעיף א2
מצא את רכיבי הקשירות החזקה (Strong Connected Components — רכ"חים) בגרף שבנית. עבור כל רכ"ח שמצאת רשום את קבוצת הקודקודים שלו.
סעיף א3
קבע מהו המספר המקסימלי של קשתות שאפשר להוסיף מבלי לשנות את מספר הרכ"חים שבגרף הנתון, והגרף עדיין יכיל את אותו מספר רכ"חים שמצאת בסעיף א(2). מהי הקשת שמצאת, או מה הן הקשתות?
שאלות ותגובות על השאלה
🎓 לא הבנתם משהו? קבלו הסבר נוסף ממרצה לתכנות
שאלו כאן — ותקבלו מענה מוסמך.