مسئله‌ی Eulerian Path و Eulerian Circuit از معروف‌ترین مسائل نظریه گراف است و برخلاف Hamiltonian Path تمرکز اصلی آن روی یال‌ها است.

سؤال اصلی این است:

آیا می‌توان مسیری پیدا کرد که از هر Edge دقیقاً یک‌بار عبور کند؟

اگر چنین مسیری وجود داشته باشد، آن را Eulerian Path یا Euler Trail می‌نامیم.

اگر این مسیر در پایان دوباره به رأس شروع برگردد، یک Eulerian Circuit یا Eulerian Cycle داریم.

این مسئله فقط یک مفهوم تئوری نیست؛ در طراحی مسیر خیابان‌روبی، بازرسی کابل‌ها و لینک‌های شبکه، Route Inspection، تولید مسیر روی گراف و مسائل مشابه کاربرد دارد.

در این مقاله از تعریف ساده شروع می‌کنیم، تفاوت آن را با Hamiltonian Path بررسی می‌کنیم، شروط Degree را یاد می‌گیریم و بعد الگوریتم مشهور Hierholzer را با JavaScript پیاده‌سازی می‌کنیم.

تعریف Eulerian Path

یک Eulerian Path مسیری است که:

• از تمام یال‌های گراف عبور می‌کند.
• هر یال را دقیقاً یک‌بار استفاده می‌کند.
• لازم نیست به نقطه شروع برگردد.
• ممکن است بعضی رأس‌ها چند بار دیده شوند.

این نکته آخر بسیار مهم است.

در Eulerian Path هدف این نیست که هر Vertex فقط یک‌بار دیده شود.

بلکه هدف این است که:

Each Edge exactly once

تعریف Eulerian Circuit

Eulerian Circuit همان Eulerian Path است، با این تفاوت که:

Start Vertex = End Vertex

مثلاً اگر مسیر زیر تمام یال‌های گراف را دقیقاً یک بار مصرف کند:

A → B → C → D → A

و از تمام Edgeها استفاده شده باشد، یک Eulerian Circuit داریم.

تفاوت Path و Circuit

Eulerian Path
=
استفاده از همه Edgeها دقیقاً یک‌بار

Eulerian Circuit
=
Eulerian Path
+
بازگشت به رأس شروع

مهم‌ترین تفاوت با Hamiltonian

این یکی از مهم‌ترین تفاوت‌هایی است که در نظریه گراف باید بدانیم.

Eulerian

تمرکز روی:

Edge

شرط:

هر یال دقیقاً یک بار

رأس می‌تواند چند بار دیده شود.

Hamiltonian

تمرکز روی:

Vertex

شرط:

هر رأس دقیقاً یک بار

لازم نیست همه یال‌ها استفاده شوند.

پس به‌صورت خلاصه:

Eulerian = Edge-oriented
Hamiltonian = Vertex-oriented

یک مثال ساده

گراف زیر را در نظر بگیرید:

A ----- B
| \     |
|  \    |
D ----- C

فرض کنید چند یال اضافی هم بین رأس‌ها داریم.

در Hamiltonian Path شاید فقط یک مسیر مثل:

A → B → C → D

کافی باشد.

اما در Eulerian Path باید تک‌تک یال‌های گراف را مصرف کنیم، حتی اگر مجبور شویم از بعضی رأس‌ها چند بار عبور کنیم.

داستان پل‌های Königsberg

Eulerian Path از یکی از مشهورترین مسائل تاریخ ریاضیات به وجود آمد.

در شهر Königsberg چند بخش خشکی با هفت پل به هم متصل بودند.

سؤال مردم این بود:

آیا می‌توان از نقطه‌ای شروع کرد، از هر پل دقیقاً یک بار عبور کرد و مسیر را کامل کرد؟

Leonhard Euler این مسئله را در قرن هجدهم بررسی کرد.

او به جای تمرکز روی شکل جغرافیایی شهر، مسئله را به صورت گراف مدل کرد:

• هر بخش خشکی = Vertex
• هر پل = Edge

و نشان داد چنین مسیری وجود ندارد.

این کار یکی از پایه‌های شکل‌گیری نظریه گراف محسوب می‌شود.

چرا Degree در Eulerian Path مهم است؟

در گراف بدون‌جهت، Degree یک رأس تعداد یال‌های متصل به آن است.

مثلاً:

A -- B
|    |
C -- D

اگر سه یال به A متصل باشند:

degree(A) = 3

