গ্রাফ — উপস্থাপন আর পরিভাষা

১ · গ্রাফ সবখানে — রাস্তা, বন্ধুত্ব, লিংক আর টাকা

ধরুন আপনি মিরপুর ১০ থেকে মতিঝিল যাবেন। Google Maps খুললে সে কয়েক সেকেন্ডে একটি পথ দেখায় — কোন মোড়ে বাঁয়ে, কোন রাস্তা একমুখী, কোথায় জ্যাম। মানচিত্রের পেছনে কম্পিউটার যা দেখে, তা কোনো ছবি নয়: দেখে কিছু মোড় আর মোড়গুলোর মধ্যে কিছু রাস্তা, প্রতিটি রাস্তার সাথে একটি সংখ্যা (দূরত্ব বা সময়)। রাস্তার রং, দোকানের সাইনবোর্ড, ফুটপাতের চায়ের দোকান — কিছুই লাগে না। শুধু “কে কার সাথে যুক্ত” — এই তথ্যটুকু রেখে বাকি সব ফেলে দেওয়া কাঠামোটির নাম graph (গ্রাফ)।

আনুষ্ঠানিক সংজ্ঞা: একটি গ্রাফ G = (V, E), যেখানে V হলো vertex-এর (বিন্দু বা node) একটি সেট আর E হলো edge-এর (সংযোগ) একটি সেট; প্রতিটি edge দুটি vertex-কে জোড়ে। এই কোর্সে n = |V| (vertex-এর সংখ্যা) আর m = |E| (edge-এর সংখ্যা) — বইয়ে কখনো V আর E সরাসরি সংখ্যা হিসেবেও লেখা হয়, যেমন O(V + E). একটি edge u আর v-কে জুড়লে আমরা বলি u আর v adjacent (পাশাপাশি), আর v হলো u-এর একজন প্রতিবেশী (neighbour).

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

“সবচেয়ে ছোট পথ”-এর একটি অ্যালগরিদম একবার শিখলে সেটি রাস্তায়, ইন্টারনেটের রাউটারে, এমনকি ধাঁধার সমাধানে — সবখানে চলে। মডিউল ৬-এর বাকি নয়টি পর্ব এমন অ্যালগরিদমে ভরা; এই পর্ব তাদের জন্য ভাষা আর ডেটা স্ট্রাকচার তৈরি করে। আপনি এর মধ্যেই দুটি বিশেষ গ্রাফ দেখেছেন: পর্ব ২৬-এর tree আর পর্ব ৩৩-এর DSU-র forest. আজ দেখব সেগুলো বড় পরিবারের কোন জায়গায় বসে।

২ · গ্রাফের প্রকারভেদ — দিক, ওজন, loop আর একাধিক edge

Undirected graph-এ edge লেখা হয় {u, v} — একটি অক্রমিক জোড়া। Directed graph-এ (সংক্ষেপে digraph) edge (u, v) একটি ক্রমিক জোড়া: u হলো লেজ (tail), v হলো মাথা (head), আর আঁকা হয় তীর দিয়ে u → v. ঢাকার অনেক একমুখী রাস্তা directed edge, আর দুমুখী রাস্তা মানে দুটি উল্টো directed edge. প্রতিটি undirected গ্রাফকে এভাবে directed হিসেবে দেখা যায় — {u, v}-এর জায়গায় u → v আর v → u; কোডেও ঠিক এটিই করা হয়।

Weighted graph-এ প্রতিটি edge-এর একটি ওজন (weight) থাকে। ওজন ঋণাত্মকও হতে পারে — যেমন কোনো রাস্তায় গেলে জ্বালানি-ভর্তুকি পাওয়া যায়, বা মুদ্রা-বিনিময়ে লাভ — আর তখন কিছু অ্যালগরিদম (Dijkstra) আর চলে না; সেই গল্প পর্ব ৪৩–৪৪-এ।

এখন দুটি বিশেষ জিনিস। Self-loop হলো একটি vertex থেকে নিজের দিকেই একটি edge, যেমন (v, v). আর parallel edge (multi-edge) মানে একই দুই vertex-এর মধ্যে একাধিক edge — যেমন একই দিনে আপনি মা-কে তিনবার bKash করলেন। এ দুটির কোনোটিই না থাকলে গ্রাফটি একটি simple graph; থাকতে পারলে multigraph. বইয়ের বেশিরভাগ উপপাদ্য simple graph ধরে নেয়, কিন্তু কনটেস্টের ইনপুটে প্রায়ই লেখা থাকে “there may be multiple edges and self-loops” — সমস্যার বিবরণ খুঁটিয়ে না পড়লে এখানেই অনেকে ভুল করেন।

কতগুলো edge থাকতে পারে?

n টি vertex-এর simple undirected গ্রাফে প্রতিটি জোড়া {u, v}-এর মধ্যে সর্বোচ্চ একটি edge. জোড়ার সংখ্যা ⁿC₂ = n(n − 1)/2. তাই 0 ≤ m ≤ n(n − 1)/2. Simple directed গ্রাফে প্রতিটি ক্রমিক জোড়া (u, v), u ≠ v, আলাদা — সর্বোচ্চ n(n − 1) টি edge. Multigraph-এ কোনো ওপরের সীমা নেই। ১,০০০ জন মানুষের মধ্যে সর্বোচ্চ বন্ধুত্ব 1000 × 999 / 2 = 4,99,500 টি — এই সংখ্যাটি অংশ ৪-এ dense আর sparse গ্রাফের পার্থক্য বুঝতে লাগবে।

৩ · Degree আর handshake lemma — প্রতিটি edge দুবার গোনা হয়

