پرش به محتویات

کد Prüfer

در این مقاله به بررسی کد موسوم به کد Prüfer (یا دنباله Prüfer) خواهیم پرداخت که روشی برای رمزگذاری یک درخت برچسب‌دار به یک دنباله از اعداد به روشی منحصر به فرد است.

با کمک کد Prüfer، فرمول کیلی (Cayley's formula) را اثبات خواهیم کرد (که تعداد درخت‌های فراگیر را در یک گراف کامل مشخص می‌کند). همچنین راه‌حل مسئله شمارش تعداد راه‌های اضافه کردن یال به یک گراف برای همبند کردن آن را نشان می‌دهیم.

نکته، درخت‌هایی که فقط از یک رأس تشکیل شده‌اند را در نظر نخواهیم گرفت - این یک حالت خاص است که در آن چندین گزاره با هم در تضاد قرار می‌گیرند.

کد Prüfer

کد Prüfer روشی برای رمزگذاری یک درخت برچسب‌دار با $n$ رأس با استفاده از یک دنباله از $n - 2$ عدد صحیح در بازه $[0; n-1]$ است. این رمزگذاری همچنین به عنوان یک تناظر یک به یک (bijection) بین تمام درخت‌های فراگیر یک گراف کامل و دنباله‌های عددی عمل می‌کند.

اگرچه استفاده از کد Prüfer برای ذخیره‌سازی و کار با درخت به دلیل مشخصات این نمایش، غیرعملی است، کدهای Prüfer به طور مکرر استفاده می‌شوند: عمدتاً در حل مسائل ترکیبیاتی.

مخترع آن - Heinz Prüfer - این کد را در سال ۱۹۱۸ به عنوان اثباتی برای فرمول کیلی پیشنهاد داد.

ساخت کد Prüfer برای یک درخت داده شده

کد Prüfer به صورت زیر ساخته می‌شود. رویه زیر را $n - 2$ بار تکرار می‌کنیم: برگ درخت با کوچکترین شماره را انتخاب کرده، آن را از درخت حذف می‌کنیم و شماره رأسی که به آن متصل بود را یادداشت می‌کنیم. پس از $n - 2$ تکرار، تنها ۲ رأس باقی می‌ماند و الگوریتم پایان می‌یابد.

بنابراین کد Prüfer برای یک درخت داده شده، دنباله‌ای از $n - 2$ عدد است که هر عدد شماره رأس متصل به برگ حذف شده است، یعنی این عدد در بازه $[0, n-1]$ قرار دارد.

الگوریتم محاسبه کد Prüfer را می‌توان به راحتی با پیچیدگی زمانی $O(n \log n)$ پیاده‌سازی کرد، تنها با استفاده از یک ساختمان داده برای استخراج کمینه (به عنوان مثال set یا priority_queue در C++) که لیستی از تمام برگ‌های فعلی را در خود نگه می‌دارد.

```cpp file=pruefer_code_slow vector> adj;

vector pruefer_code() { int n = adj.size(); set leafs; vector degree(n); vector 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;

} ``` با این حال، این ساختار را می‌توان در زمان خطی نیز پیاده‌سازی کرد. چنین رویکردی در بخش بعدی توضیح داده شده است.

ساخت کد Prüfer برای یک درخت داده شده در زمان خطی

اساس این الگوریتم استفاده از یک اشاره‌گر متحرک است که همیشه به رأس برگ فعلی که می‌خواهیم حذف کنیم، اشاره می‌کند. در نگاه اول این کار غیرممکن به نظر می‌رسد، زیرا در طول فرآیند ساخت کد Prüfer، شماره برگ می‌تواند افزایش و کاهش یابد. با این حال، با نگاهی دقیق‌تر، این موضوع در واقع درست نیست. تعداد برگ‌ها افزایش نخواهد یافت. یا تعداد آن‌ها یکی کم می‌شود (یک رأس برگ را حذف می‌کنیم و برگ جدیدی به دست نمی‌آوریم)، یا ثابت می‌ماند (یک رأس برگ را حذف می‌کنیم و یک رأس برگ دیگر به دست می‌آوریم). در حالت اول، راهی جز جستجو برای کوچکترین رأس برگ بعدی وجود ندارد. اما در حالت دوم، می‌توانیم در زمان $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)$ است. cpp file=pruefer_code_fast 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)$ است.

برخی از ویژگی‌های کد Prüfer

  • پس از ساخت کد Prüfer دو رأس باقی می‌ماند. یکی از آن‌ها رأس با بالاترین شماره، یعنی $n-1$ است، اما در مورد دیگری نمی‌توان چیز بیشتری گفت.
  • هر رأس دقیقاً به تعداد ثابتی در کد Prüfer ظاهر می‌شود - درجه آن منهای یک. این را می‌توان به راحتی بررسی کرد، زیرا هر بار که برچسب آن را در کد ثبت می‌کنیم، درجه‌اش کمتر می‌شود و زمانی که درجه آن به $1$ برسد، آن را حذف می‌کنیم. برای دو رأس باقی‌مانده نیز این واقعیت صادق است.

بازیابی درخت با استفاده از کد Prüfer