دلیل اهمیت Degree ساده است.

هر بار که وارد یک رأس می‌شویم معمولاً باید از یک یال دیگر خارج شویم.

پس یال‌ها در بسیاری از رأس‌ها به شکل جفت مصرف می‌شوند:

enter + leave

به همین دلیل زوج یا فرد بودن Degree تعیین‌کننده می‌شود.

شرط Eulerian Circuit در گراف بدون جهت

یک گراف بدون جهت دارای Eulerian Circuit است اگر:

1. همه رأس‌هایی که Degree غیرصفر دارند در یک Connected Component باشند.
2. Degree تمام رأس‌ها زوج باشد.

یعنی:

oddDegreeCount = 0

مثال

degree(A) = 2
degree(B) = 4
degree(C) = 2
degree(D) = 2

همه Degreeها زوج‌اند.

اگر بخش دارای یال گراف connected باشد، Eulerian Circuit داریم.

شرط Eulerian Path در گراف بدون جهت

برای وجود Eulerian Path که Circuit نباشد:

1. همه رأس‌های دارای Degree غیرصفر باید connected باشند.
2. دقیقاً دو رأس Degree فرد داشته باشند.

یعنی:

oddDegreeCount = 2

در این حالت:

• مسیر باید از یکی از رأس‌های Odd شروع شود.
• در رأس Odd دیگر تمام شود.

حالت‌های مهم

0 odd vertices
→ Eulerian Circuit exists

2 odd vertices
→ Eulerian Path exists

More than 2 odd vertices
→ No Eulerian Path

این قانون یکی از تمیزترین و مهم‌ترین قوانین نظریه گراف است.

چرا دقیقاً دو رأس فرد؟

فرض کنید مسیر از A شروع و در B تمام شود.

در رأس‌های میانی:

enter + leave

یال‌ها به صورت جفت استفاده می‌شوند، پس Degree مؤثر زوج است.

اما در رأس شروع یک خروج اضافه داریم.

در رأس پایان یک ورود اضافه داریم.

بنابراین این دو رأس می‌توانند Degree فرد داشته باشند.

بررسی وجود Eulerian Path با JavaScript

برای گراف بدون جهت:

function hasEulerianPath(graph) {
  const nodes = Object.keys(graph);

  let oddCount = 0;

  for (const node of nodes) {
    const degree = graph[node]?.length ?? 0;

    if (degree % 2 !== 0) {
      oddCount++;
    }
  }

  return oddCount === 0 || oddCount === 2;
}

البته این کد فقط Degreeها را بررسی می‌کند.

در نسخه واقعی باید Connectivity رأس‌های دارای Degree غیرصفر را نیز بررسی کنیم.

بررسی Connectivity

رأس‌های ایزوله در اینجا اهمیت خاصی ندارند، چون هیچ Edgeای برای مصرف ندارند.

بنابراین کافی است بررسی کنیم تمام رأس‌هایی که Degree آن‌ها بیشتر از صفر است به هم متصل باشند.

function isConnectedIgnoringIsolated(graph) {
  const nodes = Object.keys(graph);

  const start = nodes.find(
    node => (graph[node]?.length ?? 0) > 0
  );

  if (!start) return true;

  const visited = new Set();
  const stack = [start];

  while (stack.length) {
    const node = stack.pop();

    if (visited.has(node)) continue;

    visited.add(node);

    for (const next of graph[node] ?? []) {
      if (!visited.has(next)) {
        stack.push(next);
      }
    }
  }

  return nodes.every(node => {
    const degree = graph[node]?.length ?? 0;

    return degree === 0 || visited.has(node);
  });
}

تشخیص نوع مسیر اویلری

می‌توانیم این منطق را در یک تابع قرار دهیم:

function getEulerianType(graph) {
  if (!isConnectedIgnoringIsolated(graph)) {
    return "NONE";
  }

  let oddCount = 0;

  for (const node of Object.keys(graph)) {
    if ((graph[node]?.length ?? 0) % 2 !== 0) {
      oddCount++;
    }
  }

  if (oddCount === 0) {
    return "CIRCUIT";
  }

  if (oddCount === 2) {
    return "PATH";
  }

  return "NONE";
}

الگوریتم Hierholzer چیست؟

بعد از اینکه مطمئن شدیم Eulerian Path یا Circuit وجود دارد، باید خود مسیر را بسازیم.

یکی از بهترین الگوریتم‌ها برای این کار Hierholzer's Algorithm است.

ایده کلی:

