学习《图论》这一章的要求二、知识点1．图的基本概念、结点度数与边数的关系公式；2.路径、拟路径、回路、通路、连通图与非连通图、强连通图与弱连通图、有向图与无向图；强分图、点割集、边割集；3.图的矩阵表示：邻接矩阵、可达性矩阵、关联矩阵、关联矩阵的秩与结点数的关系式。4.欧拉路、欧拉回路、欧拉图；哈密尔顿回路、哈密尔顿图；5.平面图、欧拉定理、平面图中结点数和边数之间的关系不等式；Kuratowski定理；6.对偶图与着色问题、四色假设及其验证。7.树、子树、生成树、带权树、最优树；8.根树、完全m叉树、二叉树、完全二叉树中分支点和通路长度之间的关系式。47-1图的基本概念一、图的定义例1：G=<V(G)，E(G)，G>其中V(G)={a，b，c，d}，E(G)={e1，e2，e3，e4，e5，e6}，G(e1)=(a，b)，G(e2)=(a，c)，G(e3)=(b，d)，G(e4)=(b，c)，G(e5)=(d，c)，G(e6)=(a，d)例2：G=<V(G)，E(G)，G>其中V(G)={a，b，c，d}，E(G)={e1，e2，e3，e4，e5，e6}，G(e1)=(a，b)，G(e2)=(a，c)，G(e3)=(b，d)，G(e4)=(b，c)，G(e5)=(d，c)，G(e6)=(a，d)2、边的分类：（1）无向边：如果E中边ei对应V中的结点对是无序的(u，v)称ei是无向边，记ei=(u，v)，称u，v是ei的两个端点。（2）有向边：如果ei与结点有序对<u，v>相对应，称ei是有向边，记ei=<u，v>，称u为ei的始点，v为ei的终点。3、图的分类：①无向图：每条边均为无向边的图称为无向图。②有向图：每条边均为有向边的图称为有向图。③混合图：有些边是无向边，有些边是有向边的图称为混合图。1、G1=<V1，E1>是无向图，其中V1={V1，V2，V3，V4，V5，V6}，E1={e1，e2，e3，e4，e5，e6}，e1=(V1，V3)，e2=(V1，V4)，e2=(V2，V4)，e3=(V3，V4)，e4=(V3，V6)，e5=(V4，V5)，e6=(V5，V6)4、点和边的关联：如ei=(u，v)或ei=<u，v>称u，v与ei关联。10、自回路(环)：关联于同一结点的边称为自回路，或称为环。二、点的度数（degree）1、点的度数的定义定义7-1.2：在图G=<V，E>，vV，与结点v关联的边数称为该点的度数，记为deg(v)。孤立结点的度数为0。【例】：G1是无向图，deg(v1)=3，deg(v2)=1G2是有向图，deg+(v1)=２，deg-(v1)=３，deg(v1)=5，3、最大度和最小度：图G最大度记为(G)=max{deg(v)|vV(G)}，最小度数记为(G)=min{deg(v)|vV(G)}。5、定理7-1.2在任何图中,度数为奇数的结点必定是偶数个。6、定理7-1.3：在任何有向图中，所有结点的入度之和等于所有结点的出度之和。三、特殊的图1、多重图定义7-1.4：含有平行边的图称为多重图。如果在Kn中，对每一条边任意确定一个方向，则称该图为n个结点的有向完全图。显然它的边数为n(n-1)/2。215、相对于完全图的补图定义7-1.6：给定一个简单图G，由G中所有结点和所有能使G成为完全图的添加边组成的图，称为G的相对于完全图的补图，或简称为G的补图，记为G。即G=<V，E1>，G=<V，E2>，其中E2={(u，v)u，vV，(u，v)E1}(一般指无向图）。6、子图定义7-1.7：设图G=<V，E>，如果有图G’=<V’，E’>，且E’E，V’V，则称G’为G的子图。当V’=V时，则称G’为G的生成子图。7、相对于图G的补图定义7-1.8：设G’=<V’，E’>是G=<V，E>的子图，若给定另一个图G”=<V”，E”>使得E”=E-E’，且V”中仅包含E”的边所关联的结点，则称G”是子图G’相对于图G的补图。2627两图同构的一些必要条件：1.结点数目相同；2.边数相等；3.度数相同的结点数目相等。练习：至少有两个结点的无向简单图有两个相同度数的结点。3031323334