প্রুফার কোড#
এই নিবন্ধে আমরা তথাকথিত প্রুফার কোড (বা প্রুফার সিকোয়েন্স) দেখব, যা একটি লেবেলযুক্ত ট্রিকে অনন্যভাবে সংখ্যার একটি সিকোয়েন্সে এনকোড করার একটি পদ্ধতি।
প্রুফার কোডের সাহায্যে আমরা কেইলির সূত্র প্রমাণ করব (যা একটি কমপ্লিট গ্রাফে স্প্যানিং ট্রির সংখ্যা নির্দিষ্ট করে)। এছাড়াও আমরা একটি গ্রাফকে সংযুক্ত করতে এজ যোগ করার উপায়ের সংখ্যা গণনার সমস্যার সমাধান দেখাব।
দ্রষ্টব্য, আমরা একক ভার্টেক্স নিয়ে গঠিত ট্রি বিবেচনা করব না - এটি একটি বিশেষ ক্ষেত্র যেখানে একাধিক বিবৃতি সাংঘর্ষিক হয়।
প্রুফার কোড#
প্রুফার কোড হলো $n$টি ভার্টেক্স বিশিষ্ট একটি লেবেলযুক্ত ট্রিকে $[0; n-1]$ ব্যবধানের $n - 2$টি পূর্ণসংখ্যার সিকোয়েন্স ব্যবহার করে এনকোড করার একটি পদ্ধতি। এই এনকোডিংটি একটি কমপ্লিট গ্রাফের সকল স্প্যানিং ট্রি ও সংখ্যা সিকোয়েন্সগুলোর মধ্যে একটি বাইজেকশন (এক-এক ও সার্বিক সম্পর্ক) হিসেবেও কাজ করে।
যদিও প্রুফার কোড ব্যবহার করে ট্রি সংরক্ষণ ও অপারেশন করা উপস্থাপনার বৈশিষ্ট্যের কারণে অব্যবহারিক, প্রুফার কোড ঘন ঘন ব্যবহৃত হয়: প্রধানত কম্বিনেটরিয়াল সমস্যা সমাধানে।
আবিষ্কারক - হাইন্ৎস প্রুফার - ১৯১৮ সালে কেইলির সূত্রের প্রমাণ হিসেবে এই কোড প্রস্তাব করেন।
একটি প্রদত্ত ট্রির জন্য প্রুফার কোড নির্মাণ#
প্রুফার কোড নিম্নরূপে নির্মাণ করা হয়। আমরা নিম্নলিখিত প্রক্রিয়াটি $n - 2$ বার পুনরাবৃত্তি করব: ট্রির সবচেয়ে ছোট নম্বরের লিফ নির্বাচন করি, এটিকে ট্রি থেকে সরিয়ে দিই, এবং এটির সাথে সংযুক্ত ভার্টেক্সের নম্বর লিখে রাখি। $n - 2$ ইটারেশনের পর মাত্র $2$টি ভার্টেক্স অবশিষ্ট থাকবে, এবং অ্যালগরিদম শেষ হয়।
সুতরাং একটি প্রদত্ত ট্রির জন্য প্রুফার কোড হলো $n - 2$টি সংখ্যার একটি সিকোয়েন্স, যেখানে প্রতিটি সংখ্যা সংযুক্ত ভার্টেক্সের নম্বর, অর্থাৎ এই সংখ্যা $[0, n-1]$ ব্যবধানে।
প্রুফার কোড গণনার অ্যালগরিদম সহজেই $O(n \log n)$ টাইম কমপ্লেক্সিটিতে ইমপ্লিমেন্ট করা যায়, কেবল ন্যূনতম নির্ণয়ের জন্য একটি ডেটা স্ট্রাকচার ব্যবহার করে (উদাহরণস্বরূপ C++-এ set বা priority_queue), যেটিতে সকল বর্তমান লিফের একটি তালিকা থাকে।
vector<vector<int>> adj;
vector<int> pruefer_code() {
int n = adj.size();
set<int> leafs;
vector<int> degree(n);
vector<bool> killed(n, false);
for (int i = 0; i < n; i++) {
degree[i] = adj[i].size();
if (degree[i] == 1)
leafs.insert(i);
}
vector<int> code(n - 2);
for (int i = 0; i < n - 2; i++) {
int leaf = *leafs.begin();
leafs.erase(leafs.begin());
killed[leaf] = true;
int v;
for (int u : adj[leaf]) {
if (!killed[u])
v = u;
}
code[i] = v;
if (--degree[v] == 1)
leafs.insert(v);
}
return code;
}তবে নির্মাণ লিনিয়ার সময়েও ইমপ্লিমেন্ট করা যায়। এই ধরনের পদ্ধতি পরবর্তী অংশে বর্ণনা করা হয়েছে।
লিনিয়ার সময়ে একটি প্রদত্ত ট্রির জন্য প্রুফার কোড নির্মাণ#
অ্যালগরিদমের মূল বিষয় হলো একটি মুভিং পয়েন্টার ব্যবহার করা, যেটি সর্বদা বর্তমান লিফ ভার্টেক্সের দিকে নির্দেশ করবে যেটি আমরা সরাতে চাই।
প্রথম দৃষ্টিতে এটি অসম্ভব মনে হয়, কারণ প্রুফার কোড নির্মাণের প্রক্রিয়ায় লিফ নম্বর বাড়তে ও কমতে পারে। তবে ঘনিষ্ঠভাবে দেখলে, এটি আসলে সত্য নয়। লিফের সংখ্যা বাড়বে না। হয় সংখ্যা এক কমে (আমরা একটি লিফ ভার্টেক্স সরাই এবং নতুন একটি পাই না), অথবা এটি একই থাকে (আমরা একটি লিফ ভার্টেক্স সরাই এবং আরেকটি পাই)। প্রথম ক্ষেত্রে পরবর্তী ক্ষুদ্রতম লিফ ভার্টেক্স খোঁজা ছাড়া অন্য কোনো উপায় নেই। তবে দ্বিতীয় ক্ষেত্রে, আমরা $O(1)$ সময়ে সিদ্ধান্ত নিতে পারি, নতুন লিফ ভার্টেক্স ব্যবহার চালিয়ে যাওয়া যাবে কিনা, নাকি পরবর্তী ক্ষুদ্রতম লিফ ভার্টেক্স খুঁজতে হবে। এবং বেশ অনেক সময়ই আমরা নতুন লিফ ভার্টেক্স নিয়ে এগিয়ে যেতে পারি।
এটি করতে আমরা একটি ভেরিয়েবল $\text{ptr}$ ব্যবহার করব, যা নির্দেশ করবে যে $0$ থেকে $\text{ptr}$ পর্যন্ত ভার্টেক্সের সেটে সর্বাধিক একটি লিফ ভার্টেক্স আছে, যথা বর্তমানটি। ঐ রেঞ্জের অন্য সকল ভার্টেক্স হয় ইতিমধ্যে ট্রি থেকে সরানো হয়েছে, অথবা এখনও একাধিক সংলগ্ন ভার্টেক্স আছে। একই সাথে আমরা বলি যে, $\text{ptr}$-এর চেয়ে বড় কোনো লিফ ভার্টেক্স আমরা এখনও সরাইনি।
এই ভেরিয়েবলটি প্রথম ক্ষেত্রেই খুবই সহায়ক। বর্তমান লিফ নোড সরানোর পর, আমরা জানি যে $0$ ও $\text{ptr}$-এর মধ্যে কোনো লিফ নোড থাকতে পারে না, তাই আমরা সরাসরি $\text{ptr} + 1$ থেকে পরবর্তী খোঁজা শুরু করতে পারি, এবং ভার্টেক্স $0$ থেকে খোঁজা শুরু করতে হয় না। এবং দ্বিতীয় ক্ষেত্রে, আমরা আরও দুটি উপক্ষেত্র আলাদা করতে পারি: হয় নতুন পাওয়া লিফ ভার্টেক্স $\text{ptr}$-এর চেয়ে ছোট, তাহলে এটিই পরবর্তী লিফ ভার্টেক্স হতে হবে, কারণ আমরা জানি $\text{ptr}$-এর চেয়ে ছোট অন্য কোনো ভার্টেক্স নেই। অথবা নতুন পাওয়া লিফ ভার্টেক্স বড়। কিন্তু তাহলেও আমরা জানি যে এটি $\text{ptr}$-এর চেয়ে বড় হতে হবে, এবং আবার $\text{ptr} + 1$ থেকে খোঁজা শুরু করতে পারি।
যদিও আমাদের পরবর্তী লিফ ভার্টেক্সের জন্য একাধিক লিনিয়ার সার্চ করতে হতে পারে, পয়েন্টার $\text{ptr}$ শুধু বাড়ে এবং তাই মোট টাইম কমপ্লেক্সিটি $O(n)$।
vector<vector<int>> adj;
vector<int> parent;
void dfs(int v) {
for (int u : adj[v]) {
if (u != parent[v]) {
parent[u] = v;
dfs(u);
}
}
}
vector<int> pruefer_code() {
int n = adj.size();
parent.resize(n);
parent[n-1] = -1;
dfs(n-1);
int ptr = -1;
vector<int> degree(n);
for (int i = 0; i < n; i++) {
degree[i] = adj[i].size();
if (degree[i] == 1 && ptr == -1)
ptr = i;
}
vector<int> code(n - 2);
int leaf = ptr;
for (int i = 0; i < n - 2; i++) {
int next = parent[leaf];
code[i] = next;
if (--degree[next] == 1 && next < ptr) {
leaf = next;
} else {
ptr++;
while (degree[ptr] != 1)
ptr++;
leaf = ptr;
}
}
return code;
}কোডে আমরা প্রথমে প্রতিটি ভার্টেক্সের পূর্বসূরি parent[i] খুঁজি, অর্থাৎ যে পূর্বসূরি থাকবে যখন আমরা ভার্টেক্সটি ট্রি থেকে সরিয়ে দেব।
আমরা ট্রিকে $n-1$ ভার্টেক্সে রুট করে এই পূর্বসূরি খুঁজতে পারি।
এটি সম্ভব কারণ $n-1$ ভার্টেক্স কখনও ট্রি থেকে সরানো হবে না।
আমরা প্রতিটি ভার্টেক্সের ডিগ্রিও গণনা করি।
ptr হলো পয়েন্টার যা অবশিষ্ট লিফ ভার্টেক্সগুলোর (বর্তমানটি leaf ছাড়া) ন্যূনতম আকার নির্দেশ করে।
আমরা হয় বর্তমান লিফ ভার্টেক্সকে next দিয়ে অ্যাসাইন করব, যদি এটিও একটি লিফ ভার্টেক্স হয় এবং ptr-এর চেয়ে ছোট হয়, অথবা পয়েন্টার বাড়িয়ে ক্ষুদ্রতম লিফ ভার্টেক্সের জন্য লিনিয়ার সার্চ শুরু করব।
সহজেই দেখা যায় যে, এই কোডের কমপ্লেক্সিটি $O(n)$।
প্রুফার কোডের কিছু বৈশিষ্ট্য#
- প্রুফার কোড নির্মাণের পর দুটি ভার্টেক্স অবশিষ্ট থাকবে। তাদের একটি হলো সর্বোচ্চ ভার্টেক্স $n-1$, কিন্তু অন্যটি সম্পর্কে আর কিছু বলা যায় না।
- প্রতিটি ভার্টেক্স প্রুফার কোডে ঠিক একটি নির্দিষ্ট সংখ্যক বার উপস্থিত হয় - তার ডিগ্রি বিয়োগ এক। এটি সহজেই যাচাই করা যায়, যেহেতু প্রতিবার আমরা কোডে এর লেবেল রেকর্ড করার সময় ডিগ্রি ছোট হয়, এবং ডিগ্রি $1$ হলে আমরা এটি সরিয়ে দিই। অবশিষ্ট দুটি ভার্টেক্সের জন্যও এই তথ্য সত্য।
প্রুফার কোড ব্যবহার করে ট্রি পুনরুদ্ধার#
ট্রি পুনরুদ্ধার করতে শুধু শেষ অংশে আলোচিত বৈশিষ্ট্যের উপর ফোকাস করাই যথেষ্ট। আমরা ইতিমধ্যে কাঙ্ক্ষিত ট্রিতে সকল ভার্টেক্সের ডিগ্রি জানি। অতএব আমরা সকল লিফ ভার্টেক্স খুঁজতে পারি, এবং প্রথম ধাপে সরানো প্রথম লিফটিও (এটি ক্ষুদ্রতম লিফ হতে হবে)। এই লিফ ভার্টেক্সটি প্রুফার কোডের প্রথম সেলের সংখ্যার সাথে সংশ্লিষ্ট ভার্টেক্সের সাথে সংযুক্ত ছিল।
এভাবে আমরা প্রুফার কোড তৈরি করার সময় প্রথম সরানো এজটি পেলাম। আমরা এই এজটি উত্তরে যোগ করতে পারি এবং এজের উভয় প্রান্তের ডিগ্রি কমাতে পারি।
আমরা প্রুফার কোডের সকল সংখ্যা ব্যবহার না করা পর্যন্ত এই অপারেশন পুনরাবৃত্তি করব: ডিগ্রি $1$ সমান ন্যূনতম ভার্টেক্স খুঁজি, এটিকে প্রুফার কোডের পরবর্তী ভার্টেক্সের সাথে সংযুক্ত করি, এবং ডিগ্রি কমাই।
শেষে মাত্র দুটি ভার্টেক্স বাকি থাকবে যাদের ডিগ্রি $1$ সমান। এগুলো হলো সেই ভার্টেক্স যেগুলো প্রুফার কোড প্রক্রিয়ায় সরানো হয়নি। আমরা ট্রির শেষ এজ পেতে এগুলো সংযুক্ত করি। তাদের একটি সর্বদা $n-1$ ভার্টেক্স হবে।
এই অ্যালগরিদম সহজেই $O(n \log n)$-এ ইমপ্লিমেন্ট করা যায়: আমরা সকল লিফ ভার্টেক্স সংরক্ষণ করতে ন্যূনতম নির্ণয়ে সমর্থন করে এমন একটি ডেটা স্ট্রাকচার ব্যবহার করি (উদাহরণস্বরূপ C++-এ set<> বা priority_queue<>)।
নিম্নলিখিত ইমপ্লিমেন্টেশনটি ট্রির সাথে সংশ্লিষ্ট এজের তালিকা রিটার্ন করে।
vector<pair<int, int>> pruefer_decode(vector<int> const& code) {
int n = code.size() + 2;
vector<int> degree(n, 1);
for (int i : code)
degree[i]++;
set<int> leaves;
for (int i = 0; i < n; i++) {
if (degree[i] == 1)
leaves.insert(i);
}
vector<pair<int, int>> edges;
for (int v : code) {
int leaf = *leaves.begin();
leaves.erase(leaves.begin());
edges.emplace_back(leaf, v);
if (--degree[v] == 1)
leaves.insert(v);
}
edges.emplace_back(*leaves.begin(), n-1);
return edges;
}লিনিয়ার সময়ে প্রুফার কোড ব্যবহার করে ট্রি পুনরুদ্ধার#
লিনিয়ার সময়ে ট্রি পেতে আমরা প্রুফার কোড লিনিয়ার সময়ে পেতে ব্যবহৃত একই কৌশল প্রয়োগ করতে পারি।
আমাদের ন্যূনতম নির্ণয়ের জন্য কোনো ডেটা স্ট্রাকচারের প্রয়োজন নেই। পরিবর্তে আমরা লক্ষ্য করতে পারি যে, বর্তমান এজ প্রক্রিয়া করার পর, শুধু একটি ভার্টেক্স লিফ হয়। তাই আমরা হয় এই ভার্টেক্স নিয়ে এগিয়ে যেতে পারি, অথবা পয়েন্টার সরিয়ে লিনিয়ার সার্চ করে একটি ছোটটি খুঁজতে পারি।
vector<pair<int, int>> pruefer_decode(vector<int> const& code) {
int n = code.size() + 2;
vector<int> degree(n, 1);
for (int i : code)
degree[i]++;
int ptr = 0;
while (degree[ptr] != 1)
ptr++;
int leaf = ptr;
vector<pair<int, int>> edges;
for (int v : code) {
edges.emplace_back(leaf, v);
if (--degree[v] == 1 && v < ptr) {
leaf = v;
} else {
ptr++;
while (degree[ptr] != 1)
ptr++;
leaf = ptr;
}
}
edges.emplace_back(leaf, n-1);
return edges;
}ট্রি ও প্রুফার কোডের মধ্যে বাইজেকশন#
প্রতিটি ট্রির জন্য একটি প্রুফার কোড আছে যা এর সাথে সম্পর্কিত। এবং প্রতিটি প্রুফার কোডের জন্য আমরা মূল ট্রি পুনরুদ্ধার করতে পারি।
এটি থেকে অনুসরণ করে যে প্রতিটি প্রুফার কোড (অর্থাৎ $[0; n - 1]$ রেঞ্জে $n-2$টি সংখ্যার একটি সিকোয়েন্স) একটি ট্রির সাথে সম্পর্কিত।
অতএব সকল ট্রি ও সকল প্রুফার কোড একটি বাইজেকশন (এক-এক সম্পর্ক) গঠন করে।
কেইলির সূত্র#
কেইলির সূত্র বলে যে $n$টি ভার্টেক্স বিশিষ্ট একটি কমপ্লিট লেবেলযুক্ত গ্রাফে স্প্যানিং ট্রির সংখ্যা সমান:
$$n^{n-2}$$এই সূত্রের একাধিক প্রমাণ আছে। প্রুফার কোডের ধারণা ব্যবহার করলে এই বিবৃতি কোনো আশ্চর্যের বিষয় নয়।
প্রকৃতপক্ষে, $[0; n-1]$ ব্যবধান থেকে $n-2$টি সংখ্যা বিশিষ্ট যেকোনো প্রুফার কোড $n$টি ভার্টেক্সের কোনো ট্রির সাথে সম্পর্কিত। তাই আমাদের কাছে $n^{n-2}$টি ভিন্ন প্রুফার কোড আছে। যেহেতু প্রতিটি এই ধরনের ট্রি $n$টি ভার্টেক্স বিশিষ্ট একটি কমপ্লিট গ্রাফের একটি স্প্যানিং ট্রি, তাই এই ধরনের স্প্যানিং ট্রির সংখ্যাও $n^{n-2}$।
একটি গ্রাফকে সংযুক্ত করার উপায়ের সংখ্যা#
প্রুফার কোডের ধারণা আরও শক্তিশালী। এটি কেইলির সূত্রের চেয়ে আরও সাধারণ সূত্র তৈরি করতে দেয়।
এই সমস্যায় আমাদের $n$টি ভার্টেক্স ও $m$টি এজ বিশিষ্ট একটি গ্রাফ দেওয়া আছে। গ্রাফে বর্তমানে $k$টি কম্পোনেন্ট আছে। আমরা $k-1$টি এজ যোগ করার উপায়ের সংখ্যা গণনা করতে চাই যেন গ্রাফটি সংযুক্ত হয় (স্পষ্টতই $k-1$ হলো গ্রাফকে সংযুক্ত করতে প্রয়োজনীয় ন্যূনতম সংখ্যা)।
আসুন এই সমস্যা সমাধানের জন্য একটি সূত্র বের করি।
আমরা গ্রাফের সংযুক্ত কম্পোনেন্টগুলোর আকারের জন্য $s_1, \dots, s_k$ ব্যবহার করি। আমরা একটি সংযুক্ত কম্পোনেন্টের মধ্যে এজ যোগ করতে পারি না। তাই দেখা যাচ্ছে এই সমস্যাটি $k$টি ভার্টেক্স বিশিষ্ট একটি কমপ্লিট গ্রাফের স্প্যানিং ট্রির সংখ্যা খোঁজার সাথে খুবই সাদৃশ্যপূর্ণ। একমাত্র পার্থক্য হলো প্রতিটি ভার্টেক্সের আসলে আকার $s_i$: ভার্টেক্স $i$-কে সংযুক্ত করে এমন প্রতিটি এজ আসলে উত্তরকে $s_i$ দিয়ে গুণ করে।
সুতরাং সম্ভাব্য উপায়ের সংখ্যা গণনা করতে, সংযোগকারী ট্রিতে $k$টি ভার্টেক্সের প্রতিটি কতবার ব্যবহৃত হয় তা গণনা করা গুরুত্বপূর্ণ। সমস্যার জন্য একটি সূত্র পেতে সকল সম্ভাব্য ডিগ্রির উপর উত্তর যোগ করা প্রয়োজন।
ধরুন ভার্টেক্সগুলো সংযুক্ত করার পর ট্রিতে $d_1, \dots, d_k$ হলো ভার্টেক্সগুলোর ডিগ্রি। ডিগ্রির যোগফল এজ সংখ্যার দ্বিগুণ:
$$\sum_{i=1}^k d_i = 2k - 2$$যদি ভার্টেক্স $i$-এর ডিগ্রি $d_i$ হয়, তাহলে এটি প্রুফার কোডে $d_i - 1$ বার উপস্থিত হয়। $k$টি ভার্টেক্স বিশিষ্ট একটি ট্রির জন্য প্রুফার কোডের দৈর্ঘ্য $k-2$। তাই $k-2$টি সংখ্যার একটি কোড বেছে নেওয়ার উপায়ের সংখ্যা যেখানে $i$ সংখ্যাটি ঠিক $d_i - 1$ বার উপস্থিত হয়, তা মাল্টিনোমিয়াল সহগের সমান
$$\binom{k-2}{d_1-1, d_2-1, \dots, d_k-1} = \frac{(k-2)!}{(d_1-1)! (d_2-1)! \cdots (d_k-1)!}.$$ভার্টেক্স $i$-এর সংলগ্ন প্রতিটি এজ উত্তরকে $s_i$ দিয়ে গুণ করে, তাই আমরা উত্তর পাই, ধরে নিই ভার্টেক্সগুলোর ডিগ্রি $d_1, \dots, d_k$:
$$s_1^{d_1} \cdot s_2^{d_2} \cdots s_k^{d_k} \cdot \binom{k-2}{d_1-1, d_2-1, \dots, d_k-1}$$চূড়ান্ত উত্তর পেতে আমাদের ডিগ্রি বেছে নেওয়ার সকল সম্ভাব্য উপায়ের জন্য এটি যোগ করতে হবে:
$$\sum_{\substack{d_i \ge 1 \\\\ \sum_{i=1}^k d_i = 2k -2}} s_1^{d_1} \cdot s_2^{d_2} \cdots s_k^{d_k} \cdot \binom{k-2}{d_1-1, d_2-1, \dots, d_k-1}$$বর্তমানে এটি সত্যিই ভয়ংকর উত্তর মনে হচ্ছে, তবে আমরা মাল্টিনোমিয়াল উপপাদ্য ব্যবহার করতে পারি, যা বলে:
$$(x_1 + \dots + x_m)^p = \sum_{\substack{c_i \ge 0 \\\\ \sum_{i=1}^m c_i = p}} x_1^{c_1} \cdot x_2^{c_2} \cdots x_m^{c_m} \cdot \binom{p}{c_1, c_2, \dots c_m}$$এটি ইতিমধ্যে বেশ সাদৃশ্যপূর্ণ দেখাচ্ছে। এটি ব্যবহার করতে আমাদের শুধু $e_i = d_i - 1$ দিয়ে প্রতিস্থাপন করতে হবে:
$$\sum_{\substack{e_i \ge 0 \\\\ \sum_{i=1}^k e_i = k - 2}} s_1^{e_1+1} \cdot s_2^{e_2+1} \cdots s_k^{e_k+1} \cdot \binom{k-2}{e_1, e_2, \dots, e_k}$$মাল্টিনোমিয়াল উপপাদ্য প্রয়োগ করার পর আমরা সমস্যার উত্তর পাই:
$$s_1 \cdot s_2 \cdots s_k \cdot (s_1 + s_2 + \dots + s_k)^{k-2} = s_1 \cdot s_2 \cdots s_k \cdot n^{k-2}$$কাকতালীয়ভাবে এই সূত্র $k = 1$-এর জন্যও কাজ করে।