1. از یک رأس مناسب شروع می‌کنیم.
2. تا وقتی یال استفاده‌نشده وجود دارد، جلو می‌رویم.
3. هر یال را بعد از استفاده حذف یا Mark می‌کنیم.
4. وقتی به رأسی رسیدیم که یال استفاده‌نشده ندارد، آن رأس را وارد جواب می‌کنیم.
5. با Backtrack شدن Stack، مسیر نهایی شکل می‌گیرد.
6. در پایان جواب را Reverse می‌کنیم.

چرا خروجی را هنگام برگشت می‌سازیم؟

این بخش در ابتدا کمی عجیب است.

فرض کنید از یک رأس وارد مسیری می‌شویم و تمام Edgeهای ممکن را مصرف می‌کنیم.

وقتی دیگر یالی وجود ندارد، مطمئنیم این رأس باید در انتهای بخش فعلی مسیر قرار بگیرد.

پس آن را هنگام Backtrack به path اضافه می‌کنیم.

به همین دلیل خروجی اولیه برعکس ساخته می‌شود.

Hierholzer روی گراف جهت‌دار

برای گراف جهت‌دار پیاده‌سازی ساده‌تر است، چون حذف یک یال فقط از adjacency list مبدأ انجام می‌شود.

function eulerTrailDirected(graph, start) {
  const g = Object.fromEntries(
    Object.entries(graph).map(
      ([node, edges]) => [node, [...edges]]
    )
  );

  const stack = [start];
  const path = [];

  while (stack.length > 0) {
    const current = stack[stack.length - 1];

    if ((g[current]?.length ?? 0) > 0) {
      const next = g[current].pop();
      stack.push(next);
    } else {
      path.push(stack.pop());
    }
  }

  return path.reverse();
}

نکته مهم درباره گراف بدون جهت

در گراف بدون جهت یک Edge معمولاً در هر دو adjacency list ذخیره می‌شود.

مثلاً:

A -- B

ممکن است به صورت:

A: ["B"]
B: ["A"]

ذخیره شود.

اگر فقط از لیست A، مقدار B را حذف کنیم، Edge هنوز در لیست B باقی مانده و ممکن است دوباره استفاده شود.

پس باید هر Edge را در هر دو جهت حذف کنیم.

پیاده‌سازی Hierholzer برای گراف بدون جهت

برای سادگی فرض می‌کنیم هیچ Parallel Edge خاصی نداریم.

function eulerTrailUndirected(graph, start) {
  const g = Object.fromEntries(
    Object.entries(graph).map(
      ([node, edges]) => [node, [...edges]]
    )
  );

  const stack = [start];
  const path = [];

  while (stack.length > 0) {
    const current = stack[stack.length - 1];

    if ((g[current]?.length ?? 0) > 0) {
      const next = g[current].pop();

      const reverseIndex =
        g[next]?.indexOf(current) ?? -1;

      if (reverseIndex !== -1) {
        g[next].splice(reverseIndex, 1);
      }

      stack.push(next);
    } else {
      path.push(stack.pop());
    }
  }

  return path.reverse();
}

برای MultiGraph بهتر است هر Edge یک ID مستقل داشته باشد.

انتخاب رأس شروع

در گراف بدون جهت:

اگر Eulerian Circuit داریم

همه Degreeها زوج‌اند.

می‌توانیم از هر رأس با Degree بیشتر از صفر شروع کنیم.

اگر Eulerian Path داریم

دقیقاً دو رأس Odd داریم.

باید از یکی از آن‌ها شروع کنیم.

function findEulerStart(graph) {
  const nodes = Object.keys(graph);

  const oddNodes = nodes.filter(
    node => (graph[node]?.length ?? 0) % 2 !== 0
  );

  if (oddNodes.length === 2) {
    return oddNodes[0];
  }

  return nodes.find(
    node => (graph[node]?.length ?? 0) > 0
  ) ?? nodes[0];
}

یک مثال مرحله‌به‌مرحله

فرض کنید گراف:

A -- B
|    |
D -- C

یعنی:

const graph = {
  A: ["B", "D"],
  B: ["A", "C"],
  C: ["B", "D"],
  D: ["A", "C"]
};

Degreeها:

A = 2
B = 2
C = 2
D = 2

همه زوج‌اند.

پس Eulerian Circuit وجود دارد.

یکی از جواب‌ها:

A → B → C → D → A

تمام Edgeها دقیقاً یک بار استفاده شده‌اند و مسیر به شروع برگشته است.

