مدار همیلتونی (یا دور همیلتونی) در یک گراف، یک دور (مسیر بسته) است که از یکی از راس‌ها شروع شده و همه‌ی راس‌های دیگر را دقیقا یکبار ملاقات کرده و به همان راس آغازین برمی‌گردد. در دور همیلتونی لازم نیست که از همه‌ی یال‌ها عبور کنیم (برخلاف تور اویلری) بلکه هدف شروع از یک راس، ملاقات کردن همه‌ی راس‌های دیگر و برگشتن به راس مبداء است.

به هر گراف با بیش از یک راس که دور همیلتونی (Hamiltonian Cycle) داشته باشد، گراف همیلتونی می‌گوییم. فرمول خاصی برای یافتن این‌که گراف دارای دور همیلتونی است یاخیر وجود ندارد و فعلا تنها راه تعیین آن، بررسی تمام دورهای ممکن گراف است!

به هر گراف با بیش از یک راس که دور همیلتونی داشته باشد، گراف همیلتونی (Hamiltonian Graph) می‌گوییم.

کد درس	نام درس	گراف متناظر دروس
0	مهندسی نرم‌افزار
1	برنامه‌نویسی مقدماتی
2	برنامه‌نویسی تجاری
3	مبانی کامپیوتر
4	بانک‌های اطلاعاتی
5	برنامه‌نویسی پیشرفته

در شکل بالا، فلش‌ها رابطه‌ی پیش‌نیازی را نشان می‌دهند. مثلا درس مبانی کامپیوتر پیش‌نیاز دروس برنامه‌نویسی مقدماتی، برنامه‌نویسی تجاری و برنامه‌نویسی پیشرفته است. لذا در گراف متناظر این دروس، یال‌های جهت داری از راس 3 (مربوط به درس مبانی کامپیوتر) به طرف هر سه راس 1، 2 و 5 رسم شده‌است. بدیهی است که دانشجو نمی‌تواند برای گذراندن این دروس هر ترتیب دلخواهی را انتخاب کند. آن‌چه از روابط بالا برمی‌آید، این‌است که ابتدا درس 3 باید انتخاب شود، چون هیچ پیش‌نیازی ندارد. درس شماره‌ی 2 هم بدلیل این‌که پیش‌نیاز هیچ درسی نیست، در آخر انتخاب خواهد شد.

برای حل این مسئله باید ترتیب خاصی از رئوس گراف را به‌دست آوریم که در آن، همه‌ی فلش‌ها به طرف انتهای لیست باشد و هیچ فلشی به رئوس ابتدایی اشاره نکند. این مساله به‌نام مرتب‌سازی موضعی (Topological Sorting/Ordering) معروف است.

مرتب‌سازی موضعی، Topological Sorting یا Topological Ordering برای یک گراف جهت‌دار G عبارت است از یک ترتیب مشخص برای رئوس آن، به‌طوری که برای هر دو راس u و v، اگر یال جهت‌داری از u به v در گراف G وجود دارد، پس u قبل از v در آن ترتیب ظاهر شود.

یک نمونه ترتیب موضعی صحیح می‌تواند از چپ به راست به‌صورت زیر باشد:

3, 1, 5, 4, 0, 2

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

دقت داشته باشید که لزوما مرتب‌سازی موضعی رئوس به‌ازای هر گراف جهت‌داری مانند G امکان‌پذیر نیست. همچنین مربت‌سازی موضعی برای گراف‌های بدون جهت قابل تعریف نمی‌باشد.
شرط لازم و کافی برای داشتن ترتیب موضعی این است که G فاقد دور جهت‌دار باشد.

مرتب سازی موضعی فقط برای گراف جهت‌دار بدون دور (DAG) امکان‌پذیر است. به‌دلیل نداشتن دور، روابط علت-معلولی، ترتیب زمانی و سلسله مراتبی با این نوع گراف نمایش داده می‌شود. لذا مرتب‌سازی موضعی معمولا در این نوع مسئله‌ها کاربرد دارد. روش‌های مختلفی برای حل مسئله‌ی مرتب‌سازی موضعی وجود دارد. یکی از بهترین الگوریتم‌های موجود الگوریتم Kahn است که در مطلب جداگانه‌ای به آن اشاره شده است. در اینجا سعی داریم مسئله را با استفاده از الگوریتم پیمایش اول‌عمق (DFS) حل کنیم که اولین بار در سال 1976 توسط Robert Endre Tarjan ریاضی‌دان و دانشمند علوم کامپیوتر امریکایی ارائه شد.