Undirected গ্রাফে একটি vertex v-এর degree, deg(v), হলো v-কে ছোঁয়া edge-এর সংখ্যা — অর্থাৎ v-এর প্রতিবেশী কয়জন (simple graph-এ)। ফেসবুকে আপনার degree মানে আপনার বন্ধু-সংখ্যা। Self-loop থাকলে নিয়ম: একটি loop degree-তে ২ যোগ করে, কারণ তার দুটি প্রান্তই v-তে। (পর্ব ২৬-এ rooted tree-তে “degree” বলতে শুধু সন্তানের সংখ্যা বোঝানো হয়েছিল — গ্রাফে degree মানে সব edge, parent-এর edge-সহ।)

Directed গ্রাফে দুটি আলাদা সংখ্যা: out-degree, deg⁺(v) — v থেকে বেরিয়ে যাওয়া edge, আর in-degree, deg⁻(v) — v-তে ঢোকা edge. Prerequisite গ্রাফে in-degree ০-এর কোর্সের কোনো পূর্বশর্ত নেই — সেগুলো দিয়েই শুরু করা যায় (পর্ব ৪২-এর topological sort এখান থেকেই শুরু)।

এবার এই পর্বের প্রথম উপপাদ্য। চারজন বন্ধু — রহিম (1), করিম (2), সেলিনা (3) আর দীপা (4) — একে একে ফেসবুকে বন্ধু হচ্ছেন। প্রতিটি নতুন বন্ধুত্বের পর degree-র যোগফল দেখুন:

প্রমাণ — handshake lemma

উপপাদ্য (handshake lemma): যেকোনো undirected গ্রাফে (multigraph আর self-loop-সহ) Σ_{v ∈ V} deg(v) = 2m.

প্রমাণ (দুইভাবে গোনা): সব (vertex, edge-এর প্রান্ত) জোড়া গুনুন — অর্থাৎ “কোন edge-এর কোন প্রান্ত কোন vertex-এ বসে আছে”. Vertex ধরে গুনলে প্রতিটি v-তে ঠিক deg(v) টি প্রান্ত, মোট Σ deg(v). Edge ধরে গুনলে প্রতিটি edge-এর ঠিক দুটি প্রান্ত (self-loop-এর দুটিই একই vertex-এ — সেজন্যই loop degree-তে ২ যোগ করে), মোট 2m. একই জিনিস দুইভাবে গোনা হয়েছে, তাই দুটি সমান। ∎ (Induction-এও করা যায়, ওপরের ডায়াগ্রামের মতো: খালি গ্রাফে 0 = 0, আর প্রতিটি নতুন edge দুই পাশে ঠিক ২ যোগ করে।)

অনুসিদ্ধান্ত: বিজোড় degree-র vertex-এর সংখ্যা সবসময় জোড়। কারণ Σ deg(v) জোড় (2m); জোড় degree-গুলোর যোগফল জোড়; তাই বাকি বিজোড় degree-গুলোর যোগফলও জোড় — আর কয়েকটি বিজোড় সংখ্যার যোগফল জোড় হয় কেবল তখন, যখন তাদের সংখ্যা জোড়। নাম “handshake” এই অনুসিদ্ধান্ত থেকে: একটি অনুষ্ঠানে যতজন বিজোড় সংখ্যক মানুষের সাথে হাত মিলিয়েছেন, তাঁদের সংখ্যা সবসময় জোড়।

একটি দ্রুত প্রয়োগ: ৭ জন মানুষের একটি দলে কি প্রত্যেকে ঠিক ৩ জনের সাথে বন্ধু হতে পারেন? Degree-র যোগফল হতো 7 × 3 = 21 — বিজোড়, অথচ 2m সবসময় জোড়। তাই অসম্ভব — কোনো গ্রাফ না এঁকেই প্রমাণ। বিশ্ববিদ্যালয়, চাকরি বা ইন্টারভিউর পরীক্ষায় এমন প্রশ্ন প্রায়ই আসে।

৪ · পথ, cycle, সংযোগ আর বিশেষ গ্রাফের পরিবার

Walk, path আর cycle

একটি walk হলো vertex-এর একটি ক্রম v₀, v₁, …, v_k, যেখানে পরপর প্রতিটি জোড়ার মধ্যে একটি edge আছে; দৈর্ঘ্য k (edge-এর সংখ্যা)। Walk-এ vertex বা edge বারবার আসতে পারে। কোনো vertex বারবার না এলে সেটি একটি simple path; অনেক বইয়ে শুধু “path” বলতে এটিকেই বোঝানো হয়। যেকোনো walk থেকে মাঝের ঘোরাঘুরি কেটে একটি path পাওয়া যায়, তাই “u থেকে v-তে যাওয়া যায় কি না” প্রশ্নে দুটির পার্থক্য নেই।

একটি cycle হলো দৈর্ঘ্য ≥ 1-এর এমন একটি বন্ধ walk, যার শুরু আর শেষ একই vertex, আর এর বাইরে কোনো vertex বা edge পুনরাবৃত্ত হয় না। Simple undirected গ্রাফে cycle-এর দৈর্ঘ্য অন্তত ৩ (u–v–u একই edge দুবার, তাই cycle নয়); directed গ্রাফে u → v → u দৈর্ঘ্য ২-এর বৈধ cycle. bKash-এ A → B → C → A ধাঁচের টাকার চক্র জালিয়াতি ধরার কাজে খোঁজা হয় — এটি directed cycle খোঁজা (পর্ব ৪১)।

সংযোগ আর component

Undirected গ্রাফে যেকোনো দুটি vertex-এর মধ্যে path থাকলে গ্রাফটি connected. না থাকলে গ্রাফটি কয়েকটি টুকরোয় ভাগ হয় — প্রতিটি টুকরো একটি connected component: সবচেয়ে বড় এমন vertex-এর দল, যার ভেতরে সবাই সবার কাছে পৌঁছাতে পারে। “u থেকে v-তে যাওয়া যায়” সম্পর্কটি reflexive, symmetric আর transitive — একটি equivalence relation; component-গুলো তার শ্রেণি, ঠিক যেমন পর্ব ৩৩-এ DSU-র দলগুলো ছিল।

