资源描述：
《14-离散数学基础_图论》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、离散数学基础：图论FundamentalsofDiscreteMathematics:GraphTheory周晓聪(isszxc@zsu.edu.cn)中山大学计算机科学系,广州5102752006年12月5日2版权所有，翻印必究目录目录i第一章图的基本概念11.1图的基本定义........................................11.2道路与回路.........................................41.3图的连通性.................
2、........................51.4欧拉图与哈密顿图.....................................81.5邻接矩阵与可达矩阵....................................9第二章树的基本概念112.1树的基本定义........................................112.2生成树............................................132.3根树.............
3、................................172.4哈夫曼树..........................................21第三章路径问题273.1最短路径..........................................273.2最小生成树.........................................323.3关键路径..........................................34第四章平面图与着
4、色394.1平面图及其性质.......................................394.2图的着色..........................................42第五章支配集、覆盖集、独立集与匹配455.1支配集、点独立集和点覆盖集...............................455.2边覆盖与匹配........................................475.3二部图中的匹配.....................
5、..................52参考文献55iii目录第一章图的基本概念这一章介绍有关图论的一些基本概念，包括无向图（有向图）的定义、顶点与边之间的关系、顶点度数、握手定理、图的道路与回路，以及特殊的道路与回路，如欧拉图、哈密顿图等。1.1图的基本定义定义1.1.1（无向）图(graph)是二元组G=(V,E)，其中V6=∅是图G的顶点(vertex)集，其中的元素称为G的顶点(vertex)，E是图G的边(edge)集，其中的元素称为G的边(edge)，且满足，对图G的任意边e∈E，都有且仅有两
6、个顶点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中的元素对这个图进行标记。例子1.1.2下面是一个图的直观表示：Ne4•vv1•NNp2NNNNppppNN
7、e7ppppNNNNppppe1e2e3pNpNpNpNe6ppppNNNNe5ppppNNNNppppNNNN••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,v4)}有时为了简便，我们可能在给出图的直观形式时，没有对其顶点和边进行标记，例如下
8、面是上面的图不带标记的形式：12第一章图的基本概念•NNNppp•NNNNppppNNNNppppNNNNppppppppNNNNppppNNNNppppNNNN•ppNN•这通常是因为我们这时只关注整个图的性质，不关心图的顶点或边的性质。如果需要关心某些顶点或边的性质时，我们也可能将某些顶点和边标记，而不标记其他顶点和边。定义1.1.3（有向）图(directedgraph)是二元组G=(V,E)，其中V6=∅是图D的顶点(
