趣味图论PDF电子书下载

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

一个关于联欢会的问题 1

图解这个问题 2

图的基本概念 3

图论世界 5

练习一 8

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

汉普顿公园的迷宫 9

盲目地“碰” 9

作图找一条通路 10

图的连通性 11

练习二 13

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

哪些图是一笔画？ 15

欧勒定理 17

一笔画处处有 18

练习三 21

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

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

完全图和一笔画 24

红色K3或蓝色K3 25

练习四 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