ইউলারিয়ান ও হ্যামিলটোনিয়ান পথ

Eulerian & Hamiltonian paths

৯ মিনিট পড়া শুরু · Beginner Python কোডসহ সম্পূর্ণ বাংলায়

এক নজরে · TL;DR

Euler path প্রতিটি edge ঠিক একবার ব্যবহার করে; Euler circuit এমন একটি Euler path যা যেখান থেকে শুরু সেখানেই শেষ হয়।
Euler's theorem: একটি connected গ্রাফে Euler circuit থাকে ⟺ সব vertex-এর ডিগ্রি জোড়; Euler path (circuit ছাড়া) থাকে ⟺ ঠিক দুটি vertex-এর ডিগ্রি বিজোড়।
গ্রাফ থিওরির জন্মকাহিনী — কোনিগসবার্গের সাতটি সেতু (১৭৩৬, Euler) — চারটি ভূখণ্ডের ডিগ্রি 3,3,3,5 (সবগুলো বিজোড়), তাই কোনো Euler path সম্ভব ছিল না।
Hamiltonian path প্রতিটি vertex ঠিক একবার ভ্রমণ করে — কিন্তু এর জন্য Euler's theorem-এর মতো কোনো সহজ শর্ত নেই; সাধারণভাবে এটি নির্ণয় করা NP-complete (M8/L42-এ বিস্তারিত)।

এই পাঠে যা শিখবেন

Euler path ও Euler circuit-এর সংজ্ঞা এবং তাদের মধ্যে পার্থক্য
Euler's theorem-এর সম্পূর্ণ, নির্ভুল বিবৃতি
কোনিগসবার্গের সাতটি সেতুর ঐতিহাসিক সমস্যা ও এর সমাধান
Hamiltonian path ও Hamiltonian circuit-এর সংজ্ঞা এবং কেন এটি Euler path-এর চেয়ে কঠিন সমস্যা
Python-এ ডিগ্রি যাচাই করে Euler circuit-এর যোগ্যতা পরীক্ষা

১ · Euler Path ও Euler Circuit

একটি Euler pathEuler Pathএকটি গ্রাফের এমন একটি trail (walk যেখানে edge পুনরাবৃত্তি হয় না) যা গ্রাফের প্রতিটি edge ঠিক একবার ব্যবহার করে। হলো একটি গ্রাফের এমন একটি trail যা প্রতিটি edge ঠিক একবার ব্যবহার করে (vertex পুনরাবৃত্তি হতে পারে)। যদি এই path যেখান থেকে শুরু হয়, ঠিক সেখানেই শেষ হয়, তাহলে সেটিকে বলা হয় Euler circuit।

Euler's Theorem

একটি connected গ্রাফের জন্য —

এতে Euler circuit থাকে যদি এবং কেবল যদি প্রতিটি vertex-এর ডিগ্রি জোড় হয়।
এতে (circuit নয় এমন) Euler path থাকে যদি এবং কেবল যদি ঠিক দুটি vertex-এর ডিগ্রি বিজোড় হয় (path এই দুটি বিজোড়-ডিগ্রি vertex-এই শুরু ও শেষ হবে)।

অন্তর্দৃষ্টি: প্রতিবার একটি Euler path কোনো vertex দিয়ে "পাস" করলে (শুরু বা শেষ vertex ছাড়া), সেটি একটি edge দিয়ে ঢোকে ও আরেকটি edge দিয়ে বের হয় — অর্থাৎ সেই vertex-এর ডিগ্রিতে জোড়া জোড়া edge ব্যবহৃত হয়, তাই সেই vertex-এর ডিগ্রি জোড় হতে হবে। শুধু শুরু ও শেষ vertex-এর ডিগ্রি বিজোড় হতে পারে (যদি তারা একই vertex না হয়)।

২ · কোনিগসবার্গের সাতটি সেতু — গ্রাফ থিওরির জন্ম

১৭৩৬ সালে গণিতবিদ Leonhard Euler একটি জনপ্রিয় ধাঁধা সমাধান করেন যা তখনকার প্রুশিয়ার কোনিগসবার্গ শহরে (বর্তমান কালিনিনগ্রাদ) ছড়িয়ে ছিল — শহরের চারটি ভূখণ্ড (দুই নদীতীর ও দুটি দ্বীপ) সাতটি সেতু দিয়ে সংযুক্ত ছিল, আর প্রশ্ন ছিল: কি প্রতিটি সেতু ঠিক একবার পার হয়ে সম্পূর্ণ শহর ঘোরা সম্ভব?

