גרפים מכוונים ללא מעגלים משמשים
ביישומים רבים לציון קדימויות בתוך קבוצת מאורעות.
הדוגמה הבאה מייצגת מספר הגדרות במילון מושגים הלקוח מתורת
הגרפים (שים לב כי הגדרות אלה, אינן פורמליות !)
קשת - זוג קודקודים
מעגל - מסלול המתחיל ומסתיים באותו
קודקוד
קודקוד - אובייקט כלשהו
גרף - קבוצת קשתות וקבוצת קודקודים
מסלול - קבוצת קשתות העוברת דרך מספר קודקודים
נסדר את ההגדרות בגרף - כל
מושג יהיה קודקוד, וקשת בין מושג א' למושג ב' מעידה כי מושג
א' נמצא בתוך מושג ב'
(או במלים אחרות: כדי להבין את מושג ב' יש לדעת קודם את
מושג א')
זכור כי מיון טופולוגי ניתן
לבצע רק על גרפים ללא מעגלים, בדיוק כפי שהיית מצפה ממילון
טוב.
במיון טופולוגי הקודקוד שיופיע
ראשון הוא הקודקוד היוצאים ממנו קשתות לשאר הקודקודים, בדוגמא
של המילון, הקודקוד שיופיע ראשון יהיה המושג הבסיסי ביותר.
לחץ על 'הצג' כדי לראות מיון טופולוגי של הדוגמא
בעזרת מיון טופולוגי נדע כיצג
ללמוד מושגים בתורת הגרפים - אם נעבור על המושגים לפי סדר
המיון, לא נתקל בביטויים שאיננו מכירים בבאונו ללמוד ביטויים
חדשים.
בעמוד הבא נלמד את האלגוריתם
של מיון טופולוגי, מומלץ לעבור שוב על הפרק העוסק בסריקת
עומק לפני שמתקדמים הלאה.
