七桥问题
七桥问题是指十八世纪时欧洲一座都市的土地被一条河流脱离成两岸,都市中有七座桥划分连通两岸的差异区域,问题是一个人从随便一座桥开始,经由每座桥恰恰一次,能否回到起点。这个问题由欧拉在1735年提出,并乐成地给出体会答。
欧拉的解答是通过转化问题,将问题转化为一张图的欧拉回路问题。他把每座桥当做图的边,把每个区域当做图的极点,确立起一张图。对于这个图,欧拉证明晰只有所有极点的度数均为偶数时,才存在欧拉回路,即从随便一点出发,依次经由每条边恰恰一次,最终回到原点的一条路径。
对于七桥问题,欧拉通过对图的剖析,发现只有两个极点的度数为奇数,其余极点的度数为偶数,因此不存在欧拉回路,因此这个问题无解。这个结果在那时引起了伟大的惊动,欧拉因此被誉为图论之父。
解答
欧拉通过七桥问题,提出了图论中欧拉回路和欧拉路的看法,对图论的生长做出了伟大的孝顺。同时,他的解答也启示我们在解决问题时,可以通过转化问题,将其转化为一个相似但更为容易解答的问题。