Euler প্রতিটি ভূখণ্ডকে একটি vertex এবং প্রতিটি সেতুকে একটি edge হিসেবে মডেল করে দেখান যে চারটি ভূখণ্ডের ডিগ্রি ছিল 3, 3, 3, 5 — চারটিই বিজোড়! Euler's theorem অনুযায়ী Euler path থাকতে হলে ঠিক দুটি vertex-এর ডিগ্রি বিজোড় হতে হবে — কিন্তু এখানে চারটিই বিজোড়, তাই এমন কোনো path সম্ভবই ছিল না। এই সমাধানকেই সাধারণত গ্রাফ থিওরির প্রথম আনুষ্ঠানিক ফলাফল হিসেবে গণ্য করা হয়।

Python

def euler_check(edges, vertices):
    degree = {v: 0 for v in vertices}
    for u, v in edges:
        degree[u] += 1
        degree[v] += 1
    odd_vertices = [v for v in vertices if degree[v] % 2 != 0]
    return degree, odd_vertices

# গ্রাফ ১: একটি সাধারণ 4-চক্র (cycle) — A-B-C-D-A
edges1 = [("A", "B"), ("B", "C"), ("C", "D"), ("D", "A")]
vertices1 = ["A", "B", "C", "D"]
degrees1, odd1 = euler_check(edges1, vertices1)
print("গ্রাফ ১ ডিগ্রি:", degrees1, "| বিজোড়-ডিগ্রি vertex:", odd1)
print("Euler circuit সম্ভব (সব ডিগ্রি জোড়)?", len(odd1) == 0)

# গ্রাফ ২: কোনিগসবার্গের সাতটি সেতু (A,B = নদীতীর; C,D = দ্বীপ)
edges2 = [("A", "C"), ("A", "C"), ("B", "C"), ("B", "C"),
          ("A", "D"), ("B", "D"), ("C", "D")]
vertices2 = ["A", "B", "C", "D"]
degrees2, odd2 = euler_check(edges2, vertices2)
print("কোনিগসবার্গ গ্রাফের ডিগ্রি:", degrees2, "| বিজোড়-ডিগ্রি vertex:", odd2)
print("Euler circuit সম্ভব?", len(odd2) == 0, "| Euler path সম্ভব?", len(odd2) == 2)

লক্ষ্য করুন — কোনিগসবার্গের গ্রাফে ৪টি vertex-ই বিজোড়-ডিগ্রি (odd2-এর length 4), যা ০ (circuit) বা ২ (path)-এর কোনোটির সমান নয় — তাই কোডটি দুটোই False প্রিন্ট করবে, ঠিক Euler-এর ১৭৩৬ সালের সিদ্ধান্তের সাথে মিলিয়ে।

৩ · Hamiltonian Path ও Circuit

Euler path যেখানে প্রতিটি edge একবার ব্যবহৃত হয়, সেখানে একটি Hamiltonian pathHamiltonian Pathএকটি গ্রাফের এমন একটি path যা গ্রাফের প্রতিটি vertex ঠিক একবার ভ্রমণ করে (edge নয়, vertex গণনা করা হয়)। প্রতিটি vertex ঠিক একবার ভ্রমণ করে। যদি এই path শুরুর vertex-এই ফিরে আসে, তাকে বলা হয় Hamiltonian circuit।

কেন Hamiltonian path কঠিনতর সমস্যা

Euler's theorem আমাদের একটি সহজ, দ্রুত-পরীক্ষাযোগ্য শর্ত দেয় (শুধু ডিগ্রি গুনলেই চলে)। কিন্তু কোনো গ্রাফে Hamiltonian path আছে কিনা তা নির্ণয়ের জন্য এমন কোনো সহজ প্রয়োজনীয়-ও-যথেষ্ট শর্ত জানা নেই। সাধারণভাবে এই সমস্যাটি NP-complete — অর্থাৎ এটি সমাধানের কোনো known দ্রুত (polynomial-time) অ্যালগরিদম নেই। এই ধারণাটি আমরা M8/L42-এ P বনাম NP আলোচনায় বিস্তারিতভাবে দেখব।

ভাবনার প্রশ্ন

প্রতিটি প্রশ্ন নিজে কিছুক্ষণ ভাবুন — তারপর "→ উত্তর" চাপুন।

প্র ০১ কোনিগসবার্গের গ্রাফে যদি একটি সেতু সরিয়ে ফেলা হতো (মোট ৬টি সেতু), তাহলে কি Euler path সম্ভব হতো?

