听灌多(玄关)
  • 板块灌水区
  • 楼主rpyluogu
  • 当前回复6
  • 已保存回复6
  • 发布时间2024/7/27 10:17
  • 上次更新2024/7/27 11:33:01
查看原帖
听灌多(玄关)
1049376
rpyluogu楼主2024/7/27 10:17

证明:一个无向连通图,将图中的节点复制。对于原图中所有的边(i,j)(i,j),将ii连向jj在复制图中的点,jj连向ii在复制图中的点,得到的图至多有两个联通快。 例如:无向连通图

1 2
1 4
3 2
3 4  
  
将节点(1,2,3,4)复制为(5,6,7,8)
按题意建的新图为

1 6
5 2
1 8
4 5
3 6
2 7
3 8
4 7
2024/7/27 10:17
加载中...