গ্রাফ অ্যালগরিদম৭ মিনিট পড়া

অয়লারীয় পথ ও সার্কিট (Eulerian Path & Circuit)

আপনি কি প্রতিটি সেতু বা ব্রিজ ঠিক একবার করে পার হতে পারবেন? ১৭৩৬ সালে অয়লার এই প্রশ্নের উত্তর দিয়েছিলেন
existence check:দ্রুত · \(O(V+E)\)Hierholzer's:লিনিয়ার বা রৈখিক · \(O(V+E)\)total:\(O(V+E)\)

১৭৩৬ সালে কোনিগসবার্গ (Königsberg) শহরে সাতটি সেতু ছিল যেগুলো এর বিভিন্ন দ্বীপগুলোকে সংযুক্ত করত। একটি স্থানীয় ধাঁধা ছিল: আপনি কি পুরো শহরটি এমনভাবে ঘুরতে পারবেন যেখানে প্রতিটি সেতু আপনি ঠিক একবারই পার হবেন এবং সবশেষে পুনরায় আপনার ঘরে ফিরে আসবেন?

লিওনার্ড অয়লার (Leonhard Euler) প্রমাণ করেছিলেন যে এটি অসম্ভব — এবং তা করতে গিয়েই তিনি বর্তমানের গ্রাফ থিওরি (graph theory) আবিষ্কার করেছিলেন। তিনি যে মূল ধারণাটি খুঁজে পেয়েছিলেন তা আজও সমানভাবে কার্যকর: আপনি পুরো ধাঁধাটি সমাধান করতে পারেন শুধুমাত্র প্রতিটি ভূখণ্ড বা ল্যান্ডমাসের সাথে কতগুলো সেতু সংযুক্ত আছে তা দেখে।

দুটি মূল প্রশ্ন

একটি অয়লারীয় সার্কিট (Eulerian circuit) একই জায়গা থেকে শুরু এবং শেষ হয়, যেখানে প্রতিটি এজ বা সংযোগ ঠিক একবার ব্যবহার করা হয় (যেমন সব ব্রিজ পার হওয়ার পর বাড়ি ফিরে আসা)। অন্যদিকে, একটি অয়লারীয় পথ (Eulerian path) প্রতিটি এজ ঠিক একবার ব্যবহার করে ঠিকই, তবে এটি শুরুর স্থান থেকে ভিন্ন অন্য কোনো স্থানে গিয়ে শেষ হতে পারে।

ম্যাজিক ডিগ্রি কন্ডিশন (আনডিরেক্টেড বা অনির্দেশিত গ্রাফ)

প্রতিবার যখন আপনি একটি ব্রিজের মাধ্যমে কোনো নোডে বা ভার্টেক্সে প্রবেশ করেন, তখন ফিরে যাওয়ার জন্য আপনার আরও একটি ব্রিজের প্রয়োজন হয় — যদি না এটি একেবারে শুরু বা শেষের বিন্দু হয়। এর মানে হলো:

  • অয়লারীয় সার্কিট তখনই সম্ভব ↔ যখন গ্রাফটি সংযুক্ত থাকে এবং প্রতিটি ভার্টেক্সের ডিগ্রি (degree) অবশ্যই জোড় (even) হয়।
  • অয়লারীয় পথ তখনই সম্ভব ↔ যখন গ্রাফটি সংযুক্ত থাকে এবং ঠিক দুটি ভার্টেক্সের ডিগ্রি বেজোড় (odd) হয় (সেই দুটি ভার্টেক্সই হলো এর শুরু এবং শেষ)।

কোনিগসবার্গের সেই ধাঁধায় চারটি ভূখণ্ডই ছিল বেজোড় ডিগ্রির — তাই এর সার্কিট বা পথ কোনটিই সম্ভব ছিল না। অয়লার মাত্র কয়েক সেকেন্ডে এটি দেখতে পেয়েছিলেন।

ডিরেক্টেড বা নির্দেশিত গ্রাফ (Directed Graphs)

ডিরেক্টেড গ্রাফের ক্ষেত্রে, "জোড় ডিগ্রি" এর বদলে ব্যালেন্সড ইন/আউট-ডিগ্রি (in/out-degree) হিসেবে চিন্তা করুন: একটি অয়লারীয় সার্কিট-এর জন্য প্রতিটি ভার্টেক্সের ইন-ডিগ্রি = আউট-ডিগ্রি হওয়া প্রয়োজন। একটি অয়লারীয় পথ-এর জন্য ঠিক একটি ভার্টেক্সের আউট-ডিগ্রি = ইন-ডিগ্রি + 1 (শুরু) এবং একটির ইন-ডিগ্রি = আউট-ডিগ্রি + 1 (শেষ) হতে হবে।