Directed গ্রাফে ব্যাপারটি সূক্ষ্ম, কারণ u থেকে v-তে যাওয়া গেলেও v থেকে u-তে না-ও যাওয়া যেতে পারে। যদি প্রতিটি জোড়া u, v-এর জন্য u ⇝ v আর v ⇝ u দুই দিকেই path থাকে, গ্রাফটি strongly connected. দিক উপেক্ষা করলে যদি connected হয়, তবে weakly connected. যেকোনো directed গ্রাফ তার strongly connected component (SCC)-গুলোতে ভাগ হয়, আর প্রতিটি SCC-কে একটি বিন্দুতে সংকুচিত করলে যা থাকে, তাতে কোনো cycle নেই। SCC বের করার O(n + m) অ্যালগরিদম (Tarjan, Kosaraju) পর্ব ৪৬-এ।

Tree — cycle নেই, তবু সবাই যুক্ত

গ্রাফের ভাষায় একটি tree হলো connected আর acyclic (cycle-হীন) undirected গ্রাফ. পর্ব ২৬-এর rooted tree এরই একটি রূপ — যেকোনো একটি vertex-কে root বেছে নিলে বাকিদের parent-সন্তান সম্পর্ক আপনা থেকে ঠিক হয়ে যায়। Cycle-হীন কিন্তু হয়তো বিচ্ছিন্ন গ্রাফ হলো forest — কয়েকটি tree. এবার tree-র সবচেয়ে বিখ্যাত বৈশিষ্ট্যটি প্রমাণ করি।

উপপাদ্য: n টি vertex-এর যেকোনো tree-তে ঠিক n − 1 টি edge.

প্রমাণ (edge একে একে যোগ করে): n টি vertex, কোনো edge নেই — n টি component দিয়ে শুরু করুন, তারপর tree-র edge-গুলো যেকোনো ক্রমে একে একে যোগ করুন। প্রতিটি edge {u, v} যোগের সময় দুটি সম্ভাবনা: (ক) u আর v আগে থেকেই একই component-এ — তাহলে তাদের মধ্যে আগেই একটি path ছিল, নতুন edge-টি তার সাথে মিলে একটি cycle বানায়; (খ) আলাদা component-এ — তাহলে দুই component জুড়ে একটি হয়, component-এর সংখ্যা ঠিক ১ কমে। Tree-তে cycle নেই, তাই প্রতিটি edge (খ) ধরনের। শেষে tree connected, অর্থাৎ ১টি component. n থেকে ১-এ নামতে ঠিক n − 1 বার কমাতে হয় — তাই edge ঠিক n − 1 টি। ∎ এই যুক্তিটি আসলে পর্ব ৩৩-এর DSU-র cycle detection, আর পর্ব ৪৫-এর Kruskal-এর ভিত্তি।

একই যুক্তি থেকে একটি শক্তিশালী ফল: n টি vertex-এর undirected গ্রাফের জন্য (১) connected, (২) acyclic, (৩) ঠিক n − 1 টি edge — এই তিনটির যেকোনো দুটি সত্য হলে তৃতীয়টিও সত্য। কনটেস্টে “n টি শহর, n − 1 টি রাস্তা, সব শহর যুক্ত” দেখলেই বুঝবেন গ্রাফটি একটি tree (পর্ব ৪৮-এর কৌশল কাজে লাগবে)।

DAG, bipartite আর complete গ্রাফ

DAG (directed acyclic graph) হলো কোনো directed cycle নেই এমন directed গ্রাফ। কোর্সের prerequisite-এর গ্রাফ DAG হতেই হবে: “C++ পড়তে C লাগবে, C পড়তে C++ লাগবে” — এমন চক্র থাকলে কেউ কোনোদিন শুরুই করতে পারবেন না। প্রতিটি DAG-এর vertex-গুলোকে এমন এক সারিতে সাজানো যায়, যাতে প্রতিটি edge বাঁ থেকে ডানে যায় — topological sort (পর্ব ৪২)। Spreadsheet-এর ফর্মুলা বা build-এর ক্রমও DAG.

Bipartite graph-এর vertex-গুলো দুটি দলে ভাগ করা যায়, যাতে প্রতিটি edge এক দলের সাথে অন্য দলকে জোড়ে, দলের ভেতরে কোনো edge নেই। চাকরিপ্রার্থী আর পদ, রাইডার আর যাত্রী — দুই ধরনের জিনিসের সম্পর্ক স্বভাবতই bipartite. একটি সুন্দর উপপাদ্য, যা Dénes Kőnig-এর ১৯৩৬ সালের বইয়ে প্রমাণসহ আছে: একটি গ্রাফ bipartite হবে ঠিক তখনই, যখন তাতে কোনো বিজোড় দৈর্ঘ্যের cycle নেই। BFS দিয়ে দুই রঙে রাঙিয়ে এটি O(n + m)-এ যাচাই করা যায় (পর্ব ৪০), আর bipartite matching পর্ব ৪৭-এ।

Complete graph K_n-এ প্রতিটি জোড়া vertex-এর মধ্যে edge আছে: m = n(n − 1)/2, প্রত্যেকের degree n − 1. ১০টি দলের round-robin লিগের ম্যাচ-গ্রাফ K₁₀, 45টি ম্যাচ। আর K_m,n হলো complete bipartite: m জনের এক দল আর n জনের অন্য দলের প্রত্যেকে প্রত্যেকের সাথে যুক্ত, m·n টি edge.

Dense আর sparse — m কি n²-এর কাছাকাছি?

