资源描述：
《离散数学中的图论》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、离散数学基础：图论FundamentalsofDiscreteMathematics:GraphTheory周晓聪(isszxc@zsu.edu.cn)中山大学计算机科学系,广州5102752008年12月26日2版权所有，翻印必究目录目录i第一章图的基本概念11.1图的基本定义........................................11.2道路与回路.........................................61.3图的连通性.................
2、........................81.4邻接矩阵与可达矩阵....................................12第二章树的基本概念192.1树的基本定义........................................192.2生成树............................................212.3根树.............................................262.4哈夫曼树........
3、..................................31第三章路径问题413.1最短路径..........................................413.2最小生成树.........................................473.3关键路径..........................................49第四章平面图与着色554.1平面图及其性质.....................................
4、..554.2图的着色..........................................58第五章支配集、覆盖集、独立集和匹配655.1支配集、点独立集和点覆盖集...............................655.2边覆盖与匹配........................................675.3二部图中的匹配.......................................73第六章欧拉图与哈密顿图776.1欧拉图............
5、................................776.2哈密顿图..........................................77iii目录参考文献79第一章图的基本概念这一章介绍有关图论的一些基本概念，包括无向图（有向图）的定义、顶点与边之间的关系、顶点度数、握手定理、图的道路与回路等。1.1图的基本定义定义1.1.1（无向）图(graph)是二元组G=(V,E)，其中V6=∅是图G的顶点(vertex)集，其中的元素称为G的顶点(vertex)，E是图G的边(ed
6、ge)集，其中的元素称为G的边(edge)，且满足，对图G的任意边e∈E，都有且仅有两个顶点u,v∈V与e关联，称为e的两个端点，通常将e记为e=(u,v)或e=(u,v)。对于边e=(u,v)，这里u,v没有顺序，因此边e=(u,v)和e=(v,u)是同一条边。我们只考虑有限图G=(V,E)，也即其顶点集V和边集E都是有限集。上面的定义是说，在定义一个图的时候，要给出它的顶点集和边集，并说明每一条边的两个端点是那两个顶点。通常，我们可以对图作最为直观的理解，则画出这个图，并用V和E中的元素对这个图进行标记
7、。例子1.1.2下面是一个图的直观表示：Ne4•vv1•NNp2NNNNppppNNe7ppppNNNNppppe1e2e3pNpNpNpNe6ppppNNNNe5ppppNNNNppppNNNN••e9v3e8v4若将这个图用比较严格的数学形式给出来，则是：图G=(V,E)，其中：V={v1,v2,v3,v4}E={e1=(v1,v3),e2=(v1,v3),e3=(v1,v3),e4=(v1,v2),e5=(v1,v4),e6=(v2,v4),e7=(v2,v3),e8=(v3,v4),e9=(v4,v
8、4)}有时为了简便，我们可能在给出图的直观形式时，没有对其顶点和边进行标记，例如下面是上面的图不带标记的形式：12第一章图的基本概念•NNNppp•NNNNppppNNNNppppNNNNppppppppNNNNppppNNNNppppNNNN•ppNN•这通常是因为我们这时只关注整个图的性质，不关心图的顶点或边的性质。如果需要关心某些顶点或边的性质时，我们也可能将某些顶点和边标记，而不标记其他顶点和边。定义1.
