Прюферийн код¶
Энэ өгүүлэлд бид шошготой модыг тоонуудын дараалал болгон давтагдашгүй байдлаар кодлох арга болох Прюферийн код (эсвэл Прюферийн дараалал) гэгчийг авч үзнэ.
Прюферийн кодын тусламжтайгаар бид бүрэн граф дахь тэлэх модны тоог заасан Кейлигийн томьёо-г батална. Мөн бид графыг холбоост болгохын тулд ирмэг нэмэх аргын тоог тоолох бодлогын шийдийг үзүүлнэ.
Тэмдэглэл, бид ганц оройноос тогтох модыг авч үзэхгүй — энэ бол хэд хэдэн мэдэгдэл зөрчилддөг тусгай тохиолдол юм.
Прюферийн код¶
Прюферийн код гэдэг нь $n$ оройтой шошготой модыг $[0; n-1]$ интервал дахь $n - 2$ бүхэл тооны дараалал ашиглан кодлох арга юм. Энэ кодлолт мөн бүрэн графын бүх тэлэх мод ба тоон дарааллын хооронд биекц болж ажилладаг.
Хэдийгээр дүрслэлийн онцлогоос болж модыг хадгалах, түүн дээр үйлдэл хийхэд Прюферийн код ашиглах нь практик биш ч Прюферийн кодыг байнга ашигладаг: голчлон комбинаторик бодлого бодоход.
Зохион бүтээгч Хайнц Прюфер энэ кодыг 1918 онд Кейлигийн томьёоны баталгаа болгон санал болгосон.
Өгөгдсөн модны Прюферийн кодыг байгуулах¶
Прюферийн кодыг дараах байдлаар байгуулна. Бид дараах процедурыг $n - 2$ удаа давтана: бид модны хамгийн бага дугаартай навчийг сонгож, түүнийг модноос хасаад, түүнтэй холбогдсон байсан оройн дугаарыг бичнэ. $n - 2$ итерацын дараа зөвхөн $2$ орой үлдэх ба алгоритм дуусна.
Ингэснээр өгөгдсөн модны Прюферийн код нь $n - 2$ тооны дараалал бөгөөд тоо бүр нь холбогдсон оройн дугаар, өөрөөр хэлбэл энэ тоо $[0, n-1]$ интервалд байна.
Прюферийн кодыг тооцоолох алгоритмыг одоогийн бүх навчийн жагсаалтыг агуулсан, минимумыг гаргаж авах өгөгдлийн бүтэц (жишээ нь C++ дэх set эсвэл priority_queue) ашиглан $O(n \log n)$ time complexity-тэйгээр амархан хэрэгжүүлж болно.
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)$ хугацаанд шийдэж чадна. Мөн нэлээд олон тохиолдолд бид шинэ навч оройгоор үргэлжлүүлж чадна.
Үүний тулд бид $0$ ба $\text{ptr}$-ийн хоорондох оройнуудын олонлогт хамгийн ихдээ нэг навч орой буюу одоогийнх байгааг заах хувьсагч $\text{ptr}$ ашиглана. Тэр мужийн бусад бүх орой эсвэл модноос аль хэдийн хасагдсан, эсвэл нэгээс олон зэргэлдээ оройтой хэвээр байна. Үүний зэрэгцээ бид $\text{ptr}$-ээс их ямар ч навч оройг хараахан хасаагүй гэж хэлнэ.
Энэ хувьсагч эхний тохиолдолд аль хэдийн маш тустай. Одоогийн навч зангилааг хассаны дараа бид $0$ ба $\text{ptr}$-ийн хооронд навч зангилаа байж чадахгүйг мэдэх тул дараагийнхыг шууд $\text{ptr} + 1$-ээс хайж эхэлж болох ба хайлтыг орой $0$-ээс буцаан эхлүүлэх шаардлагагүй. Мөн хоёр дахь тохиолдолд бид цаашид хоёр тохиолдлыг ялгаж болно: Эсвэл шинээр гарсан навч орой $\text{ptr}$-ээс бага бөгөөд тэгвэл энэ нь дараагийн навч орой байх ёстой, учир нь бид $\text{ptr}$-ээс бага өөр орой байхгүйг мэднэ. Эсвэл шинээр гарсан навч орой илүү том байна. Гэвч тэгвэл бид түүнийг $\text{ptr}$-ээс их байх ёстойг ч бас мэдэх ба хайлтыг $\text{ptr} + 1$-ээс дахин эхлүүлж болно.
Хэдийгээр бид дараагийн навч оройг хайхын тулд олон удаа шугаман хайлт хийх шаардлагатай болж болох ч заагч $\text{ptr}$ зөвхөн нэмэгддэг тул нийт time complexity нь $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;
}
In the code we first find for each its ancestor parent[i], i.e. the ancestor that this vertex will have once we remove it from the tree.
We can find this ancestor by rooting the tree at the vertex $n-1$.
This is possible because the vertex $n-1$ will never be removed from the tree.
We also compute the degree for each vertex.
ptr is the pointer that indicates the minimum size of the remaining leaf vertices (except the current one leaf).
We will either assign the current leaf vertex with next, if this one is also a leaf vertex and it is smaller than ptr, or we start a linear search for the smallest leaf vertex by increasing the pointer.
It can be easily seen, that this code has the complexity $O(n)$.
Прюферийн кодын зарим шинж чанар¶
- Прюферийн кодыг байгуулсны дараа хоёр орой үлдэнэ. Тэдгээрийн нэг нь хамгийн өндөр орой $n-1$ боловч нөгөөгийнх нь талаар өөр юу ч хэлж болохгүй.
- Орой бүр Прюферийн кодод яг тогтмол тооны удаа буюу зэргээсээ нэгээр бага удаа гарч ирнэ. Үүнийг амархан шалгаж болно, учир нь бид түүний шошгыг кодод бичих бүрд зэрэг нь багасах ба зэрэг $1$ болмогц бид түүнийг хасна. Үлдсэн хоёр оройн хувьд ч энэ баримт үнэн.
Прюферийн код ашиглан модыг сэргээх¶
Модыг сэргээхийн тулд өмнөх хэсэгт авч үзсэн шинж чанарт л анхаарлаа хандуулахад хангалттай. Бид хайж буй мод дахь бүх оройн зэргийг аль хэдийн мэднэ. Тиймээс бид бүх навч оройг, мөн эхний алхамд хасагдсан эхний навчийг олж чадна (тэр нь хамгийн бага навч байх ёстой). Энэ навч орой Прюферийн кодын эхний нүдэн дэх тоонд харгалзах оройтой холбогдсон байсан.
Ингэснээр бид Прюферийн кодыг үүсгэх үед хасагдсан эхний ирмэгийг оллоо. Бид энэ ирмэгийг хариунд нэмж, ирмэгийн хоёр үзүүр дэх зэргийг багасгаж болно.
Бид Прюферийн кодын бүх тоог ашиглах хүртэл энэ үйлдлийг давтана: бид зэрэг нь $1$-тэй тэнцүү хамгийн бага оройг хайж, түүнийг Прюферийн кодын дараагийн оройтой холбож, зэргийг багасгана.
Эцэст нь бидэнд зэрэг нь $1$-тэй тэнцүү зөвхөн хоёр орой үлдэнэ. Эдгээр нь Прюферийн кодын процессоор хасагдаагүй оройнууд юм. Бид тэдгээрийг холбож модны сүүлийн ирмэгийг авна. Тэдгээрийн нэг нь үргэлж орой $n-1$ байх болно.
Энэ алгоритмыг $O(n \log n)$-д амархан хэрэгжүүлж болно: бид бүх навч оройг хадгалахын тулд минимум гаргаж авахыг дэмждэг өгөгдлийн бүтэц (жишээ нь C++ дэх set<> эсвэл priority_queue<>) ашиглана.
The following implementation returns the list of edges corresponding to the tree.
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$ оройтой бүрэн шошготой граф дахь тэлэх модны тоо дараахтай тэнцүү гэж өгүүлдэг:
Энэ томьёоны хэд хэдэн баталгаа бий. Прюферийн кодын үзэл баримтлалыг ашиглавал энэ мэдэгдэл ямар ч гайхшралгүйгээр гарч ирнэ.
Үнэндээ $[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$ нь оройнуудыг холбосны дараах мод дахь оройнуудын зэрэг байг. Зэргүүдийн нийлбэр нь ирмэгийн тооны хоёр дахин их байна:
Хэрэв орой $i$ нь $d_i$ зэрэгтэй бол тэр нь Прюферийн кодод $d_i - 1$ удаа гарч ирнэ. $k$ оройтой модны Прюферийн код $k-2$ урттай. Тиймээс тоо $i$ яг $d_i - 1$ удаа гарч ирэх $k-2$ тоотой кодыг сонгох аргын тоо нь олон гишүүнт коэффициент-тэй тэнцүү
Орой $i$-тэй зэргэлдээ ирмэг бүр хариуг $s_i$-ээр үржүүлдэг гэдэг баримтаас бид оройнуудын зэрэг $d_1, \dots, d_k$ гэж үзвэл хариуг авна:
Эцсийн хариуг авахын тулд бид үүнийг зэргүүдийг сонгох боломжит бүх аргаар нийлбэрлэх хэрэгтэй:
Одоогоор энэ нь үнэхээр аймшигтай хариу мэт харагдаж байгаа боловч бид дараахыг өгүүлдэг олон гишүүнт теорем-ыг ашиглаж болно:
Энэ нь аль хэдийн нэлээд төстэй харагдаж байна. Үүнийг ашиглахын тулд бид зөвхөн $e_i = d_i - 1$ гэж орлуулах хэрэгтэй:
Олон гишүүнт теоремыг хэрэглэсний дараа бид бодлогын хариу-г авна:
Санамсаргүйгээр энэ томьёо $k = 1$-ийн хувьд ч биелнэ.