Cha*_*ani 1 algorithm tree binary-tree graph
我遇到了完美匹配的定义:一组边缘恰好触及每个节点一次.
但是,我并没有真正理解这个定义.有人可以给我一个任何这样的优势的例子.或者可以指向一些参考.
我试图谷歌,但它没有给我任何一个例子.
Col*_*lin 7
完美匹配集是图中任何一组边,其中图中的每个顶点都恰好被匹配集中的一个边触摸.如果考虑连接4个顶点的图形使图形类似于正方形,则有两个完美匹配集,即平行边对.由于所有顶点都被一对触摸了一次.如果你想到一个像三角形连接的3个顶点的图形,没有完美的匹配集,因为如果你采用任何一对边,一个顶点被触摸两次,但是一个边将总是错过一个顶点.
http://en.wikipedia.org/wiki/Perfect_matching
你的问题提到了一棵树,但树只是一种特殊的图形,所以它的工作方式仍然相同.
归档时间：
15 年，1 月 前
查看次数：
7037 次
最近记录：
15 年 前