引 / A B a △ D 图8.1a
引 言 A B 图8.1 a C D
引 言 当地的居民热衷于这样一个问题,一个漫 步者如何能够走过这七座桥。并且每座桥只能 走过一次,最终回到原出发地。尽管试验者很 多,但是都没有成功。 为了寻找答案,1736年欧拉将这个问题抽 象成图8.1b所示图形的一笔画问题。即能否从 某一点开始不重复地一笔画出这个图形。最终 回到原点。欧拉在他的论文中证明了这是不可 能的,因为这个图形中每一个顶点都与奇数条 边相连接,不可能将它一笔画出,这就是古典 图论中的第一个著名问题
7 引 言 当地的居民热衷于这样一个问题，一个漫 步者如何能够走过这七座桥，并且每座桥只能 走过一次，最终回到原出发地。尽管试验者很 多，但是都没有成功。 为了寻找答案，1736年欧拉将这个问题抽 象成图8.1b所示图形的一笔画问题。即能否从 某一点开始不重复地一笔画出这个图形，最终 回到原点。欧拉在他的论文中证明了这是不可 能的，因为这个图形中每一个顶点都与奇数条 边相连接，不可能将它一笔画出，这就是古典 图论中的第一个著名问题
引 B 图8.1b
8 引 言 图8.1 b A C D B
1图的基本概念与基本定理 在实际的生产和生活中,人们为了反映 事物之间的关系,常常在纸上用点和线来画 出各式各样的示意图。 例8.1:图8.2是我国北京、上海、重庆等 十四个城市之间的铁路交通图,这里用点表 示城市,用点与点之间的线表示城市之间的 铁路线。诸如此类还有城市中的市政管道囹 民用航空线图等等
9 在实际的生产和生活中，人们为了反映 事物之间的关系，常常在纸上用点和线来画 出各式各样的示意图。 例8.1:图8.2是我国北京、上海、重庆等 十四个城市之间的铁路交通图，这里用点表 示城市，用点与点之间的线表示城市之间的 铁路线。诸如此类还有城市中的市政管道图， 民用航空线图等等。 1.图的基本概念与基本定理
1图的基本概心与基本定理 北京 太原 天津 石家庄 塘沽 济南青岛 郑州 徐州连云港 重庆 武汉 南京 上海 图8.2
10 1.图的基本概念与基本定理 太原 重庆 武汉 南京 徐州 连云港 上海 郑州 石家庄 塘沽 济南 青岛 天津 北京 图8.2