下载文档原格式
第二章 图的连通性在第一章中已经定义连通图是任二顶点间都有路相连的图。
对于连通图，其连通的程度也有高有低。
例如，下列三个图都是连通图。
对于图G 1，删除一条边或一个顶点便可使其变得不连通；而对于图G 2，至少需要删除两条边才能使其不连通，也可以删除一个顶点使其不连通；对于图G 3，要破坏其连通性，则至少需要删除三条边或三个顶点。
本章主要讨论如何通过图的顶点集、边集和不交的路集合的结构性质来获知图的连通性程度。
通过研究割边和割点来刻画1连通图的特性；定义连通度和边连通度来度量连通图连通程度的高低；通过不交路结构和元素的共圈性质来反映图的2连通和k 连通性。
§2.1 割点和割边定义2.1.1 设)(G V v ∈，如果)()(G w v G w >−，则称v 为G 的一个割点。
（注：该定义与某些著作中的定义有所不同，主要是在环边的顶点是否算作割点上有区别）。
例如，下图中u , v 两点是其割点。
定理2.1.1 如果点v 是简单图G 的一个割点，则边集E (G)可划分为两个非空子集1E 和2E ，使得][1E G 和][2E G 恰好有一个公共顶点v 。
证明留作习题。
推论2.1.1 对连通图G ，顶点v 是G 的割点当且仅当v G −不连通。
定理2.1.2 设v 是树T 的顶点，则v 是T 的割点当且仅当1)(>v d 。
证明：必要性：设v 是T 的割点，下面用反证法证明1)(>v d 。
若0)(=v d ，则1K T ≅，显然v 不是割点。
若1)(=v d ，则v T −是有1)(−−v T ν条边的无圈图，故是树。
从而)(1)(T w v T w ==−。
因此v 不是割点。
以上均与条件矛盾。
充分性：设1)(>v d ，则v 至少有两个邻点u ,w 。
路uvw 是T 中一条),(w u 路。
因T 是树，uvw 是T 中唯一的),(w u 路，从而)(1)(T w v T w =>−。
离散数学顶点的度第2讲定义2.1设G=<V,E>为一无向图，∀v∈V称所有的边与v 的关联次数之和为v 的度数，简称为度，记作d G (v), 简记作d(v)。
记i v (e)为e 与v 的关联次数，则v e ∈Ed(v)=i (e)∑。
定义2.2设D=<V,E>为一有向图， v∈V,(1)称v作始点的边的条数为v的出度，记作d D+(v)，简记作d+(v)；(2)称v作为终点的边的条数为v的入度，记作d D-(v)，简记作d-(v)。
称d D+(v)+ d D-(v)为v的度数，记作d(v)。
在无向图G中，令⊿(G) = max{d(v)| v∈V(G) }δ(G) = min{d(v)| v∈V(G) }称⊿(G) ，δ(G)分别为G的最大度和最小度。
简记做⊿，δ。
在有向图D中，可类似定义⊿(D)、δ(D)。
另外，令⊿+(D) = max{d+(v)| v∈V(D) }δ+(D) = min{d+(v)| v∈V(D) }⊿-(D) = max{d-(v)| v∈V(D) }δ-(D) = min{d-(v)| v∈V(D) }分别称为D的最大出度、最小出度、最大入度、最小入度。
简记作⊿、δ、⊿+、δ+、⊿-、δ-。
注意称度为0的顶点为孤立点；称度为1的顶点为悬挂点，与其关联的边称为悬挂边。
称度为偶数的顶点称为偶点；称度为奇数的顶点称为奇点。
注意若图G的所有顶点的度相等, 则G称作正则图;若进一步所有顶点的度都等于k,则称G是k-正则图。
定理2.1设G=<V,E> 为任意无向图，, ,则即顶点度数之和等于边数的2倍。
，12n V={v ，v ，...，v }|E|=m nii=1d(v )=2m定理2.2推论2.3任意图中，奇点的个数一定是偶数。
设D=<V,E>为任意有向图，，，则。
12n V={v ，v ，...，v }|E|=m n n-i i i=1i=1d (v )=d (v )=m +∑∑设G=<V,E>为一n阶无向图，V={v1,v2,…,v n}, 称d(v1), d(v2), …, d(v n)为G的度序列。
图论习题二答案图论习题二答案图论是数学中的一个分支，研究的是图的性质和图之间的关系。
在图论中，有很多经典的习题可以帮助我们更好地理解和应用图的概念。
本文将探讨一些图论习题二的答案，帮助读者更好地理解和掌握图论的知识。
1. 习题：给定一个无向图G=(V,E)，其中V={1,2,3,4,5,6}，E={(1,2),(1,3),(2,3),(2,4),(3,4),(4,5),(4,6)}，求图G的邻接矩阵和关联矩阵。
答案：邻接矩阵是一个n×n的矩阵，其中n是图的顶点数。
对于无向图G，邻接矩阵的元素a[i][j]表示顶点i和顶点j之间是否存在边。
如果存在边，则a[i][j]=1，否则a[i][j]=0。
对于给定的图G，邻接矩阵为：0 1 1 0 0 01 0 1 1 0 01 1 0 1 0 00 1 1 0 1 10 0 0 1 0 00 0 0 1 0 0关联矩阵是一个n×m的矩阵，其中n是图的顶点数，m是图的边数。
对于无向图G，关联矩阵的元素b[i][j]表示顶点i和边j之间的关系。
如果顶点i是边j 的起点，则b[i][j]=-1；如果顶点i是边j的终点，则b[i][j]=1；否则b[i][j]=0。
对于给定的图G，关联矩阵为：-1 -1 0 0 0 01 0 -1 -1 0 00 1 1 0 0 00 0 0 1 -1 -10 0 0 0 1 00 0 0 0 0 12. 习题：给定一个有向图G=(V,E)，其中V={1,2,3,4,5}，E={(1,2),(1,3),(2,3),(2,4),(3,4),(4,1),(5,4)}，求图G的邻接表和深度优先搜索遍历结果。
答案：邻接表是一种图的表示方法，用于存储图中每个顶点的邻接顶点。
对于有向图G，邻接表中的每个元素表示该顶点的出边。
对于给定的图G，邻接表为：1: 2, 32: 3, 43: 44: 15: 4深度优先搜索（DFS）是一种图的遍历算法，用于遍历图中的所有顶点。
图论第二版答案【篇一：图论与代数结构第一二三章习题解答】厂为一结点；若两个工厂之间有业务联系，则此两点之间用边相联；这样就得到一个无向图。
若每点的度数为3，则总度数为27，与图的总度数总是偶数的性质矛盾。
若仅有四个点的度数为偶数，则其余五个点度数均为奇数，从而总度数为奇数，仍与图的总度数总是偶数的性质矛盾。
（或者利用度数为奇数的点的个数必须为偶数个） 2. 若存在孤立点，则m不超过kn-1的边数, 故m = (n-1)(n-2)/2, 与题设矛盾。
?－3. 记ai为结点vi的正度数，ai为结点vi的负度数，则nnnn? 2? 22－ai?[(n?1)?ai]?n(n?1)?2(n?1)ai＋ai－2， i?1i?1i?1i?1 nnn－2? 2 因为ai?cn?n(n?1)/2，所以ai?ai－ 2。
i?1i?1i?14. 用向量(a1,a2,a3)表示三个量杯中水的量, 其中ai为第i杯中水的量, i = 1,2,3.以满足a1+a2+a3 = 8 (a1,a2,a3为非负整数)的所有向量作为各结点, 如果(a1,a2,a3)中某杯的水倒满另一杯得到( a’1, a’2, a’3 ) , 则由结点到结点画一条有向边。
这样可得一个有向图。
本题即为在此图中找一条由( 8, 0, 0 )到( 4, 4, 0 )的一条有向路，以下即是这样的一条： ( 8, 0, 0 ) ( 5, 0, 3 ) ( 5, 3, 0 ) ( 2, 3, 3 ) ( 2, 5,1 )(7, 0, 1 ) ( 7, 1, 0 ) ( 4, 1, 3 ) ( 4, 4, 0 )5. 可以。
???????6 若9个人中没有4个人相互认识，构造图g，每个点代表一个点，两个人相互认识则对应的两个点之间有边。
1）若可以找到点v，d(v)5，则与v相连的6个点中，要么有3个相互认识，要么有3个相互不认识（作k6并给边涂色:红=认识，蓝=不认识，只要证图中必有同色三角形。