এটি নির্ভর করে কোন সেতু সরানো হচ্ছে তার উপর। ধরুন C-D সেতুটি সরানো হলো (edges2 থেকে ("C","D") বাদ)। নতুন ডিগ্রি হবে: A=3, B=3, C=4, D=2। এখন বিজোড়-ডিগ্রি vertex মাত্র দুটি (A ও B) — তাই Euler's theorem অনুযায়ী এখন একটি Euler path সম্ভব, যা A থেকে শুরু করে B-তে শেষ হবে (অথবা উল্টো)। এটি দেখায় Euler's theorem একটি গঠনমূলক (constructive না হলেও) নির্ণায়ক শর্ত — একটি edge বদলালে যোগ্যতা বদলে যেতে পারে।

প্র ০২ একটি গ্রাফ কি একইসাথে Euler circuit এবং Hamiltonian circuit — দুটোই থাকতে পারে?

হ্যাঁ, সম্পূর্ণ সম্ভব — এই দুই ধারণা স্বাধীন (independent)। উদাহরণ — cycle graph $C_n$ (L18)-এ প্রতিটি vertex-এর ডিগ্রি ঠিক ২ (জোড়), তাই Euler circuit আছে; আবার $C_n$-এর সংজ্ঞা অনুযায়ীই এটি প্রতিটি vertex ঠিক একবার ভ্রমণ করে শুরুতে ফিরে আসে, তাই এটি নিজেই একটি Hamiltonian circuit। তবে সাধারণভাবে একটি গ্রাফে একটি থাকলেই আরেকটি থাকবে — এমন কোনো নিশ্চয়তা নেই; কোনিগসবার্গের গ্রাফে যেমন কোনোটিই ছিল না।

প্র ০৩ Euler path-এর জন্য "ডিগ্রি গুনলেই চলে" এমন সহজ শর্ত থাকা সত্ত্বেও Hamiltonian path-এর জন্য কেন এত কঠিন?

Euler path-এর ক্ষেত্রে প্রতিটি vertex-এ "ঢোকা-বের হওয়া" জোড়ার হিসাব স্থানীয় (local) — প্রতিটি vertex-এর ডিগ্রি স্বাধীনভাবে পরীক্ষা করলেই সিদ্ধান্ত নেওয়া যায়, তাই এটি দ্রুত ($O(V)$) যাচাইযোগ্য। কিন্তু Hamiltonian path-এর প্রশ্নটি মূলত বৈশ্বিক (global) — পুরো গ্রাফ জুড়ে এমন একটি নির্দিষ্ট ক্রম আছে কিনা যা প্রতিটি vertex ঠিক একবার স্পর্শ করে, যা স্থানীয় তথ্য (শুধু ডিগ্রি) দিয়ে নিশ্চিত করা যায় না। এই কারণেই এটি NP-complete শ্রেণির সমস্যা।

অনুশীলন

হাতে করুন: একটি গ্রাফে vertex {P, Q, R, S} এবং edge {P-Q, Q-R, R-S, S-P, P-R} আছে (L18-এর অনুশীলন থেকে)। ডিগ্রি হিসাব করে বলুন এতে Euler circuit, Euler path, নাকি কোনোটিই সম্ভব নয়।

ডিগ্রি: $\deg(P)=3$, $\deg(Q)=2$, $\deg(R)=3$, $\deg(S)=2$। বিজোড়-ডিগ্রি vertex ঠিক দুটি (P ও R)। তাই Euler circuit সম্ভব নয়, কিন্তু Euler path সম্ভব — যা P থেকে শুরু করে R-তে শেষ হবে (অথবা R থেকে P-তে)।
পরীক্ষা করুন: উপরের কোড সেলে edges1-এ একটি নতুন edge ("A", "C") যোগ করুন (এখন A-B-C-D-A চক্রের সাথে একটি তির্যক (diagonal) সংযোগ)। নতুন ডিগ্রি কী হবে, এবং Euler circuit এখনো সম্ভব কিনা অনুমান করে তারপর Run চেপে মিলিয়ে দেখুন।

নতুন ডিগ্রি: A=3 (B, D, C), B=2 (A, C), C=3 (B, D, A), D=2 (C, A)। এখন A ও C বিজোড়-ডিগ্রি (দুটি), তাই Euler circuit আর সম্ভব নয় (কারণ সব vertex জোড় নয়), কিন্তু Euler path এখনো সম্ভব (ঠিক দুটি বিজোড়-ডিগ্রি vertex থাকায়) — A থেকে শুরু করে C-তে শেষ হবে বা উল্টো।