2009-8-20
1
第八章 图的基本概念图是一类相当广泛的实际问题的数学模型,有着极其丰富的内容,是数据结构等课程的先修内容,学习时应掌握好图论的基本概念,基本方法,基本算法；善于把实际问题抽象为图论的问题,然后用图论的方法解决问题,
返回首页
2009-8-20
2
第一节 图的概念
本节介绍图的一些最常用的概念,主要有,
无向图,有向图,边,顶点 (或结点,点 ),弧
(或有向边 ),顶点集,边集,n阶图,有限图,关联,多重图,简单图,完全图,二分图 (或偶图 ),完全二分图,母图,子图,支撑子图 (或生成子图 ),导出子图,补图,
图的同构,入度,出度,度,孤立点等,
主要定理,握手定理,
返回本章首页
2009-8-20
3
第二节 路与回路 (1)
本节介绍图中有关路的基本概念，同时作为路在权图中的应用，我们给出求权图最短路的迪克斯特拉算法,
1.基本概念有,路,路的起点,路的终点,路的长度,开路,闭路,简单路,回路,基本路,圈,连通,连通分支,连通图,两点间的距离,可达,强连通图,单向连通图,弱连通图,权图,权,迪克斯特拉算法等；
返回本章首页
2009-8-20
4
第二节 路与回路 (2)
2.主要结论,设 G=(V,E)是图，且 |V|=n,
若存在结点 u到 v的路，则必存在 u到 v的长度不超过 n-1的路,
3.算法,迪克斯特拉 (Dijkstra)算法,迪克斯特拉算法是图论中最基本的算法,应很好地掌握,
返回本章首页
2009-8-20
5
第三节 矩阵与图
本节主要考虑三种矩阵，即邻接矩阵，
可达矩阵与关联矩阵,邻接矩阵反映的是顶点与顶点之间的关系；可达矩阵反映了图的联通情况；关联矩阵反映的是顶点与边（弧）的关系,分有向图与无向图来讨论,
返回本章首页
2009-8-20
6
第四节 关系与图
在讨论集合的二元关系时，我们就给出了关系的图形表示，即关系图,这里用图论的方法给出关系图的严格定义,
关系中的很多性质可以在关系图上反映出来,可以通过图来研究关系,也可以通过关系来研究图,
返回本章首页
2009-8-20
7
第五节 欧拉图 (1)
欧拉图是一类非常著名的图，之所以如此，不仅是因为欧拉是图论的创始人，
更主要是欧拉图具有对边（弧）的,遍历性,,
1.概念有,欧拉路,欧拉图,半欧拉路,半欧拉图,割边等；
返回本章首页
2009-8-20
8
第五节 欧拉图 (2)
2.结论有,(1)无向连通图 G是欧拉图的充要条件是 G中每个顶点的度均为偶数；
(2)设 G是无向连通图，则 G是半欧拉图的充要条件是 G恰含有两个奇数度点,
3.算法,在 欧拉图中找欧拉路的 Fleury算法,
返回本章首页
2009-8-20
9
第六节 哈密尔顿图 (1)
哈密尔顿图是一类实际背景很强的图论模型,与欧拉图不同，哈密尔顿图感兴趣的是遍历图中的诸顶点,
1.主要概念,哈密尔顿路,半哈密尔顿图,
哈密尔顿回路,哈密尔顿图,图的闭包；
2.主要结论,哈密顿图的判定，至今也还没有令人满意地结果,下面的一些哈密顿图的结果都只是充分条件或必要条件，
而非充要条件,
返回本章首页
2009-8-20
10
第六节 哈密尔顿图 (2)
(1)设 G=(V,E)是哈密尔顿图,则对 V的任意非空子集 S均有 W(G-S) ≦ |S|,其中 G-
S表示在 G中删除 S中的点以及以 S为端点的边后所构成的图； W(G-S)表示 G-S的连通分支数 ;
(2)设 G=(V,E)是 n阶无向简单图,若对 G中任意不相邻的顶点 u,v都有 d(u)+d(v)
≧ n-1,则 G存在哈密尔顿路,因此 G是半哈密尔顿图；
(3)设 G是 n阶简单图,则是哈密尔顿图当且仅当其闭包是哈密尔顿图,
返回本章首页
2009-8-20
11
第七节 二分图 (1)
二分图也是一类实际背景很强的图论模型,在 § 1已给出了二分图的定义,二分图与图的匹配有密切关系,
1.基本概念,二分图,匹配,最大匹配,饱和,
非饱和,完美匹配,交错路,可扩路,邻集等 ;
2.结论,(1)设 G是无向简单图,则 G是二分图的充要条件是它的所有回路的长度为偶数 ;
返回本章首页
2009-8-20
12
第七节 二分图 (2)
(2)图 G的匹配 M是最大匹配当且仅当 G不含
M的可扩路 ;
(3)设 G=(V,E)为二分图,顶点划分为 V= V1
∪ V 2,则 G存在饱和 V1的每个顶点匹配的充要条件是对任何 S V1均有
|N(S)|≧ |S|；
3.算法：匈牙利算法，解决了二分图的匹配问题。
返回本章首页
2009-8-20
13
本章小结
本章我们仅讨论无向图与有向图、我们首先给出图的一些基本概念和术语，比如，路、回路、连通性、邻接矩阵、关联矩阵等；给出了图论中的一些常用算法（如迪克斯特拉算法,Fleury算法等），在此基础上讨论了三类特殊的图，
即欧拉图、哈密顿图、二分图等，此三类图均有很强的实际应用背景,
返回本章首页
1
第八章 图的基本概念图是一类相当广泛的实际问题的数学模型,有着极其丰富的内容,是数据结构等课程的先修内容,学习时应掌握好图论的基本概念,基本方法,基本算法；善于把实际问题抽象为图论的问题,然后用图论的方法解决问题,
返回首页
2009-8-20
2
第一节 图的概念
本节介绍图的一些最常用的概念,主要有,
无向图,有向图,边,顶点 (或结点,点 ),弧
(或有向边 ),顶点集,边集,n阶图,有限图,关联,多重图,简单图,完全图,二分图 (或偶图 ),完全二分图,母图,子图,支撑子图 (或生成子图 ),导出子图,补图,
图的同构,入度,出度,度,孤立点等,
主要定理,握手定理,
返回本章首页
2009-8-20
3
第二节 路与回路 (1)
本节介绍图中有关路的基本概念，同时作为路在权图中的应用，我们给出求权图最短路的迪克斯特拉算法,
1.基本概念有,路,路的起点,路的终点,路的长度,开路,闭路,简单路,回路,基本路,圈,连通,连通分支,连通图,两点间的距离,可达,强连通图,单向连通图,弱连通图,权图,权,迪克斯特拉算法等；
返回本章首页
2009-8-20
4
第二节 路与回路 (2)
2.主要结论,设 G=(V,E)是图，且 |V|=n,
若存在结点 u到 v的路，则必存在 u到 v的长度不超过 n-1的路,
3.算法,迪克斯特拉 (Dijkstra)算法,迪克斯特拉算法是图论中最基本的算法,应很好地掌握,
返回本章首页
2009-8-20
5
第三节 矩阵与图
本节主要考虑三种矩阵，即邻接矩阵，
可达矩阵与关联矩阵,邻接矩阵反映的是顶点与顶点之间的关系；可达矩阵反映了图的联通情况；关联矩阵反映的是顶点与边（弧）的关系,分有向图与无向图来讨论,
返回本章首页
2009-8-20
6
第四节 关系与图
在讨论集合的二元关系时，我们就给出了关系的图形表示，即关系图,这里用图论的方法给出关系图的严格定义,
关系中的很多性质可以在关系图上反映出来,可以通过图来研究关系,也可以通过关系来研究图,
返回本章首页
2009-8-20
7
第五节 欧拉图 (1)
欧拉图是一类非常著名的图，之所以如此，不仅是因为欧拉是图论的创始人，
更主要是欧拉图具有对边（弧）的,遍历性,,
1.概念有,欧拉路,欧拉图,半欧拉路,半欧拉图,割边等；
返回本章首页
2009-8-20
8
第五节 欧拉图 (2)
2.结论有,(1)无向连通图 G是欧拉图的充要条件是 G中每个顶点的度均为偶数；
(2)设 G是无向连通图，则 G是半欧拉图的充要条件是 G恰含有两个奇数度点,
3.算法,在 欧拉图中找欧拉路的 Fleury算法,
返回本章首页
2009-8-20
9
第六节 哈密尔顿图 (1)
哈密尔顿图是一类实际背景很强的图论模型,与欧拉图不同，哈密尔顿图感兴趣的是遍历图中的诸顶点,
1.主要概念,哈密尔顿路,半哈密尔顿图,
哈密尔顿回路,哈密尔顿图,图的闭包；
2.主要结论,哈密顿图的判定，至今也还没有令人满意地结果,下面的一些哈密顿图的结果都只是充分条件或必要条件，
而非充要条件,
返回本章首页
2009-8-20
10
第六节 哈密尔顿图 (2)
(1)设 G=(V,E)是哈密尔顿图,则对 V的任意非空子集 S均有 W(G-S) ≦ |S|,其中 G-
S表示在 G中删除 S中的点以及以 S为端点的边后所构成的图； W(G-S)表示 G-S的连通分支数 ;
(2)设 G=(V,E)是 n阶无向简单图,若对 G中任意不相邻的顶点 u,v都有 d(u)+d(v)
≧ n-1,则 G存在哈密尔顿路,因此 G是半哈密尔顿图；
(3)设 G是 n阶简单图,则是哈密尔顿图当且仅当其闭包是哈密尔顿图,
返回本章首页
2009-8-20
11
第七节 二分图 (1)
二分图也是一类实际背景很强的图论模型,在 § 1已给出了二分图的定义,二分图与图的匹配有密切关系,
1.基本概念,二分图,匹配,最大匹配,饱和,
非饱和,完美匹配,交错路,可扩路,邻集等 ;
2.结论,(1)设 G是无向简单图,则 G是二分图的充要条件是它的所有回路的长度为偶数 ;
返回本章首页
2009-8-20
12
第七节 二分图 (2)
(2)图 G的匹配 M是最大匹配当且仅当 G不含
M的可扩路 ;
(3)设 G=(V,E)为二分图,顶点划分为 V= V1
∪ V 2,则 G存在饱和 V1的每个顶点匹配的充要条件是对任何 S V1均有
|N(S)|≧ |S|；
3.算法：匈牙利算法，解决了二分图的匹配问题。
返回本章首页
2009-8-20
13
本章小结
本章我们仅讨论无向图与有向图、我们首先给出图的一些基本概念和术语，比如，路、回路、连通性、邻接矩阵、关联矩阵等；给出了图论中的一些常用算法（如迪克斯特拉算法,Fleury算法等），在此基础上讨论了三类特殊的图，
即欧拉图、哈密顿图、二分图等，此三类图均有很强的实际应用背景,
返回本章首页
