גרפים›ייצוג גרפים

שאלה זו שלושה סעיפים לא-קשורים; במקור א-ב-ג. קטע זה כולל רק תת-סעיפי א (1),(2),(4) — תת-סעיף א(3) (מציאת מעגל קצר ביותר באורך זוגי) הושמט מהמיון הזה (אין הוכחה לקיום פתרון תקין, ר' SELECTION-3), וסעיפים ב,ג (בעיית תחבורה, שיטת MODI) אינם במסלול הנוכחי ולא נכללים. G=(V,E) הוא גרף מכוון המיוצג על ידי מטריצת השכנות שלו:

מטריצת השכנות של G (שורה=מקור, עמודה=יעד)

    a b c d e
  a 0 1 1 0 0
  b 0 0 0 1 0
  c 0 1 0 0 0
  d 0 0 1 0 1
  e 0 1 0 0 0

סעיף א1

סרטט את הגרף G המיוצג על ידי המטריצה.

סעיף א2

מצא את רכיבי הקשירות החזקה (Strong Connected Components) של הגרף הנתון. עבור כל רכ"ח שגודלו כל קבוצת הקדקודים שלו.

סעיף א4

מהו המספר המינימלי של קשתות שיש להוסיף לגרף הנתון כדי שיהיה רק רכ"ח אחד? מהי הקשת שיש להוסיף כדי להשיג זאת (אחת בלבד)?

שאלות ותגובות על השאלה

🎓 לא הבנתם משהו? קבלו הסבר נוסף ממרצה לתכנות

שאלו כאן — ותקבלו מענה מוסמך.

🎓 מרצה לתכנות עונה כאן — תקבלו מענה מקצועי