m সর্বোচ্চ প্রায় n²/2. যে গ্রাফে m প্রায় n²-এর ক্রমে (m = Θ(n²)), তা dense; যে গ্রাফে m অনেক কম — সাধারণত O(n) বা O(n log n) — তা sparse. বাস্তবের প্রায় সব বড় গ্রাফ খুব sparse: ঢাকার একটি মোড়ে সাধারণত ৩–৫টি রাস্তা এসে মেলে, n যত বড়ই হোক। ফেসবুকে কোটি কোটি মানুষ, কিন্তু একজনের বন্ধু সর্বোচ্চ ৫,০০০ — তাই m ≤ 2500n, যা n²/2-এর চেয়ে লাখো গুণ কম। অন্যদিকে “প্রতিটি শহর-জোড়ার সরাসরি দূরত্ব” dense, প্রায় complete.

৫ · গ্রাফ মেমরিতে রাখা — matrix, list, edge list আর CSR

কাগজের ছবি কম্পিউটারে চলে না; গ্রাফ রাখতে হয় অ্যারে বা list-এ। চারটি প্রচলিত উপায় আছে, আর প্রতিটি ভিন্ন প্রশ্নে দ্রুত। নিচের ডায়াগ্রামে একটি ছোট directed weighted গ্রাফ — চারটি bKash অ্যাকাউন্ট (1 = আপনি, 2 = মা, 3 = দোকানদার, 4 = ছোট ভাই) আর চারটি লেনদেন — একই সাথে দুটি উপস্থাপনে তৈরি হচ্ছে।

Adjacency matrix

Adjacency matrix একটি n × n অ্যারে A, যেখানে A[u][v] = 1 (বা ওজন) যদি u → v edge থাকে, নইলে 0 (বা ∞, বা একটি “নেই” চিহ্ন)। Undirected গ্রাফে A প্রতিসম (symmetric): A[u][v] = A[v][u]. Multigraph-এ ঘরে edge-এর সংখ্যা রাখা যায় — পরের অংশের কোডে Königsberg ঠিক এভাবেই রাখা হয়েছে। সুবিধা: “u আর v-এর মধ্যে edge আছে?” — এক ঘর পড়া, O(1). অসুবিধা: জায়গা সবসময় Θ(n²), আর u-এর প্রতিবেশী খুঁজতে পুরো সারি, Θ(n) — u-এর মাত্র ২ জন প্রতিবেশী থাকলেও।

Adjacency list

Adjacency list-এ প্রতিটি vertex u-এর জন্য তার প্রতিবেশীদের একটি তালিকা adj[u] — C++-এ vector<vector<int>>, ওজনসহ হলে vector<vector<pair<int,int>>>; Python-এ list-এর list. মোট জায়গা Θ(n + m): n টি তালিকা আর handshake lemma অনুযায়ী মোট 2m (undirected) বা m (directed) টি এন্ট্রি। u-এর প্রতিবেশী ঘোরা Θ(deg(u)) — ঠিক যতটুকু দরকার। কিন্তু “u–v edge আছে?” প্রশ্নে adj[u] খুঁজতে হয়, O(deg(u)); তালিকা সর্ট করা থাকলে binary search-এ O(log deg(u)), বা প্রতিটি vertex-এ একটি hash set রাখলে গড়ে O(1). BFS, DFS, Dijkstra — এই মডিউলের প্রায় সব অ্যালগরিদম adjacency list-এ লেখা হয়।

Edge list

Edge list সবচেয়ে সরল: শুধু m টি (u, v) বা (u, v, w)-এর একটি অ্যারে — ইনপুট ঠিক যেভাবে আসে। জায়গা Θ(m). কোনো vertex-এর প্রতিবেশী খুঁজতে পুরো তালিকা, O(m) — তাই BFS-এর জন্য অচল। কিন্তু যে অ্যালগরিদম edge-গুলোকে একসাথে দেখে, তার জন্য এটিই সেরা: Kruskal ওজন অনুযায়ী edge সর্ট করে (পর্ব ৪৫), Bellman-Ford প্রতি ধাপে সব edge ঘোরে (পর্ব ৪৪)।

CSR — দুটি অ্যারেতে পুরো গ্রাফ

CSR (compressed sparse row) হলো adjacency list-এর “জমাট” রূপ। সব তালিকা পরপর জোড়া দিয়ে একটি অ্যারে to (দৈর্ঘ্য m, undirected হলে 2m), আর একটি অ্যারে start (দৈর্ঘ্য n + 1): u-এর প্রতিবেশীরা to[start[u]] থেকে to[start[u+1] − 1] পর্যন্ত। বানানো যায় দুই পাসে — প্রথমে out-degree গুনে prefix sum (পর্ব ১৭) দিয়ে start, তারপর প্রতিটি edge তার জায়গায় বসানো, ঠিক counting sort-এর মতো (পর্ব ২৪)।

Pseudocode — build CSR from a directed edge list (vertices 1..n)

start[1..n+1] = 0
for each edge (u, v):  start[u+1] += 1        // count out-degree of u
for u = 1 to n:        start[u+1] += start[u] // prefix sums: start[u] = first slot of u
pos = copy of start
for each edge (u, v):  to[pos[u]] = v;  pos[u] += 1
// neighbours of u: to[start[u]] .. to[start[u+1] - 1]

লাভ: মাত্র দুটি অ্যারে, আলাদা আলাদা vector-এর বাড়তি খরচ নেই, আর সব প্রতিবেশী মেমরিতে পাশাপাশি — cache locality চমৎকার। অসুবিধা: পরে edge যোগ করতে পুরো কাঠামো আবার বানাতে হয়, তাই CSR স্থির (static) গ্রাফের জন্য।

খরচের তুলনা

সংখ্যায় দেখুন। কনটেস্টে সাধারণ সীমা n = 2 × 10⁵, m = 2 × 10⁵. Matrix-এ 4 × 10¹⁰ টি ঘর — int-এ ১৬০ GB, এক bit করে রাখলেও ৫ GB; মেমরি সীমা সাধারণত ২৫৬ MB. Adjacency list-এ মোটামুটি n টি vector আর 2m = 4 × 10⁵ টি int — কয়েক MB মাত্র। তাই নিয়মটি সহজ: ডিফল্ট adjacency list; n কয়েক হাজারের মধ্যে আর বারবার “edge আছে?” জিজ্ঞেস করতে হলে matrix; edge সর্ট করতে হলে edge list.

