一些特殊的图.ppt

《一些特殊的图.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第八章一些特殊的图§8.1二部图§8.2欧拉图§8.3哈密尔顿图§8.4平面图§8.5树7/28/20211离散数学二部图(偶图)：若无向图G=的顶点集V能划分成两个子集V1和V2，使得G中任何一条边的两个端点一个属于V1，另一个属于V2，则称G为二部图(偶图)。V1,V2称为互补顶点子集。§8.1二部图完全二部图(完全偶图)：若V1中任一顶点与V2中每个顶点均有且仅有一条边相关联，则称G为完全二部图(完全偶图)。若

2、V1

3、=n，

4、V2

5、=m，则记完全二部图G为Kn,m7/28/20212离散数学二部图（续

6、）K2,3K3,3一个无向图G=是二部图当且仅当G中无奇数长度的回路。二部图判定定理7/28/20213离散数学二部图（续）例1：判断下列图是否为二部图。v4v3v2v1v5v6v7v8同构于v4v3v2v1v5v6同构于v6v4v3v2v1v5v7v8v4v3v2v1v5v67/28/20214离散数学§8.2欧拉图哥尼斯堡七桥问题7/28/20215离散数学欧拉通路(欧拉回路)：经过图中每条边一次且仅一次并且行遍每个顶点的通路(回路)，称为欧拉通路(欧拉回路)。欧拉图：存在欧拉回路的图。7/28/202

7、16离散数学欧拉图（续）(1)无向图G具有欧拉通路当且仅当G是连通图且有零个或两个奇数度顶点。欧拉图的判定定理：(2)无向图G是欧拉图(具有欧拉回路)当且仅当G是连通图且所有顶点的度数全为偶数。7/28/20217离散数学欧拉图（续）欧拉图的判定定理：(4)有向图D是欧拉图(具有欧拉回路)当且仅当D是连通图，且所有顶点的入度等于出度。(3)有向图D具有欧拉通路当且仅当D是连通图，且除了两个顶点外，其余顶点的入度均等于出度。这两个特殊的顶点中，一个顶点的入度比出度大1，另一个顶点的出度比入度大1。7/28/20218离

8、散数学欧拉图（续）例2：判断下列图是否为欧拉图。fdbaecghijdbaecdbaec是欧拉图不是欧拉图，但有欧拉通路是欧拉图7/28/20219离散数学§8.3哈密尔顿图哈密尔顿通路(哈密尔顿回路)：经过图中每个顶点一次且仅一次的通路(回路)，称为哈密尔顿通路(哈密尔顿回路)。哈密尔顿图：存在哈密尔顿回路的图。dbaecdbaecdbaecf7/28/202110离散数学设G是n(n3)阶无向简单图，(1)若G中任何一对不相邻的顶点的度数之和都大于等于n-1，则G中存在哈密尔顿通路。(2)若G中任何一对不相邻的

9、顶点的度数之和都大于等于n，则G是哈密尔顿图。哈密尔顿图设无向图G=是哈密尔顿图，V1是V的任意非空子集，则p(G–V1)

10、V1

11、。其中，p(G–V1)为从G中删除V1(删除V1中各顶点及其关联的边)后所得子图的连通分支数。必要条件充分条件7/28/202111离散数学哈密尔顿图例3：判断下列图是否为哈密尔顿图。dbaecfV1={a}p(G–V1)=2>

12、V1

13、=1不满足必要条件；V1={a，b}p(G–V1)=3>

14、V1

15、=2不满足必要条件；ab7/28/202112离散数学§8.4平面图平面图：图G

16、若能够以除顶点外没有边交叉的方式画在平面上，则称G为平面图。K5K3,3一、平面图的基本概念及性质画出的没有边交叉的图称为G的一个平面嵌入。7/28/202113离散数学一、平面图的基本概念及性质（续）面：设G是一个连通的平面图(G的某个平面嵌入)，G的边将G所在的平面划分成若干个区域，每个区域称为的一个面。其中面积无限的区域称为无限面(或外部面)，记R0，面积有限的区域称为有限面(或内部面)。包围每个面的所有边所构成的回路称为该面的边界。边界的长度称为该面的次数，R的次数记为deg(R)。对于含k(k2)个连通分

17、支的非连通的平面图，其无限面R0的边界则由k个回路围成。7/28/202114离散数学一、平面图的基本概念及性质（续）v1v2v4v3v5v6R0R1R2v1v2v4v3v5R0R1R2R3v1v2v4v3v5R0R1R2v6v7deg(R1)=3deg(R1)=4deg(R1)=4deg(R2)=3deg(R0)=8deg(R2)=3deg(R3)=1deg(R0)=6deg(R2)=3deg(R0)=77/28/202115离散数学一、平面图的基本概念及性质（续）定理在一个平面图G中，所有面的次数之和都等于边数m

18、的2倍。即，其中r为面数。7/28/202116离散数学设G是任意的连通的平面图，则有n–m+r=2成立。其中：n为顶点数，m为边数，r为面数。欧拉公式推广设G是任意的连通分支为p(p2)的平面图，则有n–m+r=p+1成立。其中：n为顶点数，m为边数，r为面数。一、平面图的基本概念及性质（续）7/28/202117离散数学§8.5树树：连通