离散数学第3章图的基本概念.ppt

1、修正机数学基础(上)第2编辑论，第3章图的基本概念，3.1图的概念和性质，一，图的定义和表示1。 图节点的集合v和边的集合e组成的秩序对称为图g.2。 有向图表、无向图表的各边缘为有向边缘的图表称为有向图表，各边缘为无向边缘的图表称为无向图表，不是的话称为混合图表。 三孤立点、零图表与其他节点没有关联的节点称为孤立点，全部由孤立点构成的图表称为零图表。 四。 边的重量具有相同起点和终点的边称为平行边，平行边的根数称为边的重量。 五n次图表具有n个节点的图表称为n次图表，具有n个节点和m条边的图表称为(n，m )图6。 将节点的度数图表即与节点v关联的边的数量(从循环开始数两边)称为该节点的度数

2、，记作deg(v )。 其中，以v为起点的边的数量为亮度deg (v )，以v为终点的边的数量为亮度deg-(v )，因此设图g中节点的最大最小频度为(g )、(g )、二、图的基本概念和握手定理1。 握手定理图g中所有节点的度数之和等于边数的2倍。 推论1在任何图中频数为奇数的节点数必定为偶数。 在推论2有向图中，所有节点的入度之和等于所有节点的出度之和。 例题1 :如果图g知道1次节点有1个、2次节点有2个、3次节点有3个、4次节点有4个，则g的边数为。 解：例题2 :图G=的话，下面的结论成立的是。 例题3 :简单连通无向图g设为12边，g设为1度节点2个，2度节点2个，4度节点3个，其

3、合适节点度数设为3，求g中有多少节点。 让我们制作一个符合这个条件的简单无向图。 假设g中存在x个节点，则解：三个节点是x-7。 根据握手定理，因为有解，所以g有9个节点。 满足条件的图如下：2. 简单图不包含平行边和环(自回路)的图称为简单图。 在一个简单的图中，任何节点的频率都不大于n-1。 这是判断一个频度系列是否能构成简单的图的主要依据。 三二部曲线图将无向曲线图g的节点集分为两个部分，如果各部分的任何一个节点之间边都没有连接，则将g称为二部曲线图。 您可以使用、4。 完全图将各节点对之间边相连的无向简图称为无向完全图，将各节点对之间相反的2边相连的有向简图称为有向完全图。 以具有n个

4、节点的无向完全图Kn的边数为例题4 :图g为具有n个节点的无向完全图时，g的边数为。 A) n(n-1) B) n(n 1) C) D )、c和5。 设正则图无向单纯图g中的各节点的频数为k，则g被称为k正则图。 六如果授权地图g的每个边缘都有表示长度的实数，则图g称为授权地图或网络。 图g把无向图称为无向权图，图g把有向图称为有向权图。 七补充图把由图g中的所有节点和构成完全图的应追加的边构成的图称为g的补充图，并标记。 例题5 :已知图表的节点集以及图表g和图表d的边集分别试制图表g和图表d，写出各节点的频数，回答图表g、图表d是简单图表还是多重图表的解： a d a d b c b c图

5、g图d、图g : 8、子图1。 是已知的图表G=，如果G=被称为g的子图表。 2 如果，将g称为g的真子图。 三如果，g被称为g的生成子图。 三、如果图的同调图g中的节点集v和图g中的节点集v具有一对一的对应关系，对应的边全部具有相同的重量，则记为g和g同调。 因此，两个图同体需要满足接合点数相同、边数相同、频数相同的接合点数相同的条件。 上述条件是两图同体所需的条件，但并不是充分的条件，即，即使两图满足上述条件，也未必是相同的结构。对一个图中的节点进行重新排序，当根据节点移动时进行任意弯曲，且可与另一个图完全重叠，则这两个图是相同的结构。 四、通路和回路1。 路径、电路在G=中，如果从节点v