৬ · Königsberg-এর সাত সেতু — Euler path-এর শর্ত

অষ্টাদশ শতকের প্রুশিয়ার শহর Königsberg (আজকের রাশিয়ার Kaliningrad) Pregel নদীর দুই পাড়ে, আর নদীর মাঝে দুটি দ্বীপ। দুই পাড় আর দুই দ্বীপ — এই চারটি স্থলভাগকে জুড়েছিল সাতটি সেতু। শহরবাসীর মধ্যে একটি ধাঁধা চালু ছিল: এমনভাবে হাঁটা যায় কি, যাতে প্রতিটি সেতু ঠিক একবার পার হতে হয়? কেউ পারেননি, আবার অসম্ভব বলে প্রমাণও করেননি।

তখন St. Petersburg-এর বিজ্ঞান একাডেমিতে কাজ করা Leonhard Euler সমস্যাটি নিয়ে ভাবলেন, আর ১৭৩৬ সালের বলে পরিচিত একটি প্রবন্ধে উত্তর দিলেন — এটিকেই গ্রাফ তত্ত্বের জন্ম ধরা হয়। তাঁর মূল চাল ছিল বিমূর্ত করা: গুরুত্বপূর্ণ শুধু কোন স্থলভাগ কোনটির সাথে কয়টি সেতুতে যুক্ত। আজকের ভাষায়: চারটি vertex (উত্তর পাড়, দক্ষিণ পাড়, Kneiphof দ্বীপ, পূর্বের দ্বীপ) আর সাতটি edge — একটি multigraph, কারণ Kneiphof-এর সাথে উত্তর পাড়ের দুটি আর দক্ষিণ পাড়ের দুটি সেতু ছিল। Degree: Kneiphof ৫, বাকি তিনটি স্থলভাগ ৩ করে।

এখন সংজ্ঞা। একটি Euler path (Eulerian trail) হলো এমন একটি walk, যা গ্রাফের প্রতিটি edge ঠিক একবার ব্যবহার করে (vertex বারবার আসতে পারে)। শুরু আর শেষ একই vertex হলে সেটি Euler circuit.

কেন বিজোড় vertex ২-এর বেশি হলে অসম্ভব (প্রয়োজনীয়তার প্রমাণ): ধরুন একটি Euler path আছে। হাঁটার সময় শুরু বা শেষ নয় এমন একটি vertex v-তে আপনি যতবার ঢোকেন, ততবারই বেরোন — প্রতিবার একটি edge দিয়ে ঢোকা, আরেকটি দিয়ে বেরোনো। প্রতিটি edge ঠিক একবার ব্যবহার হয়, তাই v-এর edge-গুলো ঢোকা-বেরোনোর জোড়ায় ভাগ হয়ে যায়: deg(v) জোড়। শুধু শুরুর vertex-এ একটি “বাড়তি” বেরোনো আর শেষের vertex-এ একটি “বাড়তি” ঢোকা আছে। তাই বিজোড় degree থাকতে পারে কেবল শুরু আর শেষে — সর্বোচ্চ ২টি; আর শুরু = শেষ হলে (circuit) একটিও নয়। Königsberg-এ চারটি স্থলভাগেরই degree বিজোড় — তাই ধাঁধাটির কোনো সমাধান নেই। ∎ (Handshake-এর অনুসিদ্ধান্তে বিজোড় vertex কখনো ১টি হয় না।)

উল্টো দিক (যথেষ্টতা): শর্ত পূরণ হলেই পথ আছে — এটি Euler সম্ভবত জানতেন, কিন্তু সম্পূর্ণ প্রমাণ প্রকাশ হয় অনেক পরে, Carl Hierholzer-এর মৃত্যুর পর ১৮৭৩ সালে। তাঁর গঠনমূলক যুক্তিটিই আজকের Hierholzer-এর অ্যালগরিদম: সব degree জোড় হলে একটি vertex থেকে অব্যবহৃত edge ধরে হাঁটতে থাকুন — আটকে যাবেন কেবল শুরুর vertex-এ ফিরে (অন্য যেকোনো vertex-এ ঢুকলে জোড় degree-র কারণে বেরোনোর একটি edge বাকি থাকে)। কোনো edge বাকি থাকলে চক্রের একটি vertex থেকে আরেকটি চক্র বানিয়ে প্রথমটির ভেতরে জুড়ে দিন। প্রতিটি edge একবার দেখা হয়, তাই সময় O(n + m). ঠিক ২টি বিজোড় vertex থাকলে তাদের মধ্যে একটি কাল্পনিক edge যোগ করে circuit বানান, তারপর সেটি কেটে ফেলুন — পাওয়া যায় এক বিজোড় vertex থেকে অন্যটিতে Euler path.

নিচের ছবিটি জার্মানির শিশুদের একটি পরিচিত ধাঁধা — “Das Haus vom Nikolaus”: কলম না তুলে, কোনো দাগ দুবার না টেনে বাড়িটি আঁকুন। পাঁচটি vertex, আটটি edge (বর্গের চার বাহু, দুটি কর্ণ আর ছাদের দুটি ঢাল)।

Directed গ্রাফে শর্তটি একই যুক্তিতে: Euler circuit আছে যদি প্রতিটি vertex-এ in-degree = out-degree হয় আর edge-যুক্ত সব vertex (দিক উপেক্ষা করে) এক component-এ থাকে; Euler path আছে যদি ঠিক একটি vertex-এ out − in = 1 (শুরু), ঠিক একটিতে in − out = 1 (শেষ), আর বাকি সবখানে সমান হয় (একই connectivity শর্তসহ)। প্রয়োগ শুধু ধাঁধায় নয়: DNA sequencing-এ ছোট টুকরো জোড়া দেওয়ার একটি প্রধান পদ্ধতি (de Bruijn graph) আসলে Euler path খোঁজা।

