《趣味图论》求取 ⇩

一 欢乐的春节联欢会——图的基本概念1

一个关于联欢会的问题1

图解这个问题2

图的基本概念3

图论世界5

练习一8

二 怎样走出迷宫？——图的通路和连通性9

汉普顿公园的迷宫9

盲目地“碰”9

作图找一条通路10

图的连通性11

练习二13

三 一笔画的奥妙——欧勒通路和回路15

哪些图是一笔画？15

欧勒定理17

一笔画处处有18

练习三21

四 十大城市间的微波中继干线——完全图和它的应用23

有多少条微波中继干线？23

完全图和一笔画24

红色K3或蓝色K325

练习四27

五 环游世界的路线——哈密顿通路和回路29

貌异质同的几个问题29

哈密顿通路和回路30

环游路线——直接找32

练习五33

六 色彩缤纷的双色布 ——哈密顿能（回）路的判断方法35

两条判断定理35

马跳日——交错标记法37

练习六40

七 哪个苹果重？——有向图简介43

哪个苹果重？43

有向图和无向图44

三种连通性46

练习七47

八 这些图相同吗？——图的同构49

相同，还是不相同？49

怎样判断图的同构50

练习八54

九 千变万化的关系——图所表示的几种重要关系56

自返关系56

对称关系59

传递关系61

练习九63

十 富有生命力的“树”——“树”的基本概念65

一次乒乓球选拔赛65

树的家族67

行遍一棵树69

练习十73

十一 千姿百态的“树”——“树”的应用76

最优二元树76

最小支撑树79

概率树81

练习十一82

十二 印刷电路板布线问题——平面图84

这些线能布在同一层板上吗？84

欧勒公式87

库拉托夫斯基定理90

练习十二91

十三 著名的“四色猜想”难题——平面图的着色93

图的着色93

平面图的对偶图96

从猜想到定理97

练习十三102

十四 在图上找捷径——最短路径问题104

从一个城市到另一个城市的最短路程104

一种求最短路径的算法105

巡回售货员的最短回路109

练习十四111

十五 智力游戏中的图——偶图和对策113

农民过河的古题113

课程巧安排117

对弈中的制胜之道120

练习十五125

练习题答案127

后记154