第10章几种典型图 第10章几种典型图 0.1欧拉图 10.2哈密顿图 10.3平面图 10.4二分图 10.5例题选解 习题十 dBac
第10章 几种典型图 第10章 几种典型图 10.1 欧拉图 10.2 哈密顿图 10.3 平面图 10.4 二分图 10.5 例题选解 习 题 十
第10章几种典型图 10.1欧拉图 欧拉图的概念是瑞士数学家欧拉( Leonhardeuler) 在研究哥尼斯堡( K nigsberg)七桥问题时形成的。在 当时的哥尼斯堡城,有七座桥将普莱格尔( Pregel)河 中的两个小岛与河岸连接起来(见图10.1.1(a)) 当时那里的居民热衷于一个难题:一个散步者从任何 处陆地出发,怎样才能走遍每座桥一次且仅一次, 最后回到出发点?
第10章 几种典型图 10.1 欧 拉 图 欧拉图的概念是瑞士数学家欧拉（LeonhardEuler） 在研究哥尼斯堡（K nigsberg）七桥问题时形成的。在 当时的哥尼斯堡城，有七座桥将普莱格尔（Pregel）河 中的两个小岛与河岸连接起来（见图10.1.1（a））， 当时那里的居民热衷于一个难题：一个散步者从任何 一处陆地出发，怎样才能走遍每座桥一次且仅一次， 最后回到出发点？
第10章几种典型图 这个问题似乎不难,谁都想试着解决,但没有人 成功。人们的失败使欧拉猜想:也许这样的解是不存 在的,1936年他证明了自己的猜想。 为了证明这个问题无解,欧拉用A,B,C,D四个 顶点代表陆地,用连接两个顶点的一条弧线代表相应 的桥,从而得到一个由四个顶点、七条边组成的图 (见图10.1.1(b)),七桥问题便归结成:在图10.1.1 (b)所示的图中,从任何一点出发每条边走一次且仅 走一次的通路是否存在
第10章 几种典型图 这个问题似乎不难，谁都想试着解决，但没有人 成功。人们的失败使欧拉猜想：也许这样的解是不存 在的，1936年他证明了自己的猜想。 为了证明这个问题无解，欧拉用A，B，C，D四个 顶点代表陆地，用连接两个顶点的一条弧线代表相应 的桥，从而得到一个由四个顶点、七条边组成的图 （见图10.1.1（b）），七桥问题便归结成：在图10.1.1 （b）所示的图中，从任何一点出发每条边走一次且仅 走一次的通路是否存在
第10章几种典型图 欧拉指出,从某点出发再回到该点,那么中间经 过的顶点总有进入该点的一条边和走出该点的一条边, 而且路的起点与终点重合,因此,如果满足条件的路 存在,则图中每个顶点关联的边必为偶数。图10.1.1 (b)中每个顶点关联的边均是奇数,故七桥问题无解。 欧拉阐述七桥问题无解的论文通常被认为是图论这门 数学学科的起源
第10章 几种典型图 欧拉指出，从某点出发再回到该点，那么中间经 过的顶点总有进入该点的一条边和走出该点的一条边， 而且路的起点与终点重合，因此，如果满足条件的路 存在，则图中每个顶点关联的边必为偶数。图10.1.1 （b）中每个顶点关联的边均是奇数，故七桥问题无解。 欧拉阐述七桥问题无解的论文通常被认为是图论这门 数学学科的起源
第10章几种典型图 A A B 图10.1.1
第10章 几种典型图 图 10.1.1 B C (a) A D A B D C (b)