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