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

树上的完美匹配

binary-tree graph tree algorithm

Chander Shivdasani · 技术社区 · 14 年前

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

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

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

2 回复 | 直到 14 年前

Colin 14 年前

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

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

user487478 14 年前

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

推荐文章

Ash · 递归列表拆分和索引

2 年前

Tuna ArÄ±yÃ¼rek · “结构对象*对象”和“对象*对象”之间的区别

3 年前

Zevvysan · 为什么我的打印函数之一要删除节点?

7 年前

codingBoy · 使用python进行二叉树修剪[postorder方法不起作用]

7 年前

user9573040 · 递归二叉树高度

7 年前

Dipesh Desai · 在二叉树haskell中搜索值

7 年前

Yuki.kuroshita · 从二叉树中删除节点及其所有子节点,而不使用树数据结构

7 年前

MMelvin0581 · 为什么在我的LinkedBinaryTree实现中只添加根目录

7 年前

Shuklaswag · 为什么我们要通过堆而不是二进制搜索树进行排序?

7 年前

ibrahim · “main”已停止工作-C++[开发人员++]

7 年前