کافی است که به ازای همه‌ی رئوس گراف (با هر ترتیب دلخواهی)، پیمایش اول‌عمق انجام دهیم. دقت کنید که هر راس را فقط یکبار مرور کنید. برای این‌کار رئوس را علامت‌گذاری می‌کنیم. از هر راسی که خارج شدیم، آن را به پشته اضافه می‌کنیم. در پایان، با برداشتن همه‌ی رئوس از پشته، به ترتیبِ موضعیِ گرافِ داده شده می‌رسیم. در ادامه برای گراف دروس که در بالا معرفی شد، همین مراحل را با جزئیات دنبال می‌کنیم.

بیائید برای راحتی کار -و پیاده‌سازی راحت‌تر-، رئوس را به‌ترتیبِ شماره بپیماییم. از راس صفر شروع می‌کنیم و ابتدا آن‌را علامت‌گذاری می‌کنیم تا در آینده دوباره با پیمایش مجدد آن در دام حلقه‌ی بی‌پایان نیافتیم. سپس به سراغ همه‌ی رئوسی که مستقیما از راس صفر در دسترس هستند می‌رویم. فقط راس شماره‌ی 2 از راس صفر در دسترس است، لذا همه‌ی مراحل قبل را بر روی راس 2 تکرار می‌کنیم. راس 2 را علامت‌گذاری کرده و چون هیچ یالی از آن خارج نشده، پس نمی‌توانیم به سراغ راس دیگری برویم پس آن را به پشته اضافه کرده و از آن خارج می‌شویم. به راس صفر برمی‌گریم تا یال بعدی خارج شده از آن را دنبال می‌کنیم، چنین یالی وجود ندارد لذا آن را هم به پشته اضافه کرده و خارج می‌شویم. راس بعدی که علامت نخورده، راس شماره‌ی یک است. مراحل قبل را بر روی این راس تکرار می‌کنیم تا به راس 5 و سپس 4 برسیم. با توجه به این‌که هیچ یالی که به راس علامت‌نخورده منتهی شود وجود ندارد، لذا 4 هم به پشته اضافه شده و به راس 5 باز می‌گردیم....

در پایان اگر همه‌ی رئوس را از پشته خارج کنیم، به ترتیب موضعی گراف می‌رسیم (که در شکل بالا آن را ملاحظه می‌کنید). برنامه‌ی زیر که به زبان C++ نوشته شده، با همین الگوریتم پیاده‌سازی شده است:

1#include <fstream>
2#define MAX 10
3using namespace std;
4int STK[MAX], TOP = -1;
5void DFS(int A[MAX][MAX], int VISIT[MAX], int n, int V) {
6    if (VISIT[V] == 0) {
7        VISIT[V] = 1;
8        for (int I = 0; I < A[V][0]; I++)
9            DFS(A, VISIT, n, A[V][I + 1]);
10        STK[++TOP] = V;
11    }
12}
13void TopologicalSortDFS(int A[MAX][MAX], int n) {
14    int VISIT[MAX] = { 0 };
15    fstream OUT;
16    for (int I = 0; I < n; I++)
17        if (A[I][0] > 0)
18            DFS(A, VISIT, n, I);
19    OUT.open("OUTPUT.TXT", ios::out);
20    while (TOP >= 0)
21        OUT << STK[TOP--] << " ";
22    OUT.close();
23}
24void main() {
25    int n, A[MAX][MAX], I, J, V;
26    fstream IN;
27    IN.open("INPUT.TXT", ios::in);
28    IN >> n;
29    for (I = 0; I < n; I++) {
30        A[I][0] = 0;
31        for (J = 0; J < n; J++) {
32            IN >> V;
33            if (V == 1)
34                A[I][++A[I][0]] = J;
35        }
36    }
37    IN.close();
38    TopologicalSortDFS(A, n);
39}

مرتب‌سازی موضعی از الگوریتم‌های کاربردی و مهم به‌شمار می‌رود. به عنوان نمونه، در مسئله‌ی یافتن کوتاه‌ترین مسیر از این الگوریتم استفاده می‌کنیم.