离散数学(贾振华主编) 第七章 图论

《离散数学(贾振华主编) 第七章 图论》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第7章图论7.1图的基本概念7.2路与回路7.3图的矩阵表示7.4欧拉图7.5哈密尔顿图7.6树7.7二部图和平面图第7章图论7.1.1图的基本类型定义7.1所谓图G是一个三元组，G=，其中V(G)是一个非空的结点集合，E（G）是边的集合，φG是从边集合E到结点无序偶或有序偶集合上的函数。定义7.2如果两个结点之间有多条边（对于有向图，则有多条同方向的边），则称这些边为平行边，两相结点a，b间平行边的条数称为边的重数。含有平行边的图称为多重图，不含平行边和自回路的图称为简单图

2、。第7章图论7.1.2图中结点的度数1．无向图中结点的度数定义7.3设图G是无向图，v是图G中的结点，所有与v关联的边的条数，称为点v的度数，记作deg(v)。定理7.1设图G是具有n个点，m条边的无向图，其中结点集合为V={v1，v2，…，vn}，则第7章图论7.1.2图中结点的度数2．有向图中结点的度数定义7.5设图G是有向图，v是图G中的结点，以v为始点的有向边的条数称为v的出度，记个deg+(v)，以v为终点的有向边的条数称为v的入度，记作deg－(v)。定理7.2设有向图G具有n个结点，m条边

3、，其中结点构成的集合V={v1，v2，…，vn}，则有第7章图论7.1.3完全图1．无向完全图定义7.6在n阶无向图中，如果任意两个不同的结点之间都有一条边关联，则称此无向图为无向完全图，记作Kn。定理7.3n个结点的无向完全图Kn的边数是。第7章图论7.1.3完全图2．有向完全图定理7.4n个结点的有向完全图Kn的边数是n2。定义7.7在n阶有向图中，如果任意两个结点都有两条方向相反的有向边关联，且每一个结点都有自回路，则称此有向图为有向完全图。第7章图论7.1.3完全图3．竞赛图定义7.8设G为n阶

4、有向图，如果G的底图为无向完全图Kn，则称G为竞赛图。第7章图论7.1.4图的同构定义7.9设图G的点集为V，边集为E，图G′的点集为V′，边集为E′。如果存在着V到V′的双射函数f，使对任意的u，vV，(u，v)E（或E），当且仅当（f（u），f（v））E′（或E′），则称图G和G′同构，记作GG′。第7章图论7.1.5补图定义7.10设G=为任意的n阶无向简单图，则所有使G成为Kn添加的边和G的n个结点构成的图称为图G的补图，记作。定义7.11设G=

5、>是任意一个n阶无向图，V={v1，v2，…，vn}，称d（v1），d（v2），…，d（vn）为G的度数列。对于结点标定的无向图，它的度数列是唯一的。反之，对于给定的非负整数列d=（d1，d2，…，dn），若存在以V={v1，v2，…，vn}为结点n阶无向图G，使得d（vi）=di，则称d是可图化的。特别地，若得到的图是简单图，则称d是可简单图化的。第7章图论7.1.5补图定理7.5设非负整数列d=（d1，d2，…，dn），当且仅当为偶数时，d是可图化的。定理7.6设非负整数列d=（d1，d2，…，dn

6、），（n-1）≥d1≥d2≥…≥dn≥0，则d是可简单图化的，当且仅当对于每个整数r，1≤r≤（n-1），≤r（r-1）+且为偶数。定理7.7设非负整数列d=（d1，d2，…，dn），（n-1）≥d1≥d2≥…≥dn≥0，则d是可简单化的当且仅当d′=（-1，-1，…，-1，，…，）。第7章图论7.1.6子图定义7.12设G=和G=是两个图，（1）若V'V且E'E，则称G'是G的子图；（2）若G'是G的子图，但V'≠V或E'≠E，则称G'是G的真子图；（3）若G‘是G的子图，

7、且V’=V，则称G‘是G的生成子图或支撑子图。第7章图论7.2路与回路7.2.1通路与回路定义7.13在无向图（或有向图）G=中，设v0，v1，…，vn∈V，e0，e1，…，en∈E，其中ei是关联于结点vi-1，vi的边，交替序列v0e0v1e1…en-1vn称为联结v0到vn的通路或路。v0和vn分别称为通路的起点和终点，通路中所含边的条数称为该通路的长度。如果通路中的始点与终点相同，则称这条路为回路。第7章图论7.2路与回路7.2.1通路与回路定理7.8在n阶无向图中，如果存在一条从vi

8、到vj的通路，则从vi到vj必有一条长度不大于n-1的基本通路。定理7.9在n阶无向图中，如果存在一条通过vi的回路，则必有一条长度不大于n的通过vi的基本回路。第7章图论7.2路与回路7.2.2图的连通性1．无向图的连通性定义7.14设图G是无向图，u和v是图G中的两个结点，如果u和v之间有通路，则称u，v是连通的，并规定u与自身是连通的。定义7.15若图G是平凡图或G中任意两点都是连通的，则称图G为连通图，否则称G为非连通图或分离图。第