৭ · পুরো কোড — ইনপুট পড়া, দুই উপস্থাপন, degree আর Euler-এর শর্ত

কনটেস্ট আর অনলাইন judge-এ গ্রাফ প্রায় সবসময় একই ছাঁচে আসে: প্রথম লাইনে n m, তারপর m টি লাইনে u v (ওজন থাকলে u v w), আর vertex-এর নম্বর সাধারণত 1 থেকে n — 1-based. Tree হলে প্রায়ই শুধু n আর n − 1 টি edge, বা 2…n প্রতিটি vertex-এর parent-এর একটি তালিকা।

Pseudocode — read an undirected graph (vertices 1..n)

read n, m
adj = n+1 empty lists                 // index 0 unused: vertices are 1..n
for i = 1 to m:
    read u, v
    append v to adj[u]
    append u to adj[v]                // undirected: store both directions
deg(u) = length of adj[u]

নিচের প্রোগ্রামটি দুটি গ্রাফ পড়ে — অংশ ৬-এর “নিকোলাসের বাড়ি” আর Königsberg (1 = Kneiphof দ্বীপ, 2 = উত্তর পাড়, 3 = দক্ষিণ পাড়, 4 = পূর্বের দ্বীপ)। প্রতিটির জন্য adjacency matrix আর adjacency list দুটোই বানায়, প্রতিটি vertex-এর matrix-সারি, degree আর প্রতিবেশী ছাপে, handshake lemma যাচাই করে, আর বিজোড় degree গুনে Euler path-এর রায় দেয়। ইনপুট stdin থেকে না পড়ে একটি স্থির string থেকে পড়া হয়েছে, যাতে ফল সবসময় একই থাকে; আসল কনটেস্টে istringstream-এর জায়গায় সরাসরি cin বসাবেন।

#include <iostream>
#include <sstream>
#include <string>
#include <vector>
using namespace std;
void analyse(const string& name, const string& text) {
    istringstream in(text);
    int n, m; in >> n >> m;                                  // first line: n m
    vector<vector<int>> mat(n + 1, vector<int>(n + 1, 0));   // 1-based: rows 1..n
    vector<vector<int>> adj(n + 1);
    for (int i = 0; i < m; ++i) {
        int u, v; in >> u >> v;
        mat[u][v]++; mat[v][u]++;                            // counts allow parallel edges
        adj[u].push_back(v); adj[v].push_back(u);
    }
    cout << name << ": n = " << n << ", m = " << m << '\n';
    int total = 0, odd = 0;
    for (int u = 1; u <= n; ++u) {
        int d = (int)adj[u].size();
        cout << "  " << u << " | row:";
        for (int v = 1; v <= n; ++v) cout << ' ' << mat[u][v];
        cout << " | deg " << d << " | list:";
        for (int v : adj[u]) cout << ' ' << v;
        cout << '\n';
        total += d; odd += d % 2;
    }
    cout << "  sum of degrees = " << total << ", 2m = " << 2 * m << (total == 2 * m ? " (ok)" : " (BUG)") << '\n';
    string verdict = odd == 0 ? "yes, even a closed circuit"
                   : odd == 2 ? "yes, from one odd vertex to the other" : "no";
    cout << "  odd-degree vertices: " << odd << " -> Euler path: " << verdict << '\n';
}
int main() {
    analyse("house", "5 8  1 2  2 3  3 4  4 1  1 3  2 4  3 5  4 5");
    analyse("Konigsberg", "4 7  1 2  1 2  1 3  1 3  1 4  2 4  3 4");
}

house: n = 5, m = 8
  1 | row: 0 1 1 1 0 | deg 3 | list: 2 4 3
  2 | row: 1 0 1 1 0 | deg 3 | list: 1 3 4
  3 | row: 1 1 0 1 1 | deg 4 | list: 2 4 1 5
  4 | row: 1 1 1 0 1 | deg 4 | list: 3 1 2 5
  5 | row: 0 0 1 1 0 | deg 2 | list: 3 4
  sum of degrees = 16, 2m = 16 (ok)
  odd-degree vertices: 2 -> Euler path: yes, from one odd vertex to the other
Konigsberg: n = 4, m = 7
  1 | row: 0 2 2 1 | deg 5 | list: 2 2 3 3 4
  2 | row: 2 0 0 1 | deg 3 | list: 1 1 4
  3 | row: 2 0 0 1 | deg 3 | list: 1 1 4
  4 | row: 1 1 1 0 | deg 3 | list: 1 2 3
  sum of degrees = 14, 2m = 14 (ok)
  odd-degree vertices: 4 -> Euler path: no

def analyse(name, text):
    data = iter(map(int, text.split()))
    n, m = next(data), next(data)                 # first line: n m
    mat = [[0] * (n + 1) for _ in range(n + 1)]   # 1-based: rows 1..n
    adj = [[] for _ in range(n + 1)]
    for _ in range(m):
        u, v = next(data), next(data)
        mat[u][v] += 1                            # counts allow parallel edges
        mat[v][u] += 1
        adj[u].append(v)
        adj[v].append(u)
    print(f"{name}: n = {n}, m = {m}")
    total = odd = 0
    for u in range(1, n + 1):
        d = len(adj[u])
        print(f"  {u} | row:", *mat[u][1:], f"| deg {d} | list:", *adj[u])
        total += d
        odd += d % 2
    print(f"  sum of degrees = {total}, 2m = {2 * m}", "(ok)" if total == 2 * m else "(BUG)")
    if odd == 0:
        verdict = "yes, even a closed circuit"
    elif odd == 2:
        verdict = "yes, from one odd vertex to the other"
    else:
        verdict = "no"
    print(f"  odd-degree vertices: {odd} -> Euler path: {verdict}")