6、0依次经由边缘和节点到达vn，则称为在v0和vn之间存在路径、或者v0和vn联系，表记为v0vn，如果是v0vn则表记为电路。 路径经过的边数称为路径长度。 2 简单路径，没有简单电路重复边的路径称为简单路径，没有重复边的路径称为简单路径。 三基本路径，将基本环没有重复节点的路径称为基本路径，将没有重复节点的环称为基本环。 例题6 :设g图，可知路径分别是简单路径、简单电路、基本路径、基本电路。 解：简单通道、基本通道、简单回路，但不是基本回路，而是简单回路、基本回路、简单通道，但不是基本通道。 在v1 v2 v5 v3 v4、一、连通性无向图g中，如果任何两个不同的结点都连通，则将g称为连通

7、图。 无向图中结点的连通关系具有自逆性、对称性、传递性，因此结点的连通关系是等价关系。 图g虽然不是连通图，但将g分为几个部分，如果各个部分连通，则将各个部分称为连通子图，将各个连通子图g称为g的连通分支。 在g中相互连通的节点必定在同一连通分支上。 设无向图g的连通分支数为W(G )。 3.2图的连通性，例如G: G虽然不是连通图，但可以分为3个连通分支。 是连通分支，是连通分支，是连通分支。 被称为v的区分。 有向连通图1。 强连通图、单侧连通图、弱连通图在有向简单图d中为(1)无论哪个节点间都能够到达，强连通图；(2)无论哪个节点间，如果任意一个节点能够到达另一个节点，则为单侧连通图两个

8、定理61的有向图足以是强连通性的要求是，在每个节点中至少存在一个通过的电路。 定理7在有向图中，其各个节点必定位于一个强分图上，并且只位于一个强分图上。 例题7 :可以构成va、b、c、d和强连通图的边集e、b、c、d和强连通图。 当节点集v (包括与v中的节点相关联的所有边)被删除时，在无方向连通图G=中获得子图GV。 如果v是不连通GV的最小点集，则v称为g的点集。 如果v中只有一个节点，则称为切割点。 换句话说，点剪辑是指，将图g从连通图变更为需要删除为非连通图的最小点集。 例如，由于g:v1删除后G1，v3删除后G2删除v1，v3后G3，所以v1不是点切割集合，W(G1)=1，v3是点

9、切割集合，另外，在切割点处，当给予w例题8 :图g时，图g的点切割集合成为。2。 边缘切割集处于无向连通图G=，如果删除边缘集e，则得到子图GE。 如果e是不连通GE的最小边集，则e称为g的边切集。 e中只有一条边称为剪切边。 换句话说，边缘切集是指从图g的连通图到非连通图需要删除的最小边缘集。 例如，删除g :边(v1，v2)之后的G1，(v1，v2)，(v2)，删除、3。 如果连通度(1)点连通度g是无向连通图，v是g的结点数最少的点分集或者GV是平凡图(孤立点)，则将v中的结点数称为g的点连通度。因此，(1)如果g是平凡的图，则V=，(2)如果g是完全的图，则除去n-1个节点成为平凡的图

10、，所以，(3)如果g中存在切割点，则(4)如果g是非连通图，则(2)边连通度g是无向连通图，e是g的边数最少的边分集因此，如果(1)g是平凡的图，则如果E=、(2)g存在切断，则如果(3)g是非连通图。 (3)之间的关系无向图g中，点连通度必须不比边连通度大，边连通度必须不比结点的最小度数大。 另一方面，如果无向图的相邻矩阵是无向图G=、|V|=n，则3.3图的矩阵表示设为与n次方矩阵A(G )中的表示相关联的边数。 例如，如图g所示，可知A(G )是对称矩阵。 主对角线上的要素表示各节点的自环数。 当有向图D=、|V|=n时，二、有向图的邻接矩阵表示距n次方矩阵A(D )中的表的边数。 从下面的例子可以看出，A(D )不再是对称矩阵。 矩阵中所有元素的和等于有向图中的边缘数。 第行元素的和表示节点的输出度，第列元素的和表示节点的输入度，图d :例题9 :到图d的相邻矩阵为A(D)=，其中e。 例题10 :有向图的邻接矩阵(D)=第中行的要素之和是中的节点。 三、校正后的边数在邻接矩阵A(D )中为长度为1的边数。 在A2(D )中，长度为2的边数。 一般来说，长度是的边数。 位置数表示距长度的边数。 对于A(D) A2(D) Ak(D )，表示长度小于等于k的边数的和，位置上的数量小于等于k的边数的