图的基本概念--第一章课件

“雪亮工程雪亮工程是以区（县）、乡（镇）、村（社区）三级综治中心为指挥平台、以综治信息化为支撑、以网格化管理为基础、以公共安全视频监控联网应用为重点的是以区（县）、乡（镇）、村（社区）三级综治中心为指挥平台、以综治信息化为支撑、以网格化管理为基础、以公共安全视频监控联网应用为重点的“群众性治安防控工程群众性治安防控工程”。第第1 1章章 图的基本概念图的基本概念第第1 1章章 图的基本概念图的基本概念“雪亮工程雪亮工程是以区（县）、乡（镇）、村（社区）三级综治中心为指挥平台、以综治信息化为支撑、以网格化管理为基础、以公共安全视频监控联网应用为重点的是以区（县）、乡（镇）、村（社区）三级综治中心为指挥平台、以综治信息化为支撑、以网格化管理为基础、以公共安全视频监控联网应用为重点的“群众性治安防控工程群众性治安防控工程”。本章内容本章内容本章内容本章内容1 1 图图2 2 通路与回路通路与回路3 3 图的连通性图的连通性4 4 图的矩阵表示图的矩阵表示5 5 图的运算图的运算 本章内容本章内容1 1 图图2“雪亮工程雪亮工程是以区（县）、乡（镇）、村（社区）三级综治中心为指挥平台、以综治信息化为支撑、以网格化管理为基础、以公共安全视频监控联网应用为重点的是以区（县）、乡（镇）、村（社区）三级综治中心为指挥平台、以综治信息化为支撑、以网格化管理为基础、以公共安全视频监控联网应用为重点的“群众性治安防控工程群众性治安防控工程”。1.1 1.1 1.1 1.1 图的基本概念图的基本概念图的基本概念图的基本概念q图的定义图的定义q图的一些概念和规定图的一些概念和规定q简单图和多重图简单图和多重图q顶点的度数与握手定理顶点的度数与握手定理q图的同构图的同构q完全图与正则图完全图与正则图q子图与补图子图与补图1.1 1.1 图的基本概念图的定义图的基本概念图的定义3“雪亮工程雪亮工程是以区（县）、乡（镇）、村（社区）三级综治中心为指挥平台、以综治信息化为支撑、以网格化管理为基础、以公共安全视频监控联网应用为重点的是以区（县）、乡（镇）、村（社区）三级综治中心为指挥平台、以综治信息化为支撑、以网格化管理为基础、以公共安全视频监控联网应用为重点的“群众性治安防控工程群众性治安防控工程”。无序积与多重集合无序积与多重集合无序积与多重集合无序积与多重集合 q设设A A，B B为任意的两个集合，称为任意的两个集合，称 a,b|aAbBAbB为为A A与与B B的的无序积无序积，记作，记作A&BA&B。可将无序积中的无序对可将无序积中的无序对 a,b 记为记为(a,b)，并且允许并且允许ab。无论无论a,ba,b是否相等，均有是否相等，均有(a,b)(b,a)，因而因而A&BA&BB&AB&A。q元素可以重复出现的集合称为元素可以重复出现的集合称为多重集合多重集合或者或者多重集多重集，某元，某元素重复出现的次数称为该元素的素重复出现的次数称为该元素的重复度重复度。例如例如 在多重集合在多重集合 a,a,b,b,b,c,d 中，中，a,b,c,d的重复度分别为的重复度分别为2,3,1,12,3,1,1。无序积与多重集合无序积与多重集合 设设A A，B B为任意的两个集合，称为任意的两个集合，称a,b|a,b|4“雪亮工程雪亮工程是以区（县）、乡（镇）、村（社区）三级综治中心为指挥平台、以综治信息化为支撑、以网格化管理为基础、以公共安全视频监控联网应用为重点的是以区（县）、乡（镇）、村（社区）三级综治中心为指挥平台、以综治信息化为支撑、以网格化管理为基础、以公共安全视频监控联网应用为重点的“群众性治安防控工程群众性治安防控工程”。笛卡尔笛卡尔笛卡尔笛卡尔积积积积q设设A A，B B为任意的两个集合，称为任意的两个集合，称|aAbBAbB为为A A与与B B的的笛卡尔积笛卡尔积，记作，记作AXBAXB。笛卡尔积笛卡尔积中的是有序对中的是有序对 。只有只有a,ba,b相等的时候才有相等的时候才有(a,b)(b,a).).也只有也只有A=BA=B时才有时才有AXBAXBBXABXA。笛卡尔积设笛卡尔积设A A，B B为任意的两个集合，称为任意的两个集合，称|aAb|aAb5“雪亮工程雪亮工程是以区（县）、乡（镇）、村（社区）三级综治中心为指挥平台、以综治信息化为支撑、以网格化管理为基础、以公共安全视频监控联网应用为重点的是以区（县）、乡（镇）、村（社区）三级综治中心为指挥平台、以综治信息化为支撑、以网格化管理为基础、以公共安全视频监控联网应用为重点的“群众性治安防控工程群众性治安防控工程”。定义定义1 1 一个一个无向图无向图是一个有序的二元组是一个有序的二元组,E,记作记作G G，其中其中（1 1）VV称为称为顶点集顶点集，其元素称为，其元素称为顶点顶点或或结点结点。（2 2）E E称为称为边集边集，它是，它是无序积无序积V&VV&V的多重子集，其元素称为的多重子集，其元素称为无向无向边边，简称，简称边边。定义定义2 2 一个一个有向图有向图是一个有序的二元组是一个有序的二元组 E，记作记作D D，其中其中（1 1）VV称为称为顶点集顶点集，其元素称为，其元素称为顶点顶点或或结点结点。（2 2）E E为为边集边集，它是，它是笛卡儿积笛卡儿积VVVV的多重子集，其元素称为的多重子集，其元素称为有向有向边边，简称，简称边边。无向图和有向图无向图和有向图无向图和有向图无向图和有向图说明说明q可以用图形表示图，即用小圆圈（或实心点）表示顶可以用图形表示图，即用小圆圈（或实心点）表示顶点，用顶点之间的连线表示无向边，用有方向的连线点，用顶点之间的连线表示无向边，用有方向的连线表示有向边。表示有向边。定义定义1 1 一个无向图是一个有序的二元组一个无向图是一个有序的二元组V,E,记作记作G G，其中，其中6“雪亮工程雪亮工程是以区（县）、乡（镇）、村（社区）三级综治中心为指挥平台、以综治信息化为支撑、以网格化管理为基础、以公共安全视频监控联网应用为重点的是以区（县）、乡（镇）、村（社区）三级综治中心为指挥平台、以综治信息化为支撑、以网格化管理为基础、以公共安全视频监控联网应用为重点的“群众性治安防控工程群众性治安防控工程”。例例例例1.11.11.11.1例例1.11.1(1)(1)给定无向图给定无向图G G，其中其中 V Vvv1 1,v,v2 2,v,v3 3,v,v4 4,v,v5 5，E=(vE=(v1 1,v,v1 1),(v),(v1 1,v,v2 2),(v),(v2 2,v,v3 3),(v),(v2 2,v,v3 3),(v),(v2 2,v,v5 5),(v),(v1 1,v,v5 5),(v),(v4 4,v,v5 5).).(2)(2)给定有向图给定有向图D=D=，其中其中 V Va,b,c,da,b,c,d，E E,。画出画出G G与与D D的图形。的图形。例例1.1 1.1例例1.1(1)1.1(1)给定无向图给定无向图G G，其中，其中 V V7“雪亮工程雪亮工程是以区（县）、乡（镇）、村（社区）三级综治中心为指挥平台、以综治信息化为支撑、以网格化管理为基础、以公共安全视频监控联网应用为重点的是以区（县）、乡（镇）、村（社区）三级综治中心为指挥平台、以综治信息化为支撑、以网格化管理为基础、以公共安全视频监控联网应用为重点的“群众性治安防控工程群众性治安防控工程”。图的一些概念和规定图的一些概念和规定图的一些概念和规定图的一些概念和规定qG G表示无向图，但有时用表示无向图，但有时用G G泛指图泛指图(无向的或有向的无向的或有向的)。qD D只能表示有向图。只能表示有向图。qV(G)V(G)，E(G)E(G)分别表示分别表示G G的的顶点集顶点集和和边集边集。q若若|V(G)|V(G)|n n，则称则称G G为为n n阶图阶图。q若若|V(G)|V(G)|与与|E(G)|E(G)|均为有限数，则称均为有限数，则称G G为为有限图有限图。q若边集若边集E(G)E(G)，则称则称G G为为零图零图，此时，又若，此时，又若G G为为n n阶图，则称阶图，则称G G为为n n阶零图阶零图，记作，记作N Nn n，特别地，称特别地，称N N1 1为为平凡图平凡图。q在图的定义中规定顶点集在图的定义中规定顶点集V V为非空集，但在图的运算中可能产为非空集，但在图的运算中可能产生顶点集为空集的运算结果，为此规定生顶点集为空集的运算结果，为此规定顶点集为空集的图顶点集为空集的图为为空空图图，并将空图记为，并将空图记为。图的一些概念和规定图的一些概念和规定G G表示无向图，但有时用表示无向图，但有时用G G泛指图泛指图(无向的或有无向的或有8“雪亮工程雪亮工程是以区（县）、乡（镇）、村（社区）三级综治中心为指挥平台、以综治信息化为支撑、以网格化管理为基础、以公共安全视频监控联网应用为重点的是以区（县）、乡（镇）、村（社区）三级综治中心为指挥平台、以综治信息化为支撑、以网格化管理为基础、以公共安全视频监控联网应用为重点的“群众性治安防控工程群众性治安防控工程”。标定图与非标定图、基图标定图与非标定图、基图标定图与非标定图、基图标定图与非标定图、基图 q将图的集合定义转化成图形表示之后，常用将图的集合定义转化成图形表示之后，常用e ek k表示表示无向边无向边(v vi i,v,vj j)（或或有向边有向边 ），），并称并称顶点或边用字母标定顶点或边用字母标定的图的图为为标定图标定图，否则称为，否则称为非标定图非标定图。q将有向图各将有向图各有向边均改成无向边后的无向图有向边均改成无向边后的无向图称为原来图的称为原来图的基图基图。q易知标定图与非标定图是可以相互转化的易知标定图与非标定图是可以相互转化的;任何无向图任何无向图G G的各边均加上箭头就可以得到以的各边均加上箭头就可以得到以G G为基图的有向图。为基图的有向图。标定图与非标定图、基图标定图与非标定图、基图 将图的集合定义转化成图形表示之后，常将图的集合定义转化成图形表示之后，常9“雪亮工程雪亮工程是以区（县）、乡（镇）、村（社区）三级综治中心为指挥平台、以综治信息化为支撑、以网格化管理为基础、以公共安全视频监控联网应用为重点的是以区（县）、乡（镇）、村（社区）三级综治中心为指挥平台、以综治信息化为支撑、以网格化管理为基础、以公共安全视频监控联网应用为重点的“群众性治安防控工程群众性治安防控工程”。关联与关联次数、环、孤立点关联与关联次数、环、孤立点关联与关联次数、环、孤立点关联与关联次数、环、孤立点 q设设G G为无向图，为无向图，ek(vi,vj)E)E，称称vi,vj为为ek的端点的端点，ek与与vi或或ek与与vj是彼此相是彼此相关联关联的。的。若若vivj，则称则称ek与与vi或或ek与与vj的的关联次数为关联次数为1 1。若若vivj，则称则称ek与与vi的的关联次数为关联次数为2 2，并称，并称ek为为环环。任意的任意的vlVV，若若vlvi且且vlvj，则称则称ek与与vl的的关联次数为关联次数为0 0。q设设D D为有向图，为有向图，ek EE，称称vi,vj为为ek的的端点。端点。若若vivj，则称则称ek为为D D中的中的环环。q无论在无向图中还是在有向图中，无边关联的顶点均称为无论在无向图中还是在有向图中，无边关联的顶点均称为孤立孤立点点。关联与关联次数、环、孤立点关联与关联次数、环、孤立点 设设G G为无向图，为无向图，ekek10“雪亮工程雪亮工程是以区（县）、乡（镇）、村（社区）三级综治中心为指挥平台、以综治信息化为支撑、以网格化管理为基础、以公共安全视频监控联网应用为重点的是以区（县）、乡（镇）、村（社区）三级综治中心为指挥平台、以综治信息化为支撑、以网格化管理为基础、以公共安全视频监控联网应用为重点的“群众性治安防控工程群众性治安防控工程”。相邻与邻接相邻与邻接相邻与邻接相邻与邻接 q设无向图设无向图G GVE，vi，vjVV，ek，elEE。若若 etEE，使得使得et(vi，vj)，则称则称vi与与vj是是相邻的相邻的。若若ek与与el至少有一个公共端点至少有一个公共端点，则称，则称ek与与el是是相邻的相邻的。q设有向图设有向图D DVE，vi，vjVV，ek，elEE。若若 etEE，使得使得et ，则称则称vi为为et的的始点始点，vj为为et的的终终点点，并称，并称vi邻接到邻接到vj，vj邻接于邻接于vi。若若ek的终点为的终点为el的始点，则称的始点，则称ek与与el相邻相邻。相邻与邻接相邻与邻接 设无向图设无向图G GVE，vivi，vjV vjV，ekek，e e11“雪亮工程雪亮工程是以区（县）、乡（镇）、村（社区）三级综治中心为指挥平台、以综治信息化为支撑、以网格化管理为基础、以公共安全视频监控联网应用为重点的是以区（县）、乡（镇）、村（社区）三级综治中心为指挥平台、以综治信息化为支撑、以网格化管理为基础、以公共安全视频监控联网应用为重点的“群众性治安防控工程群众性治安防控工程”。邻域邻域邻域邻域q设无向图设无向图G ，vV，称称 u|uV(u,v)Euv 为为v的的邻域邻域，记做，记做NG(v)。称称NG G(v)v 为为v的的闭邻域闭邻域，记做，记做NG(v)(v)。称称 e|eEe与与v相关联相关联 为为v的的关联集关联集，记做，记做IG(v)。q设有向图设有向图D ，vV，称称 u|uVV EEuv 为为v的的后继元集后继元集，记做，记做+D(v)v)。称称 u|uVV EEuv 为为v的的先驱元集先驱元集，记做，记做-D(v)v)。称称+D D(v)为为v v的出的出邻域邻域,-D D(v)为为v v 的入的入邻域邻域.+D D(v)-D D(v)为为v的的邻域邻域，记做，记做ND(v)。称称ND(v)v 为为v的的闭邻域闭邻域，记做，记做ND(v)。邻域设无向图邻域设无向图G GVE，vVvV，12“雪亮工程雪亮工程是以区（县）、乡（镇）、村（社区）三级综治中心为指挥平台、以综治信息化为支撑、以网格化管理为基础、以公共安全视频监控联网应用为重点的是以区（县）、乡（镇）、村（社区）三级综治中心为指挥平台、以综治信息化为支撑、以网格化管理为基础、以公共安全视频监控联网应用为重点的“群众性治安防控工程群众性治安防控工程”。举例举例举例举例N NG G(v1 1)+D(d)v2 2，v5 5 NG(v1)v1 1，v2 2，v5 5 I IG G(v1 1)e1 1，e2 2，e3 3 c-D(D(d)a，c N ND D(d)a，c N ND D(d)a，c，d 举例举例NG(v1)NG(v1)+D(d)+D(d)v2 v2，v5NG(vv5NG(v13“雪亮工程雪亮工程是以区（县）、乡（镇）、村（社区）三级综治中心为指挥平台、以综治信息化为支撑、以网格化管理为基础、以公共安全视频监控联网应用为重点的是以区（县）、乡（镇）、村（社区）三级综治中心为指挥平台、以综治信息化为支撑、以网格化管理为基础、以公共安全视频监控联网应用为重点的“群众性治安防控工程群众性治安防控工程”。简单图与多重图简单图与多重图简单图与多重图简单图与多重图 定义定义1.31.3 在无向图中，关联一对顶点的无向边如果在无向图中，关联一对顶点的无向边如果多于多于1 1条条，则，则称这些边为称这些边为平行边平行边，平行边的条数称为，平行边的条数称为重数重数。在有向图中，关联一对顶点的有向边如果在有向图中，关联一对顶点的有向边如果多于多于1 1条条，并且这些，并且这些边的边的始点和终点相同始点和终点相同(也就是它们的方向相同也就是它们的方向相同)，则称这些边，则称这些边为为平行边平行边。含平行边的图称为含平行边的图称为多重图多重图。既不含平行边也不含环的图既不含平行边也不含环的图称为称为简单图简单图。例如：例如：在图在图1.11.1中，中，(a)a)中中e e5 5与与e e6 6是平行边，是平行边，(b)b)中中e e2 2与与e e3 3是平行边，但是平行边，但e e6 6与与e e7 7不是平行边。不是平行边。(a)a)和和(b)b)两个图都不是简单图。两个图都不是简单图。简单图与多重图简单图与多重图 定义定义1.3 1.3 在无向图中，关联一对顶点的无向边在无向图中，关联一对顶点的无向边14“雪亮工程雪亮工程是以区（县）、乡（镇）、村（社区）三级综治中心为指挥平台、以综治信息化为支撑、以网格化管理为基础、以公共安全视频监控联网应用为重点的是以区（县）、乡（镇）、村（社区）三级综治中心为指挥平台、以综治信息化为支撑、以网格化管理为基础、以公共安全视频监控联网应用为重点的“群众性治安防控工程群众性治安防控工程”。顶点的度数顶点的度数顶点的度数顶点的度数定义定义1.41.4 设设G G为一无向图，为一无向图，vVV，称称v作为边的端点作为边的端点次数之和为次数之和为v的度数的度数，简称为，简称为度度，记做，记做 dG(v)。在不发生混淆时，简记为在不发生混淆时，简记为d(v)。注注:某个点上的环要计算某个点上的环要计算2 2次度数次度数.设设D DVE为有向图，为有向图，vVV，称称v作为边的始点次数之和为作为边的始点次数之和为v的出度的出度，记做，记做d+D(v)，简记作简记作d+(v)。称称v作为边的终点次数之和为作为边的终点次数之和为v的入度的入度，记做，记做d-D(v)，简记作简记作d-(v)。称称d+(v)+)+d-(v)为为v v的的度数度数，记做，记做d(v)。注注:某个点上的有向环要对这个点计算一次入度计算一次出度某个点上的有向环要对这个点计算一次入度计算一次出度.顶点的度数定义顶点的度数定义1.4 1.4 设设G G为一无向图，为一无向图，vVvV，15“雪亮工程雪亮工程是以区（县）、乡（镇）、村（社区）三级综治中心为指挥平台、以综治信息化为支撑、以网格化管理为基础、以公共安全视频监控联网应用为重点的是以区（县）、乡（镇）、村（社区）三级综治中心为指挥平台、以综治信息化为支撑、以网格化管理为基础、以公共安全视频监控联网应用为重点的“群众性治安防控工程群众性治安防控工程”。图的度数的相关概念图的度数的相关概念图的度数的相关概念图的度数的相关概念q在无向图在无向图G G中，中，最大度最大度(G)G)maxmaxd(v)|)|vV(G)V(G)最小度最小度(G)(G)mind(mind(v)|)|vV(G)V(G)q称度数为称度数为1 1的顶点为的顶点为悬挂顶点悬挂顶点，与它关联的边称为，与它关联的边称为悬挂边悬挂边。度为偶数度为偶数(奇数奇数)的顶点称为的顶点称为偶度偶度(奇度奇度)顶点顶点。q在有向图在有向图D D中，中，最大出度最大出度+(D)D)maxmaxd+(v)|)|vV(D)V(D)最小出度最小出度+(D)(D)minmind+(v)|)|vV(D)V(D)最大入度最大入度-(D)(D)maxmaxd-(v)|)|vV(D)V(D)最小入度最小入度-(D)(D)minmind-(v)|)|vV(D)V(D)图的度数的相关概念在无向图图的度数的相关概念在无向图G G中，中，16“雪亮工程雪亮工程是以区（县）、乡（镇）、村（社区）三级综治中心为指挥平台、以综治信息化为支撑、以网格化管理为基础、以公共安全视频监控联网应用为重点的是以区（县）、乡（镇）、村（社区）三级综治中心为指挥平台、以综治信息化为支撑、以网格化管理为基础、以公共安全视频监控联网应用为重点的“群众性治安防控工程群众性治安防控工程”。图的度数举例图的度数举例图的度数举例图的度数举例d(v1 1)4(4(注意，环提供注意，环提供2 2度度)，4 4，1 1，v4 4是悬挂顶点，是悬挂顶点，e7 7是悬挂边。是悬挂边。d+(a)4 4，d-(a)1 1(环环e1 1提供出度提供出度1 1，提供入度，提供入度1)1)，d(a)4+14+15 5。5 5，3 3，+4(4(在在a点达到点达到)+0(0(在在b点达到点达到)-3(3(在在b点达到点达到)-1(1(在在a和和c点达到点达到)图的度数举例图的度数举例d(v1)d(v1)4(4(注意，环提供注意，环提供2 2度度)，d+(a)d+(a)17“雪亮工程雪亮工程是以区（县）、乡（镇）、村（社区）三级综治中心为指挥平台、以综治信息化为支撑、以网格化管理为基础、以公共安全视频监控联网应用为重点的是以区（县）、乡（镇）、村（社区）三级综治中心为指挥平台、以综治信息化为支撑、以网格化管理为基础、以公共安全视频监控联网应用为重点的“群众性治安防控工程群众性治安防控工程”。握手定理握手定理握手定理握手定理定理定理1.11.1 设设G G为任意无向图，为任意无向图，V V v1 1,v2 2,vn，|E|E|m，则则说明说明任何无向图中，各顶点度数之和等于边数的两倍。任何无向图中，各顶点度数之和等于边数的两倍。证明证明G G中每条边中每条边(包括环包括环)均有两个端点，均有两个端点，所以在计算所以在计算G G中各顶点度数之和时，中各顶点度数之和时，每条边均提供每条边均提供2 2度，当然，度，当然，m条边，共提供条边，共提供2 2m度。度。握手定理定理握手定理定理1.1 1.1 设设G G为任意无向图，为任意无向图，V Vv1 v118“雪亮工程雪亮工程是以区（县）、乡（镇）、村（社区）三级综治中心为指挥平台、以综治信息化为支撑、以网格化管理为基础、以公共安全视频监控联网应用为重点的是以区（县）、乡（镇）、村（社区）三级综治中心为指挥平台、以综治信息化为支撑、以网格化管理为基础、以公共安全视频监控联网应用为重点的“群众性治安防控工程群众性治安防控工程”。q另外一个更严格的证明：另外一个更严格的证明：q当当G G是简单图时，是简单图时，另外一个更严格的证明：另外一个更严格的证明：19“雪亮工程雪亮工程是以区（县）、乡（镇）、村（社区）三级综治中心为指挥平台、以综治信息化为支撑、以网格化管理为基础、以公共安全视频监控联网应用为重点的是以区（县）、乡（镇）、村（社区）三级综治中心为指挥平台、以综治信息化为支撑、以网格化管理为基础、以公共安全视频监控联网应用为重点的“群众性治安防控工程群众性治安防控工程”。q当图当图G G不是简单图时，不是简单图时，只要把每一个环与重边上只要把每一个环与重边上“嵌入嵌入”一一个新的顶点得到新的图个新的顶点得到新的图G G，G G是简单图是简单图.假设有假设有t t个新的个新的顶点顶点,图图G G中原来中原来G G中的顶点度数不变，中的顶点度数不变，而每个新的顶点的而每个新的顶点的度数为度数为2.2.新图新图G G的边数比图的边数比图G G的边数多了的边数多了t t条（原因是在环条（原因是在环和重边上加入新点后，和重边上加入新点后，将原来的一条边变成了两条边）。将原来的一条边变成了两条边）。q对对G G利用前面的证明结果：利用前面的证明结果：q两边消去两边消去2t,2t,得到结论。得到结论。当图当图G G不是简单图时，不是简单图时，只要把每一个环与重边上只要把每一个环与重边上“嵌入嵌入”一个新的一个新的20“雪亮工程雪亮工程是以区（县）、乡（镇）、村（社区）三级综治中心为指挥平台、以综治信息化为支撑、以网格化管理为基础、以公共安全视频监控联网应用为重点的是以区（县）、乡（镇）、村（社区）三级综治中心为指挥平台、以综治信息化为支撑、以网格化管理为基础、以公共安全视频监控联网应用为重点的“群众性治安防控工程群众性治安防控工程”。握手定理握手定理握手定理握手定理定理定理1.2 1.2 设设D D为任意有向图，为任意有向图，V V v1 1,v2 2,vn，|E|E|m，则则 握手定理定理握手定理定理1.2 1.2 设设D D为任意有向图，为任意有向图，V Vv1 v121“雪亮工程雪亮工程是以区（县）、乡（镇）、村（社区）三级综治中心为指挥平台、以综治信息化为支撑、以网格化管理为基础、以公共安全视频监控联网应用为重点的是以区（县）、乡（镇）、村（社区）三级综治中心为指挥平台、以综治信息化为支撑、以网格化管理为基础、以公共安全视频监控联网应用为重点的“群众性治安防控工程群众性治安防控工程”。握手定理的推论握手定理的推论握手定理的推论握手定理的推论推论推论任何图任何图(无向的或有向的无向的或有向的)中，奇度顶点的个数是偶数。中，奇度顶点的个数是偶数。证明证明设设G GVE为任意一图，令为任意一图，令V V1 1 v|vVVd(v)为奇数为奇数 V V2 2 v|vVVd(v)为偶数为偶数 则则V V1 1VV2 2V V，V V1 1VV2 2 ，由握手定理可知由握手定理可知 由于由于2 2m和和，所以，所以为偶数为偶数，但因但因V V1 1中顶点度数为奇数，中顶点度数为奇数，所以所以|V V1 1|必为偶数。必为偶数。握手定理的推论推论握手定理的推论推论任何图任何图(无向的或有向的无向的或有向的)中，奇度顶点的个中，奇度顶点的个22“雪亮工程雪亮工程是以区（县）、乡（镇）、村（社区）三级综治中心为指挥平台、以综治信息化为支撑、以网格化管理为基础、以公共安全视频监控联网应用为重点的是以区（县）、乡（镇）、村（社区）三级综治中心为指挥平台、以综治信息化为支撑、以网格化管理为基础、以公共安全视频监控联网应用为重点的“群众性治安防控工程群众性治安防控工程”。问题研究问题研究问题研究问题研究问题：问题：在一个部门的在一个部门的2525个人中间，由于意见不同，是否可能每个个人中间，由于意见不同，是否可能每个人恰好与其他人恰好与其他5 5个人意见一致？个人意见一致？解答：解答：不可能不可能。考虑一个图，其中顶点代表人，如果两个人意见。考虑一个图，其中顶点代表人，如果两个人意见相同，可用边连接，所以每个顶点都是奇数度。存在奇数个度相同，可用边连接，所以每个顶点都是奇数度。存在奇数个度数为奇数的图，这是不可能的。数为奇数的图，这是不可能的。说明：说明：(1)(1)很多离散问题可以用图模型求解。很多离散问题可以用图模型求解。(2)(2)为了建立一个图模型，需要决定顶点和边分别代表什么。为了建立一个图模型，需要决定顶点和边分别代表什么。(3)(3)在一个图模型中，边经常代表两个顶点之间的关系。在一个图模型中，边经常代表两个顶点之间的关系。问题研究问题：在一个部门的问题研究问题：在一个部门的2525个人中间，由于意见不同，是否可个人中间，由于意见不同，是否可23“雪亮工程雪亮工程是以区（县）、乡（镇）、村（社区）三级综治中心为指挥平台、以综治信息化为支撑、以网格化管理为基础、以公共安全视频监控联网应用为重点的是以区（县）、乡（镇）、村（社区）三级综治中心为指挥平台、以综治信息化为支撑、以网格化管理为基础、以公共安全视频监控联网应用为重点的“群众性治安防控工程群众性治安防控工程”。q例例2 2：晚会上大家握手言欢，试证握过奇次手的人数是偶数。晚会上大家握手言欢，试证握过奇次手的人数是偶数。q解答：构造一个图，解答：构造一个图，以参加晚会的人为顶，仅当二人握手以参加晚会的人为顶，仅当二人握手时在相应的二顶间加一条边。时在相应的二顶间加一条边。于是每个人握手的次数为这于是每个人握手的次数为这个图的相应顶点的度数。个图的相应顶点的度数。用握手定理的推论得到结论。用握手定理的推论得到结论。q例例3 3：空间中不可能有这样的多面体存在，空间中不可能有这样的多面体存在，它的面数是奇它的面数是奇数，而且每个面是奇数条围成的。数，而且每个面是奇数条围成的。q解答：如果有这样的多面体存在，以此多面体的面集合为顶解答：如果有这样的多面体存在，以此多面体的面集合为顶点集构造一个图点集构造一个图G,G,当且仅当两个面有公共边界线时在相应的当且仅当两个面有公共边界线时在相应的两顶间连一条边，两顶间连一条边，于是于是|V(G)|V(G)|是奇数，而且对每个顶点是奇数，而且对每个顶点v,d(v)v,d(v)是奇数是奇数,则所有的顶点的度数之和为奇数，则所有的顶点的度数之和为奇数，与握手定与握手定理矛盾。理矛盾。例例2 2：晚会上大家握手言欢，试证握过奇次手的人数是偶数。晚会上大家握手言欢，试证握过奇次手的人数是偶数。24“雪亮工程雪亮工程是以区（县）、乡（镇）、村（社区）三级综治中心为指挥平台、以综治信息化为支撑、以网格化管理为基础、以公共安全视频监控联网应用为重点的是以区（县）、乡（镇）、村（社区）三级综治中心为指挥平台、以综治信息化为支撑、以网格化管理为基础、以公共安全视频监控联网应用为重点的“群众性治安防控工程群众性治安防控工程”。度数列度数列度数列度数列设设G G为一个为一个n阶无向图，阶无向图，V V v1 1,v2 2,vn，称称d(v1 1)，d(v2 2)，d(vn n)为为G G的的度数列度数列。对于顶点标定的无向图，它的度数列是唯一的。对于顶点标定的无向图，它的度数列是唯一的。反之，对于给定的非负整数列反之，对于给定的非负整数列d d1 1,d2 2,dn，若存在若存在V V v1 1,v2 2,vn 为顶点集的为顶点集的n阶无向图阶无向图G G，使得使得d(vi)di，则称则称d是是可图化的可图化的。特别地，若所得图是简单图，则称特别地，若所得图是简单图，则称d是是可简单图化的可简单图化的。类似地，设类似地，设D D为一个为一个n n阶有向图，阶有向图，V V v1 1,v2 2,vn，称称d(v1 1)，d(v2 2)，d(vn)为为D D的的度数列度数列，另外称，另外称d+(v1 1)，d+(v2 2)，d+(vn)与与d-(v1 1)，d-(v2 2)，d-(vn)分别为分别为D D的的出度列出度列和和入度列入度列。度数列设度数列设G G为一个为一个n n阶无向图，阶无向图，V Vv1,v2,v1,v2,25“雪亮工程雪亮工程是以区（县）、乡（镇）、村（社区）三级综治中心为指挥平台、以综治信息化为支撑、以网格化管理为基础、以公共安全视频监控联网应用为重点的是以区（县）、乡（镇）、村（社区）三级综治中心为指挥平台、以综治信息化为支撑、以网格化管理为基础、以公共安全视频监控联网应用为重点的“群众性治安防控工程群众性治安防控工程”。度数列举例度数列举例度数列举例度数列举例按顶点的标定顺序，度数列为按顶点的标定顺序，度数列为4,4,2,1,34,4,2,1,3。按字母顺序，度数列，出度列，入按字母顺序，度数列，出度列，入度列分别为度列分别为5,3,3,35,3,3,34,0,2,14,0,2,11,3,1,21,3,1,2度数列举例按顶点的标定顺序，度数列为按字母顺序，度数列，出度度数列举例按顶点的标定顺序，度数列为按字母顺序，度数列，出度26“雪亮工程雪亮工程是以区（县）、乡（镇）、村（社区）三级综治中心为指挥平台、以综治信息化为支撑、以网格化管理为基础、以公共安全视频监控联网应用为重点的是以区（县）、乡（镇）、村（社区）三级综治中心为指挥平台、以综治信息化为支撑、以网格化管理为基础、以公共安全视频监控联网应用为重点的“群众性治安防控工程群众性治安防控工程”。可图化的充要条件可图化的充要条件可图化的充要条件可图化的充要条件定理定理1.31.3 设非负整数列设非负整数列d(d1 1，d2 2，dn)，则则d d是可图化的当是可图化的当且仅当且仅当 证明证明必要性。必要性。由握手定理显然得证。由握手定理显然得证。充分性。充分性。由已知条件可知，由已知条件可知，d中有偶数个奇数度点。中有偶数个奇数度点。奇数度点两两之间连一边，剩余度用环来实现。奇数度点两两之间连一边，剩余度用环来实现。5331可图化的充要条件定理可图化的充要条件定理1.3 1.3 设非负整数列设非负整数列d d(d1(d1，d2d2，27“雪亮工程雪亮工程是以区（县）、乡（镇）、村（社区）三级综治中心为指挥平台、以综治信息化为支撑、以网格化管理为基础、以公共安全视频监控联网应用为重点的是以区（县）、乡（镇）、村（社区）三级综治中心为指挥平台、以综治信息化为支撑、以网格化管理为基础、以公共安全视频监控联网应用为重点的“群众性治安防控工程群众性治安防控工程”。可图化举例可图化举例可图化举例可图化举例由定理由定理1.31.3立即可知，立即可知，(3,3,2,1)(3,3,2,1)，(3,2,2,1,1)(3,2,2,1,1)等是不可图化的，等是不可图化的，(3,3,2,2)(3,3,2,2)，(3,2,2,2,1)(3,2,2,2,1)等是可图化的。等是可图化的。可图化举例由定理可图化举例由定理1.3 1.3立即可知，立即可知，28“雪亮工程雪亮工程是以区（县）、乡（镇）、村（社区）三级综治中心为指挥平台、以综治信息化为支撑、以网格化管理为基础、以公共安全视频监控联网应用为重点的是以区（县）、乡（镇）、村（社区）三级综治中心为指挥平台、以综治信息化为支撑、以网格化管理为基础、以公共安全视频监控联网应用为重点的“群众性治安防控工程群众性治安防控工程”。q定理：若定理：若 是简单图的次序列，且是简单图的次序列，且则则 是偶数，且对是偶数，且对19601960年年ErdosErdos和和GallaiGallai已经证明这也是充分条件。已经证明这也是充分条件。定理：若定理：若 是简单图的次序列，且是简单图的次序列，且29“雪亮工程雪亮工程是以区（县）、乡（镇）、村（社区）三级综治中心为指挥平台、以综治信息化为支撑、以网格化管理为基础、以公共安全视频监控联网应用为重点的是以区（县）、乡（镇）、村（社区）三级综治中心为指挥平台、以综治信息化为支撑、以网格化管理为基础、以公共安全视频监控联网应用为重点的“群众性治安防控工程群众性治安防控工程”。q证明：大致思路：证明：大致思路：对任意的对任意的k,k,把图分成两部分：一部分是把图分成两部分：一部分是1 1到到k k个点组成的，个点组成的，设为设为V1V1，另外的另外的n-Kn-K点组成另外一部分点组成另外一部分,设为设为V2V2。q我们再来计算我们再来计算1 1到到k k点的总的度数之和。点的总的度数之和。这个度数由两部分这个度数由两部分贡献，贡献，一是来自于一是来自于V1V1的贡献，的贡献，最多是最多是V1V1构成完全图，构成完全图，它它们的度数之和为们的度数之和为k(k-1),k(k-1),第二部分来自于第二部分来自于V2,V2V2,V2中的每个点中的每个点给给V1V1的所有点贡献的次数最多是的所有点贡献的次数最多是d_id_i和和k k之间的最小值（原因之间的最小值（原因是，是，V2 V2的每个点的度数全部贡献给的每个点的度数全部贡献给V1,V1,但但V1V1中的点最多只有中的点最多只有k k个，个，只能最多接收只能最多接收k k次）。次）。证明：大致思路：证明：大致思路：对任意的对任意的k,k,把图分成两部分：一部分是把图分成两部分：一部分是1 1到到30“雪亮工程雪亮工程是以区（县）、乡（镇）、村（社区）三级综治中心为指挥平台、以综治信息化为支撑、以网格化管理为基础、以公共安全视频监控联网应用为重点的是以区（县）、乡（镇）、村（社区）三级综治中心为指挥平台、以综治信息化为支撑、以网格化管理为基础、以公共安全视频监控联网应用为重点的“群众性治安防控工程群众性治安防控工程”。定理定理定理定理1.41.41.41.4定理定理1.41.4 设设G G为任意为任意n阶无向简单图，则阶无向简单图，则(G)G)n-1-1。证明证明因为因为G G既无平行边也无环，既无平行边也无环，所以所以G G中任何顶点中任何顶点v至多与其余的至多与其余的n-1-1个顶点均相邻，个顶点均相邻，于是于是d(v)n-1-1，由于由于v v的任意性，所以的任意性，所以(G)G)n-1-1。例例1.21.2 判断下列各非负整数列哪些是可图化的？哪些是可简单判断下列各非负整数列哪些是可图化的？哪些是可简单图化的？图化的？(1)(5,5,4,4,2,1)(1)(5,5,4,4,2,1)不可图化。不可图化。(2)(5,4,3,2,2)(2)(5,4,3,2,2)可图化，不可简单图化。若它可简单图化，可图化，不可简单图化。若它可简单图化，设所得图为设所得图为G G，则则(G)G)max5,4,3,2,2max5,4,3,2,25 5，这与定理这与定理1.41.4矛盾。矛盾。定理定理1.4 1.4定理定理1.4 1.4 设设G G为任意为任意n n阶无向简单图，则阶无向简单图，则(G)(G)31“雪亮工程雪亮工程是以区（县）、乡（镇）、村（社区）三级综治中心为指挥平台、以综治信息化为支撑、以网格化管理为基础、以公共安全视频监控联网应用为重点的是以区（县）、乡（镇）、村（社区）三级综治中心为指挥平台、以综治信息化为支撑、以网格化管理为基础、以公共安全视频监控联网应用为重点的“群众性治安防控工程群众性治安防控工程”。例例例例1.21.21.21.2(3)(3,3,3,1)(3)(3,3,3,1)可图化，不可简单图化。假设该序列可以简单图化，可图化，不可简单图化。假设该序列可以简单图化，设设G GVE以该序列为度数列。以该序列为度数列。不妨设不妨设V Vvv1 1,v,v2 2,v,v3 3,v,v4 4 且且 d(vd(v1 1)d(vd(v2 2)d(vd(v3 3)3,d(v3,d(v4 4)1 1，由于由于d(vd(v4 4)1 1，因而因而v v4 4只能与只能与v v1 1，v v2 2，v v3 3之一相邻，之一相邻，于是于是v v1 1，v v2 2，v v3 3不可能都是不可能都是3 3度顶点，这是矛盾的，度顶点，这是矛盾的，因而因而(3)(3)中序列也不可简单图化。中序列也不可简单图化。(4)(4)(d d1 1,d,d2 2,d dn n)，d d1 1dd2 2 ddn n1 1 且且 为偶数。为偶数。可图化，不可简单图化。可图化，不可简单图化。原因原因?例例1.2(3)(3,3,3,1)(4)(d1,d2,d1.2(3)(3,3,3,1)(4)(d1,d2,d32“雪亮工程雪亮工程是以区（县）、乡（镇）、村（社区）三级综治中心为指挥平台、以综治信息化为支撑、以网格化管理为基础、以公共安全视频监控联网应用为重点的是以区（县）、乡（镇）、村（社区）三级综治中心为指挥平台、以综治信息化为支撑、以网格化管理为基础、以公共安全视频监控联网应用为重点的“群众性治安防控工程群众性治安防控工程”。例例例例14.214.214.214.2(5)(4,4,3,3,2,2)(5)(4,4,3,3,2,2)可简单图化。下图中两个可简单图化。下图中两个6 6阶无向简单图都以阶无向简单图都以(5)(5)中序列为度中序列为度数列。数列。例例14.2(5)(4,4,3,3,2,2)14.2(5)(4,4,3,3,2,2)33“雪亮工程雪亮工程是以区（县）、乡（镇）、村（社区）三级综治中心为指挥平台、以综治信息化为支撑、以网格化管理为基础、以公共安全视频监控联网应用为重点的是以区（县）、乡（镇）、村（社区）三级综治中心为指挥平台、以综治信息化为支撑、以网格化管理为基础、以公共安全视频监控联网应用为重点的“群众性治安防控工程群众性治安防控工程”。图的同构图的同构图的同构图的同构定义定义1.51.5 设设G G1 1V，G G2 2V 为两个无向图，为两个无向图，若存在双射函数若存在双射函数f f：V V1 1VV2 2，对于对于vi,vjVV1 1，(vi,vj)E)E1 1当且仅当当且仅当(f(f(vi),f(),f(vj)E)E2 2，并且并且(vi,vj)与与(f(f(vi),f(),f(vj)的重数相同，的重数相同，则称则称G G1 1与与G G2 2是同构的是同构的，记做，记做G G1 1G G2 2。说明说明(1)(1)类似地，可以定义两个有向图的同构。类似地，可以定义两个有向图的同构。(2)(2)图的同构关系看成全体图集合上的二元关系。图的同构关系看成全体图集合上的二元关系。(3)(3)图的同构关系是等价关系。图的同构关系是等价关系。(4)(4)在图同构的意义下，图的数学定义与图形表示在图同构的意义下，图的数学定义与图形表示 是一一对应的。是一一对应的。图的同构定义图的同构定义1.5 1.5 设设G1G1，G2G2V2,EV2,E34“雪亮工程雪亮工程是以区（县）、乡（镇）、村（社区）三级综治中心为指挥平台、以综治信息化为支撑、以网格化管理为基础、以公共安全视频监控联网应用为重点的是以区（县）、乡（镇）、村（社区）三级综治中心为指挥平台、以综治信息化为支撑、以网格化管理为基础、以公共安全视频监控联网应用为重点的“群众性治安防控工程群众性治安防控工程”。图的同构举例图的同构举例图的同构举例图的同构举例彼得森彼得森(Petersen)图图图的同构举例彼得森图的同构举例彼得森(Petersen)(Petersen)图图35“雪亮工程雪亮工程是以区（县）、乡（镇）、村（社区）三级综治中心为指挥平台、以综治信息化为支撑、以网格化管理为基础、以公共安全视频监控联网应用为重点的是以区（县）、乡（镇）、村（社区）三级综治中心为指挥平台、以综治信息化为支撑、以网格化管理为基础、以公共安全视频监控联网应用为重点的“群众性治安防控工程群众性治安防控工程”。图同构的必要条件：图同构的必要条件：图同构的必要条件：图同构的必要条件：q节点数目相等节点数目相等q边数相等边数相等q度数相同的节点数目相等度数相同的节点数目相等图同构的必要条件：节点数目相等图同构的必要条件：节点数目相等36“雪亮工程雪亮工程是以区（县）、乡（镇）、村（社区）三级综治中心为指挥平台、以综治信息化为支撑、以网格化管理为基础、以公共安全视频监控联网应用为重点的是以区（县）、乡（镇）、村（社区）三级综治中心为指挥平台、以综治信息化为支撑、以网格化管理为基础、以公共安全视频监控联网应用为重点的“群众性治安防控工程群众性治安防控工程”。边图（线图）边图（线图）边图（线图）边图（线图）q定义：定义：设设G G是一个无环图，边图是一个无环图，边图L(G)L(G)这样构成：将这样构成：将E(G)E(G)中的中的每条边作为每条边作为L(G)L(G)的顶点集，即的顶点集，即 V V（L(G)=E(G)L(G)=E(G)，L(G)L(G)中的中的两顶相邻当且仅当它们是两顶相邻当且仅当它们是G G中的两条相邻的边。中的两条相邻的边。q边图有许多有趣的性质边图有许多有趣的性质.例如，例如，(1)(1)若若uvuv是是G G中的边，则在中的边，则在L(G)L(G)中中uvuv对应的顶点的度数是对应的顶点的度数是 的的d(u)+d(v)-2.d(u)+d(v)-2.这是因为：这是因为：uvuv对应的顶点的次数是除边对应的顶点的次数是除边uvuv以外的与以外的与u,vu,v相邻的边的条数相邻的边的条数之和，即之和，即(d(u)-1)+(d(v)-1)(d(u)-1)+(d(v)-1)q2)2)边图（线图）定义：边图（线图）定义：设设G G是一个无环图，边图是一个无环图，边图L(G)L(G)这样构成：这样构成：37“雪亮工程雪亮工程是以区（县）、乡（镇）、村（社区）三级综治中心为指挥平台、以综治信息化为支撑、以网格化管理为基础、以公共安全视频监控联网应用为重点的是以区（县）、乡（镇）、村（社区）三级综治中心为指挥平台、以综治信息化为支撑、以网格化管理为基础、以公共安全视频监控联网应用为重点的“群众性治安防控工程群众性治安防控工程”。完全图完全图完全图完全图定义定义1.61.6 设设G G为为n阶无向简单图，若阶无向简单图，若G G中中每个顶点均与其余的每个顶点均与其余的n-1-1个个顶点相邻顶点相邻，则称，则称G G为为n阶无向完全图阶无向完全图，简称，简称n阶完全图阶完全图，记做，记做K Kn(n1)1)。设设D D为为n阶有向简单图，若阶有向简单图，若D D中每个顶点都邻接到其余的中每个顶点都邻接到其余的n-1-1个顶个顶点，又邻接于其余的点，又邻接于其余的n-1-1个顶点，则称个顶点，则称D D是是n阶有向完全图阶有向完全图。设设D D为为n阶有向简单图，若阶有向简单图，若D D的基图为的基图为n阶无向完全图阶无向完全图K Kn，则称则称D D是是n阶竞赛图阶竞赛图。完全图定义完全图定义1.6 1.6 设设G G为为n n阶无向简单图，若阶无向简单图，若G G中每个顶点均与其中每个顶点均与其38“雪亮工程雪亮工程是以区（县）、乡（镇）、村（社区）三级综治中心为指挥平台、以综治信息化为支撑、以网格化管理为基础、以公共安全视频监控联网应用为重点的是以区（县）、乡（镇）、村（社区）三级综治中心为指挥平台、以综治信息化为支撑、以网格化管理为基础、以公共安全视频监控联网应用为重点的“群众性治安防控工程群众性治安防控工程”。完全图举例完全图举例完全图举例完全图举例n阶无向完全图的边数为：阶无向完全图的边数为：n(n-1)/2-1)/2n阶有向完全图的边数为：阶有向完全图的边数为：n(n-1)-1)n阶竞赛图的边数为：阶竞赛图的边数为：n(n-1)/2-1)/2K5 53 3阶有向完全图阶有向完全图4 4阶竞赛图阶竞赛图完全图举例完全图举例n n阶无向完全图的边数为：阶无向完全图的边数为：n(n-1)/2K53n(n-1)/2K53阶阶39“雪亮工程雪亮工程是以区（县）、乡（镇）、村（社区）三级综治中心为指挥平台、以综治信息化为支撑、以网格化管理为基础、以公共安全视频监控联网应用为重点的是以区（县）、乡（镇）、村（社区）三级综治中心为指挥平台、以综治信息化为支撑、以网格化管理为基础、以公共安全视频监控联网应用为重点的“群众性治安防控工程群众性治安防控工程”。正则图正则图正则图正则图定义定义1.71.7 设设G G为为n阶无向简单图，若阶无向简单图，若vV(G)V(G)，均有均有d(v)k，则则称称G G为为k-正则图正则图。举例举例n阶零图是阶零图是0-0-正则图正则图n阶无向完全图是阶无向完全图是(n-1)-1)-正则图正则图彼得森图是彼得森图是3-3-正则图正则图说明说明n阶阶k-正则图中，边数正则图中，边数mkn/2/2。当当k为奇数时，为奇数时，n必为偶数。必为偶数。正则图定义正则图定义1.7 1.7 设设G G为为n n阶无向简单图，若阶无向简单图，若vV(G)vV(G)，均有，均有40“雪亮工程雪亮工程是以区（县）、乡（镇）、村（社区）三级综治中心为指挥平台、以综治信息化为支撑、以网格化管理为基础、以公共安全视频监控联网应用为重点的是以区（县）、乡（镇）、村（社区）三级综治中心为指挥平台、以综治信息化为支撑、以网格化管理为基础、以公共安全视频监控联网应用为重点的“群众性治安防控工程群众性治安防控工程”。子图子图子图子图定义定义1.81.8 设设G ，G 为两个图为两个图(同为无向图或同同为无向图或同为有向图为有向图)，若，若V V且且E E，则称则称G G 是是G G的的子图子图，G为为G 的的母图母图，记作，记作G G。若若V V或或E E，则称则称G 为为G的的真子图真子图。若若V V，则称则称G 为为G的的生成子图生成子图。注注:定义中一定是先要保证定义中一定是先要保证G G是图这个前提是图这个前提.子图定义子图定义1.8 1.8 设设G G，G G V 为两为两41“雪亮工程雪亮工程是以区（县）、乡（镇）、村（社区）三级综治中心为指挥平台、以综治信息化为支撑、以网格化管理为基础、以公共安全视频监控联网应用为重点的是以区（县）、乡（镇）、村（社区）三级综治中心为指挥平台、以综治信息化为支撑、以网格化管理为基础、以公共安全视频监控联网应用为重点的“群众性治安防控工程群众性治安防控工程”。子图子图子图子图设设G 为一图，为一图，V1 1 V且且V1 1，称以称以V1 1为顶点集，以为顶点集，以G中中两个端点都在两个端点都在V1 1中的边中的边组成边集组成边集E1 1的图为的图为G的的V1 1导出的子导出的子