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

در نظریه گرافها، یک مرتب‌سازی موضعی یا ترتیب موضعی یک گراف بدون دور جهت دار، یک ترتیب خطی از همه رئوس آن است به‌طوری‌که هر گره قبل از همه گره‌هایی می‌آید که از آن به آن‌ها یال خارج شده‌است. هر درخت بدون دور جهت دار یک یا چند مرتب‌سازی موضعی دارد. اگر گراف بدون دور نباشد آنگاه هیچ ترتیب خطی به این صورت وجود ندارد.
مثال‌ها
کاربرد اصلی مرتب‌سازی موضعی (ترتیب موضعی) در زمانبندی یک سلسله‌ای از کارها یا وظایف است. الگوریتم‌های مرتب‌سازی موضعی اولین بار در اوایل دهه ۱۹۶۰ در زمینه تکنیک بررسی و ارزیابی برنامه (PERT) برای زمانبندی در مدیریت پروژه مورد مطالعه قرار گرفت (Jarnagin ۱۹۶۰). کارها با رئوس نشان داده می‌شوند و یک یال از x به y وجود دارد اگر کار x باید تمام شود تا کار y بتواند شروع شود. (برای مثال در زمان شستن لباس‌ها، قبل از شروع خشک شدن لباس‌ها، کار شستن باید تمام شود) پس یک مرتب‌سازی موضعی به ما یک ترتیب برای انجام کارها می‌دهد.
گراف زیر، تعداد زیادی مرتب‌سازی موضعی قابل قبول دارد. مثل:
left
۷،۵،۳،۱۱،۸،۲،۹،۱۰ (چپ به راست)
۳،۵،۷،۸،۱۱،۲،۹،۱۰(اول کم شماره‌ترین راس ممکن)
۳،۷،۸،۵،۱۱،۱۰،۲،۹
۵،۷،۳،۸،۱۱،۱۰،۹،۲(اول کم‌ترین تعداد راس)
۷،۵،۱۱،۳،۱۰،۸،۹،۲(اول پرشماره‌ترین راس ممکن)
۷،۵،۱۱،۲،۳،۸،۹،۱۰(از بالا به پایین)
الگوریتم‌ها
الگوریتم معمول مرتب‌سازی موضعی در زمان خطی تعداد راس‌ها به اضافه تعداد یال‌ها یعنی ((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 بودن مسئله مسیر همیلتونی برای بیشتر گراف‌های جهت دار.