analyse("house", "5 8  1 2  2 3  3 4  4 1  1 3  2 4  3 5  4 5")
analyse("Konigsberg", "4 7  1 2  1 2  1 3  1 3  1 4  2 4  3 4")

house: n = 5, m = 8
  1 | row: 0 1 1 1 0 | deg 3 | list: 2 4 3
  2 | row: 1 0 1 1 0 | deg 3 | list: 1 3 4
  3 | row: 1 1 0 1 1 | deg 4 | list: 2 4 1 5
  4 | row: 1 1 1 0 1 | deg 4 | list: 3 1 2 5
  5 | row: 0 0 1 1 0 | deg 2 | list: 3 4
  sum of degrees = 16, 2m = 16 (ok)
  odd-degree vertices: 2 -> Euler path: yes, from one odd vertex to the other
Konigsberg: n = 4, m = 7
  1 | row: 0 2 2 1 | deg 5 | list: 2 2 3 3 4
  2 | row: 2 0 0 1 | deg 3 | list: 1 1 4
  3 | row: 2 0 0 1 | deg 3 | list: 1 1 4
  4 | row: 1 1 1 0 | deg 3 | list: 1 2 3
  sum of degrees = 14, 2m = 14 (ok)
  odd-degree vertices: 4 -> Euler path: no

কনটেস্টের ইনপুটে যে ভুলগুলো সবচেয়ে বেশি হয়

• আকার n, n + 1 নয়: vertex 1…n হলে adj(n + 1) নিন, অথবা পড়ার সময়ই --u; --v; করে 0-based করে নিন — কিন্তু দুটো মিশিয়ে নয়। এটি গ্রাফ-কোডের সবচেয়ে সাধারণ off-by-one ভুল।
• উল্টো দিকের edge ভুলে যাওয়া: undirected গ্রাফে adj[v].push_back(u) না লিখলে গ্রাফটি চুপচাপ directed হয়ে যায়; ছোট পরীক্ষায় প্রায়ই উত্তর ঠিক আসে।
• একাধিক test case: প্রতিটি test-এর আগে adj খালি করুন (শুধু 1…n পর্যন্ত, পুরো সর্বোচ্চ আকার নয় — নইলে সময় যায়)।

৮ · Implicit graph — গ্রিড আর ধাঁধার অবস্থা

অনেক সমস্যায় গ্রাফটি কোথাও লেখা নেই — একটি নিয়ম থেকে প্রতিবেশী হিসাব করে বের করা হয়। একে বলে implicit graph. সবচেয়ে পরিচিত উদাহরণ grid graph: একটি R × C গোলকধাঁধা বা মানচিত্র, যেখানে প্রতিটি খোলা ঘর একটি vertex, আর পাশাপাশি দুটি খোলা ঘরের মধ্যে একটি edge. Adjacency list বানানোর দরকার নেই — ঘর (r, c)-এর প্রতিবেশী সরাসরি:

