مرتب‌سازی توپولوژیکی

در نظریه گرافها، یک مرتب‌سازی موضعی یا ترتیب موضعی یک گراف بدون دور جهت دار، یک ترتیب خطی از همه رئوس آن است به‌طوری‌که هر گره قبل از همه گره‌هایی می‌آید که از آن به آن‌ها یال خارج شده‌است. هر درخت بدون دور جهت دار یک یا چند مرتب‌سازی موضعی دارد. اگر گراف بدون دور نباشد آنگاه هیچ ترتیب خطی به این صورت وجود ندارد.

مثال‌ها

کاربرد اصلی مرتب‌سازی موضعی (ترتیب موضعی) در زمانبندی یک سلسله‌ای از کارها یا وظایف است. الگوریتم‌های مرتب‌سازی موضعی اولین بار در اوایل دهه ۱۹۶۰ در زمینه تکنیک بررسی و ارزیابی برنامه (PERT) برای زمانبندی در مدیریت پروژه مورد مطالعه قرار گرفت (Jarnagin ۱۹۶۰). کارها با رئوس نشان داده می‌شوند و یک یال از x به y وجود دارد اگر کار x باید تمام شود تا کار y بتواند شروع شود. (برای مثال در زمان شستن لباس‌ها، قبل از شروع خشک شدن لباس‌ها، کار شستن باید تمام شود) پس یک مرتب‌سازی موضعی به ما یک ترتیب برای انجام کارها می‌دهد.

گراف زیر، تعداد زیادی مرتب‌سازی موضعی قابل قبول دارد. مثل:

۷،۵،۳،۱۱،۸،۲،۹،۱۰ (چپ به راست)

۳،۵،۷،۸،۱۱،۲،۹،۱۰(اول کم شماره‌ترین رأس ممکن)

۳،۷،۸،۵،۱۱،۱۰،۲،۹

۵،۷،۳،۸،۱۱،۱۰،۹،۲(اول کم‌ترین تعداد رأس)

۷،۵،۱۱،۳،۱۰،۸،۹،۲(اول پرشماره‌ترین رأس ممکن)

۷،۵،۱۱،۲،۳،۸،۹،۱۰(از بالا به پایین)

الگوریتم‌ها

الگوریتم معمول مرتب‌سازی موضعی در زمان خطی تعداد رأس‌ها به اضافه تعداد یال‌ها یعنی ((O(V+E) اجرا می‌شود.

یکی از این الگوریتم‌ها که اولین بار توسط(kahn (۱۹۶۲ شرح داده شد، با انتخاب رئوسی که در یک ترتیب احتمالی مرتب‌سازی موضعی هستند، کار می‌کند. اول یک لیست از رأس‌ها شروع را که هیچ یال وارد شونده‌ای ندارند را پیدا می‌کند و آن‌ها را در یک مجموعه می‌گذارد، حداقل یکی از همچنین گره‌هایی وجود دارد اگر گراف بدون دور باشد، سپس:

L ← Empty list that will contain the sorted elements
S ← Set of all nodes with no incoming edges
while S is non-empty do
    remove a node n from S
    insert n into L
    for each node m with an edge e from n to m do
        remove edge e from the graph
        if m has no other incoming edges then
            insert m into S
if graph has edges then
    output error message (graph has at least one cycle)
else 
    output message (proposed topologically sorted order: L)

اگر یک گراف، یک گراف بدون دور جهت دار باشد، لیست L حاوی یک جواب است (جواب یکتا نیست). در غیر این صورت، گراف حداقل یک دور دارد پس یک مرتب‌سازی موضعی غیرممکن است.

توجه کنید که با توجه به غیر یکتا بودن نتیجه مرتب‌سازی، ساختار S می‌تواند یک مجموعه یا یک صف یا یک پشته باشد. بسته به ترتیبی که گره‌ها از مجموعه S خارج می‌شوند، جواب‌ها ی مختلف ایجاد می‌شود.

یک الگوریتم دیگر برای مرتب‌سازی موضعی بر پایه جستجوی عمق اول است. روی رئوس گراف حلقه می‌زنیم، به هر ترتیبی، برای هر رأسی که قبلاً توسط یک جستجوی دیگر ملاقات نشده یک جستجوی عمق اول را آغاز می‌کنیم. مرتب‌سازی موضعی مطلوب عکس پس ترتیب این جستجوهاست. یعنی ما می‌توانیم این ترتیب را به صورت یک لیست از رئوس بسازیم با اضافه کردن هر رأس به شروع لیست وقتی که جستجوی عمق اول روی آن در حال پردازش است و از پردازش روی همه بچه‌های آن رأس برگشته است. تا وقتی که هر رأس و یال یک بار دیده شوند، الگوریتم در زمان خطی اجرا می‌شود. این الگوریتم بر پایه جستجوی عمق اول اولین بار به وسیلهٔ (Cormen,Leiserson & Rivest(1990 بیان شده ولی اولین بار توسط (Tarjan(1976 نوشته شده‌است.

یکتایی

اگر یک مرتب‌سازی موضعی این ویژگی را داشته باشد که همه جفت رأس‌های پی در پی در یک ترتیب مرتب شده با یال‌ها به هم وصل شده‌اند، آنگاه این یال‌ها یک مسیر همیلتونی جهت‌دار را در این گراف جهت‌دار بدون دور می‌سازند. اگر یک مسیر همیلتونی وجود داشته باشد، مرتب‌سازی موضعی یکتاست و هیچ ترتیب دیگری یال‌های مسیر را مربوط نمی‌کند. برعکس، اگر یک مرتب‌سازی موضعی یک مسیر همیلتونی را نسازد، گراف بدون دور جهت دار بیش از یک مرتب‌سازی موضعی دارد. در این موارد همیشه می‌توان یک ترتیب قابل قبول دیگر با جابه جا دو رأس پی در پی که با یک یال به هم متصل نیستند، ساخت. پس، می‌توان در زمان چندجمله‌ای چک کرد که یک مرتب‌سازی موضعی یکتا موجود است و دور همیلتونی دارد یا خیر، با وجود np-hard بودن مسئله مسیر همیلتونی برای بیشتر گراف‌های جهت دار.

منابع

• Jarnagin, M. P. (1960), Automatic machine methods of testing PERT networks for consistency, Technical Memorandum No. K-24/60, Dahlgren, Virginia: U. S. Naval Weapons Laboratory.
• Kahn, A. B. (1962), "Topological sorting of large networks", Communications of the ACM 5): 558–562, doi:10.1145/368996.369025.
• Tarjan, Robert E. (1976), "Edge-disjoint spanning trees and depth-first search", Algorithmica 6 (2): 171–185, doi:10.1007/BF00268499.
• Vernet, Lilian; Markenzon (1997), "Hamiltonian problems for reducible flowgraphs", Proc. 17th International Conference of the Chilean Computer Science Society (SCCC '97), pp. 264–267, doi:10.1109/SCCC.1997.637099 .