مثالی با Eulerian Path ولی بدون Circuit

فرض کنید:

A -- B -- C
     |
     D

Degreeها:

A = 1
B = 3
C = 1
D = 1

اینجا چهار رأس Degree فرد داریم.

پس حتی Eulerian Path هم وجود ندارد.

حالا اگر ساختار طوری باشد که فقط دو رأس Odd داشته باشیم، Eulerian Path وجود خواهد داشت ولی Eulerian Circuit نداریم.

گراف جهت‌دار چه شرایطی دارد؟

در Directed Graph به جای Degree ساده باید دو مفهوم را در نظر بگیریم:

in-degree
out-degree

Eulerian Circuit در گراف جهت‌دار

برای هر رأس فعال باید:

inDegree(v) = outDegree(v)

باشد.

همچنین بخش دارای Edge گراف باید از نظر اتصال مناسب باشد.

Eulerian Path در گراف جهت‌دار

باید:

• یک رأس داشته باشیم که:

outDegree = inDegree + 1

باشد؛ این رأس Start است.

• یک رأس داشته باشیم که:

inDegree = outDegree + 1

باشد؛ این رأس End است.

• برای تمام رأس‌های دیگر:

inDegree = outDegree

باشد.

مثال جهت‌دار

فرض کنید:

A → B
B → C
C → A
A → D

Degreeها:

A:
out = 2
in = 1

D:
out = 0
in = 1

اگر سایر رأس‌ها balanced باشند:

A = start
D = end

و ممکن است Eulerian Path وجود داشته باشد.

پیچیدگی Hierholzer

اگر ساختار داده به درستی طراحی شود، هر Edge فقط یک بار پردازش می‌شود.

بنابراین:

Time Complexity = O(V + E)

یا در بسیاری از توضیح‌ها، چون بخش غالب پیمایش Edgeهاست:

O(E)

پیچیدگی فضایی نیز معمولاً:

O(V + E)

است، چون یک کپی از گراف، Stack و مسیر نگه می‌داریم.

مقایسه Hierholzer با Fleury

الگوریتم دیگری به نام Fleury's Algorithm نیز برای Eulerian Path وجود دارد.

ایده Fleury:

تا جایی که مجبور نشده‌ای، Bridge را انتخاب نکن.

این ایده آموزشی و شهودی است ولی بررسی مکرر Bridge می‌تواند هزینه بیشتری ایجاد کند.

Hierholzer معمولاً:

• ساده‌تر برای پیاده‌سازی بهینه،
• سریع‌تر،
• و مناسب‌تر برای سیستم‌های واقعی

است.

Bridge چه ارتباطی با Fleury دارد؟

اگر در میانه مسیر یک Bridge را زود مصرف کنیم، ممکن است بخش باقی‌مانده گراف را از دسترس خارج کنیم.

برای همین Fleury سعی می‌کند Bridge را فقط زمانی مصرف کند که انتخاب دیگری وجود ندارد.

اما Hierholzer با ساخت و ادغام Cycleها مسئله را هوشمندانه‌تر حل می‌کند.

کاربردهای واقعی

1. Street Sweeping

فرض کنید خودرو باید تمام خیابان‌های یک محدوده را تمیز کند.

اگر:

• Intersectionها = Vertex
• Streetها = Edge

باشند، هدف بسیار نزدیک به Eulerian Routing است.

اگر Eulerian Circuit وجود داشته باشد، می‌توان تمام خیابان‌ها را دقیقاً یک بار پیمایش کرد.

2. Route Inspection

در مسائل بازرسی شبکه، ممکن است لازم باشد تمام Edgeها بازدید شوند.

مثلاً:

• خطوط انتقال
• کابل‌ها
• لوله‌ها
• مسیرهای زیرساختی

3. Network Link Inspection

اگر هدف بررسی تک‌تک Linkهای شبکه باشد، مدل Edge-based اهمیت دارد.

در این حالت Eulerian مفهومی طبیعی‌تر از Hamiltonian است.

4. DNA Assembly و de Bruijn Graph

در بسیاری از مدل‌های Sequence Assembly، قطعات یا k-merها طوری به گراف تبدیل می‌شوند که بازسازی توالی به پیدا کردن Eulerian Path در de Bruijn Graph مربوط می‌شود.

این یکی از کاربردهای مهم نظریه Eulerian در Bioinformatics است.

5. رسم شکل بدون برداشتن قلم