হায়ারহোলজারের অ্যালগরিদম (Hierholzer's Algorithm): পথ তৈরি করা

পথটি আদৌ সম্ভব কিনা তা যাচাই করা বেশ তুচ্ছ একটি কাজ — তবে আসলে পথটি তৈরি করতে একটু বেশি বুদ্ধিমত্তার প্রয়োজন হয়। হায়ারহোলজারের পদ্ধতিটি ঠিক এইভাবে কাজ করে:

  1. যেকোনো জায়গা থেকে শুরু করুন এবং গ্রিডি বা লোভী হয়ে একে একে এজগুলো অনুসরণ করতে থাকুন (ব্যবহৃত এজগুলোকে চিহ্নিত করে রাখুন) যতক্ষণ না আপনি কোথাও আটকে যান — এটি আপনাকে একটি সার্কিট দেবে, তবে এটি হয়তো সব এজকে কভার নাও করতে পারে।
  2. আপনার তৈরি করা সার্কিটে এমন কোনো ভার্টেক্স খুঁজুন যার এজগুলো এখনো ব্যবহার করা হয়নি। সেখান থেকে নতুন একটি মিনি-সার্কিট শুরু করুন।
  3. এই মিনি-সার্কিটটিকে আগের মূল বা মেইন সার্কিটের সেই ভার্টেক্সের অবস্থানেই জোড়া বা স্প্লাইস (splice) করে দিন।
  4. যতক্ষণ পর্যন্ত কোনো অব্যবহৃত এজ অবশিষ্ট থাকে, ততক্ষণ পর্যন্ত এই প্রক্রিয়াটি পুনরাবৃত্তি করতে থাকুন।

সঠিক ডেটা স্ট্রাকচার (যেমন একটি ডাবলি-লিঙ্কড লিস্ট) ব্যবহার করলে প্রতিটি স্প্লাইস করতে মাত্র \(O(1)\) সময় লাগে, যা আপনাকে সর্বমোট \(O(V+E)\) সময় দেয়।

দ্রষ্টব্য: কোনিগসবার্গের সেতুর ধাঁধায় চারটি বেজোড়-ডিগ্রির ভূখণ্ড ছিল। অয়লারের নিয়ম অনুসারে, পথটি সম্ভব হতে হলে আপনার কাছে ০ বা ২ টি বেজোড়-ডিগ্রির ভার্টেক্স থাকা প্রয়োজন। কিন্তু চারটি থাকার অর্থ হলো এর কোনো সমাধান নেই!

অয়লারীয় পথ — হায়ারহোলজারের অ্যালগরিদম

from collections import defaultdict


def eulerian_path(n, edges):
    adj = defaultdict(list)
    degree = [0] * n
    for u, v in edges:
        adj[u].append(v)
        adj[v].append(u)
        degree[u] += 1
        degree[v] += 1


    # Find start node: odd-degree vertex (or any node for circuit)
    odd = [i for i in range(n) if degree[i] % 2 == 1]
    start = odd[0] if odd else 0


    path = []
    stack = [start]
    while stack:
        v = stack[-1]
        if adj[v]:
            u = adj[v].pop()
            adj[u].remove(v)  # undirected graph: remove both directions
            stack.append(u)
        else:
            path.append(stack.pop())
    return path


# Path: 0-1-2-3-1 (nodes 0 and 3 have odd degree)
edges = [(0,1),(1,2),(2,3),(3,1),(1,0)]
print(eulerian_path(4, edges))
Output
[0, 1, 3, 2, 1, 0]

Complexity

🔢 অস্তিত্ব যাচাই (Existence check)
ইন/আউট ডিগ্রি গণনা করুন এবং সংযোগ বা কানেক্টিভিটি যাচাই করতে বিএফএস/ডিএফএস (BFS/DFS) চালান
ডিগ্রি গণনা — অত্যন্ত দ্রুত \(O(V+E)\)
🗺️ হায়ারহোলজারের বাস্তবায়ন (Hierholzer's construction)
প্রতিটি এজ বা সংযোগ ঠিক একবার অতিক্রম করা হয়; লিঙ্কড লিস্টের সাথে স্প্লাইস অপারেশনগুলো মাত্র \(O(1)\) সময়ে করা যায়
লিনিয়ার বা রৈখিক — প্রতিটি এজ একবার ভিজিট করা হয় \(O(V+E)\)
➕ ভার্চুয়াল এজ ট্রিক (Virtual edge trick)
একটি অয়লারীয় পথকে সার্কিটে রূপান্তর করতে একটি ফেক বা ডামি এজ end→start যোগ করুন; কাজ শেষে ফলাফল হতে সেটি সরিয়ে ফেলুন
অতিরিক্ত ধ্রুবক বা কন্সট্যান্ট খরচ \(O(1)\)

ছোট কুইজ

কোনিগসবার্গের সেতুর ধাঁধায় ৪টি ভূখণ্ড ছিল এবং প্রতিটির সাথে বেজোড় সংখ্যক সেতু যুক্ত ছিল। কেন এই পুরো শহরটি একবার করে সেট পার হয়ে ঘুরে আসা অসম্ভব ছিল?

পড়া চালিয়ে যান

হ্যামিল্টোনীয় পথ (Hamiltonian Path)
প্রতিটি ঘর ঠিক একবার করে ভ্রমণ করুন — এটি প্রতিটি সেতু ভ্রমণের চেয়ে অনেক বেশি কঠিন
→
বিএফএস এবং ডিএফএস পুনর্বিবেচনা (BFS & DFS Revisited)
গ্রাফ অন্বেষণের দুটি উপায় — স্তর অনুযায়ী, অথবা একদম গভীরে গিয়ে
→
টারজানের অ্যালগরিদম (Tarjan's Algorithm)
একটি ডিরেক্টেড গ্রাফের (directed graph) সমস্ত ঘনিষ্ঠভাবে যুক্ত গ্রুপকে (tightly-knit groups) একবার অতিক্রম করেই (one pass) খুঁজে বের করুন
→