• ৪ দিকের প্রতিবেশী (ওপর, নিচ, বাঁ, ডান): (r − 1, c), (r + 1, c), (r, c − 1), (r, c + 1).
• ৮ দিকের প্রতিবেশী: ওপরের চারটি আর চারটি কোনাকুনি — দাবার রাজার চাল।
• প্রতিটি প্রার্থীর জন্য দুটি পরীক্ষা: ঘরটি গ্রিডের ভেতরে কি না (0 ≤ r < R, 0 ≤ c < C), আর দেয়াল (#) কি না। ক্রম জরুরি — আগে সীমা, পরে grid[r][c], নইলে অ্যারের বাইরে পড়বেন।
• কোনো অ্যারেতে (যেমন দূরত্ব) রাখতে হলে ঘরটিকে একটি সংখ্যা দিন: id = r · C + c, যা 0 থেকে R·C − 1; উল্টো দিকে r = id / C, c = id % C — 2D অ্যারের row-major ক্রমের মতোই।

দিকগুলো দুটি ছোট অ্যারেতে রাখলে কোড পরিষ্কার থাকে: dr = {-1, 1, 0, 0}, dc = {0, 0, -1, 1}. নিচে একটি ৩ × ৪ গ্রিডে ঘর (1, 2)-এর ৪ দিকের প্রতিবেশী খোঁজা হচ্ছে:

#include <iostream>
#include <string>
#include <utility>
#include <vector>
using namespace std;
int main() {
    vector<string> grid = {"..#.",
                           ".#..",
                           "...."};                          // '#' is a wall, '.' is open
    int R = (int)grid.size(), C = (int)grid[0].size();
    const int DR[] = {-1, 1, 0, 0}, DC[] = {0, 0, -1, 1};    // up, down, left, right
    auto is_open = [&](int r, int c) {
        return r >= 0 && r < R && c >= 0 && c < C && grid[r][c] == '.';
    };
    for (auto [r, c] : vector<pair<int, int>>{{0, 0}, {1, 2}, {2, 1}}) {
        cout << "cell (" << r << "," << c << ") id " << r * C + c << ": 4-nbrs";
        for (int k = 0; k < 4; ++k)
            if (is_open(r + DR[k], c + DC[k])) cout << " (" << r + DR[k] << "," << c + DC[k] << ")";
        int eight = 0;
        for (int dr = -1; dr <= 1; ++dr)
            for (int dc = -1; dc <= 1; ++dc)
                if ((dr != 0 || dc != 0) && is_open(r + dr, c + dc)) ++eight;
        cout << " | 8-nbrs count " << eight << '\n';
    }
    int V = 0, E = 0;
    for (int r = 0; r < R; ++r)
        for (int c = 0; c < C; ++c)
            if (is_open(r, c)) {
                ++V;
                E += is_open(r, c + 1) + is_open(r + 1, c);  // right and down: each edge once
            }
    cout << "vertices (open cells) = " << V << ", edges (4-neighbour) = " << E << '\n';
}

cell (0,0) id 0: 4-nbrs (1,0) (0,1) | 8-nbrs count 2
cell (1,2) id 6: 4-nbrs (2,2) (1,3) | 8-nbrs count 6
cell (2,1) id 9: 4-nbrs (2,0) (2,2) | 8-nbrs count 4
vertices (open cells) = 10, edges (4-neighbour) = 10

grid = ["..#.",
        ".#..",
        "...."]                                   # '#' is a wall, '.' is open
R, C = len(grid), len(grid[0])
DR, DC = [-1, 1, 0, 0], [0, 0, -1, 1]             # up, down, left, right

def is_open(r, c):
    return 0 <= r < R and 0 <= c < C and grid[r][c] == "."

for r, c in [(0, 0), (1, 2), (2, 1)]:
    four = [(r + dr, c + dc) for dr, dc in zip(DR, DC) if is_open(r + dr, c + dc)]
    eight = sum(is_open(r + dr, c + dc) for dr in (-1, 0, 1) for dc in (-1, 0, 1)
                if (dr, dc) != (0, 0))
    cells = " ".join(f"({a},{b})" for a, b in four)
    print(f"cell ({r},{c}) id {r * C + c}: 4-nbrs {cells} | 8-nbrs count {eight}")

V = E = 0
for r in range(R):
    for c in range(C):
        if is_open(r, c):
            V += 1
            E += is_open(r, c + 1) + is_open(r + 1, c)   # right and down: each edge once
print(f"vertices (open cells) = {V}, edges (4-neighbour) = {E}")

cell (0,0) id 0: 4-nbrs (1,0) (0,1) | 8-nbrs count 2
cell (1,2) id 6: 4-nbrs (2,2) (1,3) | 8-nbrs count 6
cell (2,1) id 9: 4-nbrs (2,0) (2,2) | 8-nbrs count 4
vertices (open cells) = 10, edges (4-neighbour) = 10

State space — প্রতিটি অবস্থা একটি vertex

Implicit graph-এর আরও বড় রূপ হলো state space: কোনো ধাঁধা বা প্রক্রিয়ার প্রতিটি সম্ভাব্য অবস্থা একটি vertex, আর এক চালে এক অবস্থা থেকে অন্যটিতে যাওয়া একটি edge. ৮-ধাঁধা (3 × 3 বোর্ডে ১–৮ টাইল আর একটি ফাঁকা ঘর) নিন: বোর্ডের প্রতিটি সাজানো একটি vertex, আর ফাঁকা ঘরের পাশের একটি টাইল সরানো একটি edge. মোট সাজানো 9! = 3,62,880, কিন্তু একটি নির্দিষ্ট শুরু থেকে ঠিক অর্ধেক, 1,81,440টিতে পৌঁছানো যায় — গ্রাফটির দুটি component. “সবচেয়ে কম চালে সমাধান” মানে এই গ্রাফে সবচেয়ে ছোট পথ, BFS দিয়ে (পর্ব ৪০)। প্রতিবেশী তৈরি হয় চলতে চলতে, আর দেখা অবস্থাগুলো একটি hash set-এ মনে রাখা হয়।

৯ · মডিউল ৬-এর মানচিত্র — কোন প্রশ্নে কোন অ্যালগরিদম

গ্রাফ চিনে ফেলার পর প্রশ্ন: “আমি আসলে কী জানতে চাই?” নিচের টেবিলটি এই মডিউলের বাকি পর্বগুলোর মানচিত্র। Complexity-গুলো adjacency list ধরে।

একটি জিনিস লক্ষ করুন: প্রথম তিনটি আর SCC — সবই O(n + m), অর্থাৎ গ্রাফটি একবার পড়ার সময়ের সমান। এগুলো সম্ভব হয় কারণ adjacency list-এ প্রতিটি edge মোট দুবার (undirected) বা একবার (directed) ছোঁয়া হয় — আবার handshake lemma.

১০ · AI-এর যুগে গ্রাফ — মডেলিং আপনার, যাচাইও আপনার

“এই সমস্যার জন্য গ্রাফ বানিয়ে BFS লিখে দাও” — AI সহকারী এক নিমেষে কোড দেবে। কিন্তু গ্রাফ-সমস্যার কঠিন অংশটি প্রায়ই কোড নয়, মডেলিং: কী vertex, কী edge, দিক আছে কি না, ওজন কোথা থেকে আসে, state-এ কী কী রাখতে হবে। আর complexity-র প্রশ্নে AI প্রায়ই বলে “O(V + E)” — অথচ নিজেই কোডটি লিখেছে adjacency matrix দিয়ে।

গ্রাফের কোডে AI সাধারণত যেসব ভুল করে

গ্রাফের কোড যাচাইয়ের চেকলিস্ট

• খাতায় ছোট একটি উদাহরণ এঁকে নিজে vertex, edge, দিক আর ওজন ঠিক করেছি — AI-এর মডেল তার সাথে মিলিয়েছি
• গ্রাফ পড়ার পর assert করেছি: Σ |adj[u]| = 2m (undirected) বা m (directed)
• Edge case চালিয়েছি: n = 1, m = 0, self-loop, parallel edge, বিচ্ছিন্ন vertex, vertex n-কে ছোঁয়া edge
• জায়গার হিসাব করেছি: matrix হলে n² × ঘরের আকার মেমরি সীমার মধ্যে কি না
• ছোট এলোমেলো গ্রাফে আমার দ্রুত কোডের উত্তর একটি সরল brute force-এর (যেমন matrix দিয়ে লেখা) সাথে মিলিয়েছি — stress testing
• AI-এর complexity দাবিতে কোন উপস্থাপন ধরা হয়েছে, তা আলাদা করে জিজ্ঞেস করেছি