历经517的拷打,我在这道题前低下了头
  • 板块学术版
  • 楼主cold_dzy_light
  • 当前回复4
  • 已保存回复4
  • 发布时间2023/7/25 19:28
  • 上次更新2023/11/3 07:40:43
查看原帖
历经517的拷打,我在这道题前低下了头
793577
cold_dzy_light楼主2023/7/25 19:28

给出一个n 个顶点和 2*(n-1) 条边组成的有向图,对于图上的每条有向边 (u, v) 都存在一条与其相反的边 (v, u)。换句话说这个图由一颗树衍生而出,是把树上的每一条边都被拆成了两条方向相反的边。定义弦为两条相邻的边,且满足其中一条边的终点恰是另一条边的起点。例如对于两条边 (x, y)​ 和 (y, w)​,这两条边就是一条弦。边 (u, v)​ 和边 (v, u)​ 也是一条弦。若两个弦有公共的边,那就称这两个弦相交,否则为不相交。例如对于两条弦{(a,b),(b,c)}​ 和 {(b,c),(c,d)}​ 就是相交的,因为共享了(b,c)​ 这条边。 显然对于一个由树衍生出的图来说,一定可以把图上所有的边分为n​ 条互不相交的弦。 现在这个图上因为某些原因缺失了2k 条边,这样就只剩下 m=2(n-1)-2*k 条边了,你能否将图上剩余的边分为 m/2 条互不相交的弦?

2023/7/25 19:28
加载中...