证明:一个无向连通图,将图中的节点复制。对于原图中所有的边(i,j)(i,j)(i,j),将iii连向jjj在复制图中的点,jjj连向iii在复制图中的点,得到的图至多有两个联通快。 例如:无向连通图
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