图论-图的基本概念

图论－图的基本概念教师：孙继荣电话：87768609Email:图论－图的基本概念教学要求理解图的概念：结点、边、有向图，无向图、图的同构、简单图、完全图、结点的度数、子图、边的重数和平行边等理解握手定理了解通路与回路概念：通路(简单通路、初级通路和复杂通路)，回路(简单回路、初级回路和复杂回路)，会求通路和回路的长度了解无向图的连通性，会求无向图的连通分支。了解点割集、割点、边割集、割边、点连通度、边连通度等概念了解有向图的强连通强性；会判别其类型了解(有向图、无向图)关联矩阵、(无向图)相邻矩阵和(有向图)邻接矩阵的概念，掌握构造方法及其应用。知道带权图、最短通路概念，知道关键路径概念

计算机数学基础－孙继荣图论－图的基本概念学习内容：

图的概念

（图的表示，有向图、无向图、度、同构）

图的矩阵表示

（邻接矩阵，关联矩阵）

计算机数学基础－孙继荣图论－图的基本概念图的基本概念图是指某些具体的事物以及这些事物之间的联系图是一个有序对<V，E>，V是结点集，E是边集，当V,E有限时，<V,E>称为有限图；否则称无限图.无向边,与无序结点(v,u)相关联的边有向边，与有序结点<v,u>相关联的边.无向图，每条边都是无向边的图，记作G＝<V,E>;每条边都是有向边的图，记作D＝<V,E>.混合图，既有有向边，也有无向边的图.计算机数学基础－孙继荣图论－图的基本概念图的基本概念平凡图，仅有一个结点的图；零图（空图）：边集为空集的图<V,>，即仅有结点的图.自回路(环)，关联于同一个结点的边.

无向平行边，联结相同两个结点的多于1条的无向边；有向平行边，联结两个结点之间的多于1条且方向相同的有向边.

简单图，不含平行边和自回路的图.计算机数学基础－孙继荣图论－图的基本概念图的基本概念在无向图G＝<V,E>中，与结点v(V)关联的边数，即为结点度数deg(v)或d(v).；有向图G＝<V,E>中，，以结点v为始点的变的条数为该点的出度，记作deg+(v);以结点v为终点的边为该点的入度，记作deg－(v)；结点v的出度和入度之和为度数.最大度数，(G)＝max{d(v)vV}；

最小度数，(G)=min{d(v)vV}计算机数学基础－孙继荣图论－图的基本概念图的基本概念补图G=<V,E>，设G＝<V,E>,以V为结点集，以使G成为完全图所添加的边为边集E的图，就是图G的补图G

，即<V,EE>是完全图,其中EE＝.图的同构，设G1=<V1,E1>和G2=<V2,E2>,存在双射f：V1V2，(vi,vj)E1,当且仅当(f(vi),f(vj))E2，且(vi,vj)与(f(vi),f(vj))的重数相同.则G1≌G2.同构充分条件：建立两个图的对应关系，这个关系是双射函数.同构必要条件：①结点数相同；②边数相同；③度数相同的结点个数相同.

计算机数学基础－孙继荣图论－图的基本概念图的基本概念握手定理:结点度数之和为边数的两倍设G=<V，E>，有在有向图图D＝<V,E>中，奇数度结点的个数为偶数个.如果一个图中只有两个奇数度节点，则这两个节点相连通。计算机数学基础－孙继荣图论－图的基本概念通路、回路、图的连通性通路与通路的长度，设图G＝<V，E>，V＝{v0,v1,…,vn},E={e1,e2,…,em},结点与边的交替序列v0e1v1e2…vi-1eivi,成为结点v0到结点vi的通路.v0,vi是通路的起点和终点.通路中边的数目就是通路的长度.回路，起点和终点重合的通路.简单通路(回路)：边不重复的通路(回路).初级通路(回路)：结点不重复的通路(回路).复杂通路(回路)：边有重复的通路(回路).计算机数学基础－孙继荣图论－图的基本概念通路、回路、图的连通性连通与连通图，无向图G中，结点u,v存在通路，那么u,v是连通的，G中任意结点u,v都是连通的，G是连通图.连通分支，设G＝<V,E>，V的连通等价类V1，V2，…,Vm,子图G(V1),G(V2),…,G(Vm)成为连通分支，P(G)表示图G连通分支的个数.计算机数学基础－孙继荣图论－图的基本概念通路、回路、图的连通性点割集与割点，设无向图G＝<V，E>，存在结点集VV，使得P(G－V)>P(G)，而对任意VV，都有P（G－V）＝P(G)，V称为图G的点割集.若V是单元集，V＝{v}，v叫做割点.边割集与割边，设无向图G＝<V，E>，存在边集EE，使得P(G－V)>P(G)，而对任意EE，都有P（G－E）＝P(G)，E称为图G的边割集.若E是单元集，E＝{e}，e叫做割边(桥).

计算机数学基础－孙继荣图论－图的基本概念通路、回路、图的连通性点连通度：最小的点割集的点数目边连通度：最小的边割集的边数目定理5：计算机数学基础－孙继荣图论－图的基本概念通路、回路、图的连通性定理：一个有向图是强连通的充分必要条件是G中有一个回路，它至少经过每个结点一次的。强分图：既有强连通性的最大子图单侧分图：既有单侧连通性的最大子图弱分图：既有弱连通性的最大子图定理：在有向图D＝<V，E>中，它的每个结点位于且仅位于一个强分图中计算机数学基础－孙继荣图论－图的基本概念图的矩阵表示(无向图)关联矩阵设G=<V,E>,关联矩阵M(G)=,其中mij=vi与ej的关联次数(行为结点，列为边)性质：列元素和为2行元素和为结点的度数若行元素和为0，则对应的结点为孤立点全部元素之和为G的总度数平行边对应的两列完全相同计算机数学基础－孙继荣图论－图的基本概念图的矩阵表示(无向图)相邻矩阵:设G＝<V,E>,，相邻矩阵A(G)=，其中aij=vi与vj相关联的边的条数(行、列均为结点)性质：A(G)是对称矩阵对角线上的元素表示该结点处环的个数，若vi是孤立结点，则计算机数学基础－孙继荣图论－图的基本概念图的矩阵表示（无环有向图）关联矩阵：

，列元素和为0每行元素绝对值之和等于对应点的度数，其中1的个数为对应点的出度，－1的个数为对应电的入度所有元素的和为0，1的个数等于－1的个数，都等于边数m计算机数学基础－孙继荣图论－图的基本概念图的矩阵表示（有向图）邻接矩阵：设D＝<V,E>，相邻矩阵A(D)=，其中aij=vi邻接到vj的边的条数(行、列均为结点)所有元素之和为D中长度为1的通路

有向图的邻接矩阵不一定对称计算机数学基础－孙继荣图论－图的基本概念图的矩阵表示由有向图D的邻接矩阵推断从ai到aj的长度为l的通路的数目：Al(D)由有向图D的邻接矩阵推断