图论导引

图书标准信息

• 作者 查特朗
• 出版社 人民邮电出版社
• 出版时间 2006-06
• 版次 1
• ISBN 9787115148346
• 定价 49.00元
• 装帧 平装
• 开本 其他
• 纸张 胶版纸
• 页数 435页
• 字数 460千字

【内容简介】

　　本书介绍了图论的常用主题，同时也包含一些尚需进一步研究或未解决的议题，用于激发学生的创新能力。全书共分13章，前3章介绍一些基础知识，后面章节介绍了树、连通性、可遍历性、子图、匹配和因子分解、可平面性、图的着色、拉姆齐数、距离及控制等内容。本书内容全面，证明与应用实例并举，还给出了证明技巧，书的最后提供了奇数题号的解答或提示。

  本书可作为本科生一学期课程教材，也可供图论爱好者自学使用。

【目录】

1.　Introduction

1.1.　Graphs and Graph Models  1

1.2.　Connected Graphs  9

1.3.　Common Classes of Graphs  19

1.4.　Multigraphs and Digraphs  26

2.　Degrees

2.1.　The Degree of a Vertex  31

2.2.　Regular Graphs  38

2.3.　Degree Sequences  43

2.4.　Excursion:Graphs and Matrices  48

2.5.　Exploration:Irregular Graphs  50

3.　Isomorphic Graphs

3.1.　The Definiition of Isomorphism  55

3.2.　Isomorphism as a Relation  63

3.3.　Excursion:Graphs and Groups  66

3.4.　Excursion:Reconstruction and Solvability  76

4.　Trees

4.1.　Bridges  85

4.2.　Trees  87

4.3.　The Minimum Spanning Tree Problem  94

4.4.　Excursion:The Number of Spanning Trees  101

5.　Connectivity

5.1.　Cut-Vertices  107

5.2.　Blocks  111

5.3.　Connectivity  115

5.4.　Menger's Theorem  124

5.5.　Exploration:Geodetic Sets  130

6.　Traversability

6.1.　Eulerian Graphs  133

6.2.　Hamiltonian Graphs  140

6.3.　Exploration:Hamiltonian Walks and Numbers  152

6.4.　Excursion:The Early Books of Graph Theory  156

7.　Digraphs

7.1.　Strong Digraphs  161

7.2.　Tournaments  169

7.3.　Excursion:Decision-Making  176

7.4.　Exploration:Wine Bottle Problems  180

8.　Matchings and Factorization

8.1.　Matchings  183

8.2.　Factorization  194

8.3.　Decompositions and Graceful Labelings  209

8.4.　Excursion:Instant Insanity  214

8.5.　Excursion:The Petersen Graph  219

8.6.　Exploration:γ-Labelings of Graphs  224

9.　Planarity

9.1.　Planar Graphs  227

9.2.　Embedding Graphs on Surfaces  241

9.3.　Excursion:Graph Minors  249

9.4.　Exploration:Embedding Graphs in Graphs  253

10.　Coloring

10.1.　The Four Color Problem  259

10.2.　Vertex Coloring  267

10.3.　Edge Coloring  280

10.4.　Excursion:The Heawood Map Coloring Theorem  288

10.5.　Exploration:Local Coloring  293

11.　Ramsey Numbers

11.1.　The Ramsey Number of Graphs  297

11.2.　Turan's Theorem  307

11.3.　Exploration:Rainbow Ramsey Numbers  314

11.4.　Excursion:Erdos Numbers  321

12.　Distance

12.1.　The Center of a Graph  327

12.2.　Distant Vertices  333

12.3.　Excursion:Locating Numbers  341

12.4.　Excursion:Detour and Directed Distance  346

12.5.　Exploration:Channel Assignment  351

12.6.　Exploration:Distance Between Graphs  357

13.　Domination

13.1.　The Domination Number of a Graph  361

13.2.　Exploration:Stratification  372

13.3.　Exploration:Lights Out  377

13.4.　Excursion:And Still It Grows More Colorful  381

Solutions and Hints for Odd-Numbered Exercises  397

References  425

Index of Names  437

Index of Mathematical Terms  440

List of Symbols  447