ראשי > אלגוריתמים בסיסיים בתורת הגרפים > ייצוג גרפים > גרפים כרשימות סמיכות

גרפים כרשימות סמיכות

רשימת סמיכות

הייצוג על ידי רשימת סמיכות של גרף מורכב ממערך Adj של |V| רשימות, אחת עבור כל קודקוד ב-V. עבור כל u השייך ל-V, רשימת הסמיכות [Adj[u מכילה מצביעים לכל הקודקודים v עבורם קיימת קשת u,v.

אם G הוא גרף מכוון אז הסכום של אורכי כל רשימות הסמיכות הוא |E| שכן כל קשת מיוצגת פעם אחת בדיוק. אם G הוא גרף בלתי מכוון אז הסכום של אורכי כל רשימות הסמיכות הוא פי שניים ממספר הקשתות שכן הקשת u,v תיוצג פעם אחת ברשימה של u ופעם נוספת ברשימת של v.

דוגמא

דוגמא נוספת קיימת בסוף פרק זה.