代码之家 › 专栏 › 技术社区 › Chander Shivdasani

树上的完美匹配

binary-tree graph tree algorithm

Chander Shivdasani · 技术社区 · 15 年前

我遇到了一个完美匹配的定义:一组只接触每个节点一次的边。

然而,我并没有真正理解这个定义。有人能给我举个这样的例子吗。或者是指给我一些参考。

我试着用谷歌搜索,但没有给我任何例子。

2 回复 | 直到 15 年前

Colin 15 年前

完美匹配集是图中的任意一组边,图中的每个顶点都恰好被匹配集中的一条边所接触。如果考虑一个有4个顶点连接的图,使其类似于一个正方形,则有两个完美的匹配集,即平行边对。因为所有的顶点都被任意一对精确地接触一次。如果你想一个有三个顶点像三角形一样连接的图,就没有完美的匹配集,因为如果你取任何一对边,一个顶点会被触摸两次,但是一条边总是会漏掉一个顶点。

http://en.wikipedia.org/wiki/Perfect_matching

user487478 15 年前

N边=>2*N个顶点。因为没有顶点一旦被触碰就不应该再被触碰。

推荐文章

Rosie Lomas · 在ggplot中设置数字刻度

3 年前

Mahin Rahman · 我的培训和测试图表保持不变,有人能帮我解释一下,或者解释一下我哪里出错了?

4 年前

nedlaback · 在O(V+E)图中寻找瓶颈边

8 年前

Skampak · R visNetwork:创建新类型的边

8 年前

Habil Ganbarli · 在完整图上进行MST聚类(用于余弦相似性)

8 年前

Vaibhav · 在r Shinny中的Visnetwork中撤消单击事件

8 年前

Anuja · 长度l在R中的最短路径

8 年前

Cbhihe · 优化Neo4j查询,有条件地创建新关系

8 年前

fghjk · 绘制轨迹(python)

8 年前

LBerger · 计算图形图像中的名称使用(TensorBoard)

8 年前