עמוד:289

הגדרות . ? הגרף המכוון , G שקדקודיו מייצגים משימות או פעילויות והקשתות המכוונות מייצגות יחס קדימויות בין המשימות , נקרא רשת . ( Activity On Vertex ) AOV קדקוד u ברשת AOV נקרא קדקוד מקדים של הקדקוד DN v ורק אם קיים מסלול מכוון « -מ . 1-ל קדקוד v ברשת AOV נקרא קדקוד עוקב של הקדקוד u אם הקדקוד u הוא קדקוד מקדים של הקדקוד ע . מיון טיפולוגי ( topological sort ) של גרף מכוון ללא מעגלים הוא סידור ליניארי של כל קדקודי הגרף כך שאם בגרף יש קשת מכוונת ל , (/ , _/ אזי / מופיע לפני 7 בסידור זה . בהמשך לדוגמה שראינו לעיל , להלן שתי אפשרויות למיון טופולוגי , מבין האפשרויות הרבות לסידור טופולוגי , ואלו הן ? . הערה ו אם בגרף ישנו לפחות מעגל אחד , אזי לא ניתן לסדר את קדקודי הגרף בשום סדר ליניארי שיכול לייצג את המיון הטופולוגי . בדוגמה הנדונה , המשמעות של מעגל היא שקורס כלשהו מהווה דרישת-קדם של אותו קורס , כלומר , הקדקוד » הוא קדקוד מקדים של . « פירושו של דבר - תלמיד חייב לסיים את הקורס » לפני שהוא מתחיל ללמוד את הקורס . 11 ברור שמצב כזה הוא בלתי אפשרי ולכן מיון טופולוגי מוגדר בגרפים מכוונים ללא מעגלים . אם מדיניות האוניברסיטה שבדוגמה היא שבכל סמסטר סטודנט יכול ללמוד רק קורס אחד , אז הוא חייב ללמוד אותם על-פי הסדר הטופולוגי . להלן גרסאות שונות של האלגוריתמים הפשוטים שלהלן , אשר יוצרים סידור ליניארי של קדקודים בגרף מכוון ללא מעגלים , כאשר הסידור הליניארי הזה מייצג את המיון הטופולוגי . בטרם ננסח את האלגוריתם , נתבונן ברשת AOV הזאת

מטח : המרכז לטכנולוגיה חינוכית


לצפייה מיטבית ורציפה בכותר