题目：
给定完全二分图，左右分别有n1和n2个顶点，求其生成数个数。
文章来源地址https://www.toymoban.com/news/detail-757883.html
文章来源：https://www.toymoban.com/news/detail-757883.html
知识补充1：完全二分图定义
对某完全图(V,E)，将其顶点V划分在两个集合A,B中。取边集E中任意一条边e，若其两个顶点一个在集合A，一个在集合B中，则该完全图为完全二分图。
知识补充2：完全二分图的常见证明方法---染色法
为证明一个图是二分图，通常采用染色法。即遍历二分图每一条边(A,B):
①假设A有颜色，若B无颜色：若A为黑色，则将B染成白色。若A为白色，则将B染成黑色。
②假设A有颜色，B有颜色：若A颜色=B颜色，则不是二分图。(无法将该边的两点划分到黑色-白色两个集合中)
知识补充3：prufer序列
一种完全图生成树的计数方法，可以将完全图生成树一一对应于一个prufer序列。则由序列的排列数，可由映射关系求解出生成树的个数。(具体暂时不介绍)
本体需要用到的prufer序列的结论：
①n节点无向图的无根树，对应序列长度为n-2
②当我们将图的叶子节点删除时，其邻节点会被加入到prufer序列当中。
本题题解：
1.已知n点完全图生成树的prufer序列长度都为n-2，且序列构造结束必然剩下两个点，这两个点形成一条边。
2.针对二分图而言，最后剩下的两个点必然一个为黑点，一个为白点。我们假设黑点集合为A(左边节点集合，大小为n1)，白点集合为B(右边节点集合，大小为n2)
3.对于一张已经染好黑白二色的二分图，我们现在求解一个prufer序列：按照prufer序列构造原则，我们每一步会删除一个叶子节点，同时加入其邻节点：
①若当前删除节点为黑节点，则prufer序列中会写入一个白色节点。
②若当前删除节点为白节点，则prufer序列中会写入一个黑色节点。
当prufer序列构造完成时：
总共要删除n1-1个黑色节点，所以prufer序列会存在n1-1个白色节点。
同理，总共要删除n2-1个白色节点，所以prufer序列会存在n2-1个黑色节点。
所以prufer序列会存在n1-1个白色节点。n2-1个黑色节点。
回顾集合大小定义
“黑点集合为A(左边节点集合，大小为n1)，白点集合为B(右边节点集合，大小为n2)”
因此，prufer序列的可能组合计数有：
①选出n1-1个白色节点：
②选出n2-1个黑色节点:
乘法原理，总共有:*
相关题目：洛谷[bzoj4766]文艺计算姬
到了这里，关于[Bijective-proof]完全二分图的生成树个数求解的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