بسیاری از پازل‌های «این شکل را بدون برداشتن قلم و بدون تکرار خط رسم کن» در اصل Eulerian Path هستند.

چون:

Line = Edge

و هدف استفاده از هر خط دقیقاً یک بار است.

6. تست مسیرهای ارتباطی

در بعضی مدل‌های تست سیستم و شبکه، نیاز داریم تمام Transitionها یا Linkها پوشش داده شوند.

اگر هر Transition دقیقاً یک بار لازم باشد، مسئله می‌تواند ساختار Eulerian داشته باشد.

Chinese Postman Problem چیست؟

در دنیای واقعی ممکن است گراف Eulerian نباشد.

مثلاً خیابان‌روب مجبور باشد بعضی خیابان‌ها را بیش از یک بار طی کند.

در این حالت مسئله به Chinese Postman Problem نزدیک می‌شود.

هدف آن:

پیدا کردن کم‌هزینه‌ترین مسیر بسته‌ای که تمام Edgeها را حداقل یک بار پوشش دهد.

تفاوت مهم:

Eulerian:
هر Edge دقیقاً یک بار

Chinese Postman:
هر Edge حداقل یک بار
+
کمینه کردن هزینه تکرار

Edge Caseهای مهم

گراف بدون Edge

اگر گراف Edge نداشته باشد، تعریف Trail می‌تواند بر اساس Convention متفاوت باشد، اما از نظر عملی چیزی برای پیمایش وجود ندارد.

رأس‌های ایزوله

رأس‌هایی با Degree صفر برای Eulerian Trail روی Edgeهای موجود مانع نیستند.

به همین دلیل در Connectivity آن‌ها را Ignore می‌کنیم.

MultiGraph

اگر بین دو رأس چند Edge موازی وجود داشته باشد، نباید فقط بر اساس نام همسایه Edge را حذف کنیم.

بهتر است هر Edge دارای ID مستقل باشد.

Self-loop

Self-loop نیز یک Edge واقعی است و Degree را در گراف بدون جهت دو واحد افزایش می‌دهد.

Directed Graph

نباید شروط Degree گراف بدون جهت را روی Directed Graph اعمال کنیم.

در آنجا in-degree و out-degree اهمیت دارند.

اشتباه رایج در پیاده‌سازی

کدی مثل:

g[u].pop()

به تنهایی برای گراف بدون جهت کافی نیست.

چون Edge معکوس هنوز در لیست همسایه باقی مانده است.

همین موضوع می‌تواند باعث شود الگوریتم یک یال را دوبار حساب کند.

مقایسه نهایی مسائل مشهور

چه زمانی Eulerian مناسب است؟

وقتی:

• باید همه Edgeها پوشش داده شوند.
• هر Edge ideally دقیقاً یک‌بار استفاده شود.
• عبور چندباره از Vertex مشکلی ندارد.
• ساختار مسئله Edge-centric است.

چه زمانی مناسب نیست؟

اگر همه Vertexها باید دقیقاً یک‌بار دیده شوند:

Hamiltonian

اگر بهترین تور وزن‌دار بین رأس‌ها مهم است:

TSP

اگر فقط از A به B کوتاه‌ترین مسیر را می‌خواهید:

Dijkstra / A*

اگر باید تمام Edgeها حداقل یک بار با کمترین هزینه پوشش داده شوند:

Chinese Postman

مناسب‌تر است.

جمع‌بندی

Eulerian Path مسیری است که تمام Edgeهای گراف را دقیقاً یک بار مصرف می‌کند.

Eulerian Circuit همین کار را انجام می‌دهد و در پایان به رأس شروع برمی‌گردد.

در گراف بدون جهت:

0 Odd Degree
→ Eulerian Circuit

2 Odd Degrees
→ Eulerian Path

More than 2
→ No Eulerian Trail

البته شرط Connectivity بخش دارای Edge نیز باید برقرار باشد.

در گراف جهت‌دار، رابطه بین in-degree و out-degree تعیین‌کننده است.

برای ساخت مسیر، الگوریتم Hierholzer انتخاب بسیار مناسبی است و با پیاده‌سازی درست در حدود O(V + E) اجرا می‌شود.

مهم‌ترین نکته برای تشخیص مسئله این است:

اگر باید همه Edgeها را پوشش بدهی → Eulerian

اگر باید همه Vertexها را یک بار ببینی → Hamiltonian

همین تفاوت کوچک ظاهری، دو خانواده کاملاً متفاوت از مسائل گراف را ایجاد می‌کند.