برای بازیابی درخت، کافی است فقط روی خاصیتی که در بخش قبل بحث شد تمرکز کنیم. ما از قبل درجه تمام رئوس در درخت مورد نظر را می‌دانیم. بنابراین می‌توانیم تمام رئوس برگ و همچنین اولین برگی که در مرحله اول حذف شده است را پیدا کنیم (این باید کوچکترین برگ باشد). این رأس برگ به رأسی متصل بود که شماره آن در اولین خانه کد Prüfer قرار دارد.

بنابراین ما اولین یالی که هنگام تولید کد Prüfer حذف شده بود را پیدا کردیم. می‌توانیم این یال را به جواب اضافه کرده و درجه‌ها را در دو سر یال کاهش دهیم.

این عملیات را تا زمانی که از تمام اعداد کد Prüfer استفاده کنیم تکرار می‌کنیم: به دنبال کوچکترین رأسی با درجه برابر با $1$ می‌گردیم، آن را به رأس بعدی از کد Prüfer متصل می‌کنیم و درجه‌ها را کاهش می‌دهیم.

در پایان تنها دو رأس با درجه برابر با $1$ باقی می‌ماند. اینها رئوسی هستند که در فرآیند کد Prüfer حذف نشدند. آنها را به هم متصل می‌کنیم تا آخرین یال درخت را به دست آوریم. یکی از آنها همیشه رأس $n-1$ خواهد بود.

این الگوریتم را می‌توان به راحتی در $O(n \log n)$ پیاده‌سازی کرد: ما از یک ساختمان داده که از استخراج کمینه پشتیبانی می‌کند (به عنوان مثال set<> یا priority_queue<> در C++) برای ذخیره تمام رئوس برگ استفاده می‌کنیم.

پیاده‌سازی زیر لیستی از یال‌های متناظر با درخت را برمی‌گرداند.

```cpp file=pruefer_decode_slow vector> pruefer_decode(vector const& code) { int n = code.size() + 2; vector 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;

} ```

بازیابی درخت با استفاده از کد Prüfer در زمان خطی

برای به دست آوردن درخت در زمان خطی، می‌توانیم از همان تکنیکی که برای به دست آوردن کد Prüfer در زمان خطی استفاده شد، استفاده کنیم. ما به ساختمان داده برای استخراج کمینه نیازی نداریم. در عوض، می‌توانیم متوجه شویم که پس از پردازش یال فعلی، تنها یک رأس به برگ تبدیل می‌شود. بنابراین می‌توانیم یا با این رأس ادامه دهیم، یا با حرکت دادن یک اشاره‌گر، یک رأس کوچکتر را با جستجوی خطی پیدا کنیم. cpp file=pruefer_decode_fast 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; }

تناظر یک به یک بین درخت‌ها و کدهای Prüfer

برای هر درخت یک کد Prüfer متناظر با آن وجود دارد. و برای هر کد Prüfer می‌توانیم درخت اصلی را بازیابی کنیم.

از این رو نتیجه می‌شود که هر کد Prüfer (یعنی دنباله‌ای از $n-2$ عدد در بازه $[0; n - 1]$) نیز متناظر با یک درخت است.

بنابراین، همه درخت‌ها و همه کدهای Prüfer یک تناظر یک به یک (one-to-one correspondence) تشکیل می‌دهند.

فرمول کیلی

فرمول کیلی بیان می‌کند که تعداد درخت‌های فراگیر در یک گراف کامل برچسب‌دار با $n$ رأس برابر است با:

$$n^{n-2}$$

اثبات‌های متعددی برای این فرمول وجود دارد. با استفاده از مفهوم کد Prüfer، این گزاره جای تعجب ندارد.

در واقع، هر کد Prüfer با $n-2$ عدد از بازه $[0; n-1]$ متناظر با یک درخت با $n$ رأس است. بنابراین ما $n^{n-2}$ کد Prüfer متفاوت از این نوع داریم. از آنجایی که هر چنین درختی یک درخت فراگیر از یک گراف کامل با $n$ رأس است، تعداد چنین درختان فراگیری نیز $n^{n-2}$ است.

تعداد راه‌های همبند کردن یک گراف

مفهوم کدهای Prüfer حتی از این هم قدرتمندتر است. این مفهوم اجازه می‌دهد تا فرمول‌های بسیار کلی‌تری نسبت به فرمول کیلی ایجاد کنیم.

در این مسئله، یک گراف با $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$ بار در کد Prüfer ظاهر می‌شود. کد Prüfer برای درختی با $k$ رأس دارای طول $k-2$ است. بنابراین تعداد راه‌های انتخاب یک کد با $k-2$ عدد که در آن عدد $i$ دقیقاً $d_i - 1$ بار ظاهر شود، برابر است با ضریب چندجمله‌ای (multinomial coefficient)

$$\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}$$

در حال حاضر این پاسخ واقعاً وحشتناک به نظر می‌رسد، اما می‌توانیم از قضیه چندجمله‌ای (multinomial theorem) استفاده کنیم که می‌گوید:

$$(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$ نیز صادق است.

مسائل تمرینی