求问点双和边双的应用
  • 板块学术版
  • 楼主Cindy_Li
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/4/6 15:48
  • 上次更新2024/8/27 12:29:12
查看原帖
求问点双和边双的应用
565091
Cindy_Li楼主2024/4/6 15:48

本蒟蒻在做题的时候,经常会出现点双题用边双,边双题用点双等情况。

但是题解很少会讲为什么用点双/边双,而不是另一种。


例如下面这道题:

给定无向连通图,求所有在且仅在 11 个简单环中的边。

我的想法是把所有边双找出来,看边数是否等于点数。

但会出现反例:

正解是把所有点双找出来。


bdfs 发现大多数 blog 没有提及,小部分说的也比较模糊,例如“点双的限制比边双严格”,“点双一定是边双,边双是若干个点双拼起来”。

故求问:

  1. 有没有一些题目的普遍特点/条件,提示使用点双/边双?
  2. 有没有一些好的方法,能够判断使用点双/边双?
  3. 广义地,点双和边双在应用中,有什么区别?
2024/4/6 15:48
加载中...