图论及应用第一章完整作业

电子科技大学研究生试题《图论及其应用》(参考答案)考试时间：120分钟一．填空题(每题3分，共18分)1．4个顶点的不同构的简单图共有__11___个；2．设无向图G 中有12条边，已知G 中3度顶点有6个，其余顶点的度数均小于3。

则G 中顶点数至少有__9___个；3．设n 阶无向图是由k(k ?2)棵树构成的森林，则图G 的边数m= _n-k____;4．下图G 是否是平面图？答__是___; 是否可1-因子分解？答__是_.5．下图G 的点色数=)(G χ______, 边色数=')(G χ__5____。

图G二．单项选择(每题3分，共21分)1．下面给出的序列中，是某简单图的度序列的是( A )(A) (11123); (B) (233445); (C) (23445); (D) (1333).2．已知图G 如图所示，则它的同构图是（ D ）3． 下列图中，是欧拉图的是（ D ）4． 下列图中，不是哈密尔顿图的是（B ）5． 下列图中，是可平面图的图的是（B ）AC DA B CD6．下列图中，不是偶图的是（ B ）7．下列图中，存在完美匹配的图是（B ）三．作图(6分)1．画出一个有欧拉闭迹和哈密尔顿圈的图；2．画出一个有欧拉闭迹但没有哈密尔顿圈的图；3．画出一个没有欧拉闭迹但有哈密尔顿圈的图；解： 四．(10分)求下图的最小生成树，并求其最小生成树的权值之和。

解：由克鲁斯克尔算法的其一最小生成树如下图：权和为：20.五．(8分)求下图G 的色多项式P k (G).解：用公式(G P k -G 的色多项式：)3)(3)()(45-++=k k k G P k 。

六．(10分) 22，n 3个顶点的度数为3，…，n k 个顶点的度数为k ，而其余顶点的度数为1，求1度顶点的个数。

解：设该树有n 1个1度顶点，树的边数为m.一方面：2m=n 1+2n 2+…+kn k另一方面：m= n 1+n 2+…+n k -1 v v 13图G由上面两式可得：n 1=n 2+2n 3+…+(k -1)n k七．证明：(8分) 设G 是具有二分类(X,Y)的偶图，证明(1)G 不含奇圈；（2）若|X |≠|Y |，则G 是非哈密尔顿图。

图论及其应用习题答案图论及其应用习题答案图论是数学的一个分支，研究的是图的性质和图之间的关系。

图是由节点和边组成的，节点表示对象，边表示对象之间的关系。

图论在计算机科学、电子工程、物理学等领域有着广泛的应用。

下面是一些图论习题的解答，希望对读者有所帮助。

1. 问题：给定一个无向图G，求图中的最大连通子图的节点数。

解答：最大连通子图的节点数等于图中的连通分量个数。

连通分量是指在图中，任意两个节点之间存在路径相连。

我们可以使用深度优先搜索（DFS）或广度优先搜索（BFS）来遍历图，统计连通分量的个数。

2. 问题：给定一个有向图G，判断是否存在从节点A到节点B的路径。

解答：我们可以使用深度优先搜索（DFS）或广度优先搜索（BFS）来遍历图，查找从节点A到节点B的路径。

如果能够找到一条路径，则存在从节点A到节点B的路径；否则，不存在。

3. 问题：给定一个有向图G，判断是否存在环。

解答：我们可以使用深度优先搜索（DFS）或广度优先搜索（BFS）来遍历图，同时记录遍历过程中的访问状态。

如果在搜索过程中遇到已经访问过的节点，则存在环；否则，不存在。

4. 问题：给定一个加权无向图G，求图中的最小生成树。

解答：最小生成树是指在无向图中，选择一部分边，使得这些边连接了图中的所有节点，并且总权重最小。

我们可以使用Prim算法或Kruskal算法来求解最小生成树。

5. 问题：给定一个有向图G，求图中的拓扑排序。

解答：拓扑排序是指将有向图中的节点线性排序，使得对于任意一条有向边(u, v)，节点u在排序中出现在节点v之前。

我们可以使用深度优先搜索（DFS）或广度优先搜索（BFS）来遍历图，同时记录节点的访问顺序，得到拓扑排序。

6. 问题：给定一个加权有向图G和两个节点A、B，求从节点A到节点B的最短路径。

解答：我们可以使用Dijkstra算法或Bellman-Ford算法来求解从节点A到节点B的最短路径。

这些算法会根据边的权重来计算最短路径。

第三章1.证明： 必要性：v 是连通图G 的割边， 则， 至少有两个连通分支。

设其中一个连通分支顶点集合为V1,另外连通分支顶点集合为V2,即V1与V2构成V 的划分。

对于任意的u ∈V1, v ∈V2，如果割边e 不在某一条（u ，v ）路上，那么，该路也是连接G-e 中的u 与v 的路，这与u,v 处于G-v 的不同分支矛盾。

“充分性”若e 不是图G 的割边，那么G-v 连通，因此在G-v 中存在u,v 路，当然也是G 中一条没有经过边e 的u,v 路。

矛盾。

7.证明： v 是单图G 的割点，则G-v 至少两个连通分支。

现任取 , 如果x,y 在G-v 的同一分支中，令u 是与x,y 处于不同分支的点，那么，通过u ，可说明，x 与y 在G-v 的补图中连通。

若x,y 在G-v 的不同分支中，则它们在G-v 的补图中邻接。

所以，若v 是G 的割点，则v 不是其补图的割点。

9.连通图G 的一个子图B 称为是G 的一个块，如果(1), 它本身是块；(2), 若没有真包含B 的G 的块存在。

又由于对于阶数至少是3的()()G e G ωω->图G是块当且仅当G无环并且任意两点都位于同一圈上。

根据题意，对于阶数至少是3的图G，由于G没有偶圈，所以G的每个块的点可以在奇圈上，如果不在奇圈上，则块只能是K2，否则如果不是K2的话，该子图将存在割点，该子图就不是块。

得证。

16.（1）（2）（3）第四章3. （1）既是欧拉闭迹又是哈密尔顿圈（2）（3）（4）7.由于图没有奇度顶点，所以是欧拉图，又定理1可得，图G的边集可以划分为圈C1，C2，。

Cm，所以E（G）可以表示成C1，C2.。

Cm的并。

10.若图不是二连通，则存在割点，由于哈密尔顿图不存在割点，因而G是非哈密尔顿图。

若G是具有二分类（X,Y）的偶图，且|X|不等于|Y|，设X中所有点为x1，x2.。

xm，Y中的所有点为y1，y2.。

yn，若存在哈密尔顿图，则在哈密尔顿圈中必然存在X中的点与Y中的点相互交替出现，但是|X|不等于|Y|，则必然出现某两个点同属于|X|或者|Y|，但是G是偶图，属于同一集合的这样的两个点不可以相连，所以存在哈密尔顿圈矛盾，因而不存在哈密尔顿圈。

《图论及其应用》大作业指导老师郝荣霞知行1503 徐鹏宇 152912002.1.9证明：若G是森林且恰有2k个奇点，则在G中有k条边不重的路P1,P2......P K,使得E(G)=E(P1) E(P2) ...... E(P K)。

证明：对奇点数k使用数学归纳法。

①当k=1时，G是森林，且有且只有2个奇点⇒G只能为一颗树，且G的所有奇度顶点为两个1度顶点⇒G是一条路⇒满足题设②假设当k=t时，结论成立。

接下来考虑k=t + 1时的情况。

在G中一个分支中取两个叶子点u与v，令P是连接该两个顶点的唯一路。

由于P上除u，v以外的点均被P经过两次，即G-P后除u，v以外的点奇偶性不变。

⇒则G–P是有2t个奇度顶点的森林⇒由归纳假设知，G–P可以分解为t条边不重合的路之并，即E(G-P)=E(P1) E(P2) ...... E(P t)。

⇒则G可分解为t+1条边不重合的路之并，即E(G)=E(P1) E(P2) ...... E(P t) E(P)。

⇒即证。

2.4.4证明：若e 是K n 的边，则τ（K n -e ）=（n-2）n n-3证明：由定理2.9：τ（K n ）=n n-2由于τ（K n -e ）=τ（K n ）-τ（含有e 的生成树棵树）现在需要求含有e 的生成树棵树，τ（含有e 的生成树棵树）=)1(21n 1-n 2-n n n ）（=2n n-3τ（K n -e ）=τ（K n ）-τ（含有e 的生成树棵树）=（n-2）n n-33.2.4证明：不是块的连通图至少有两个块，其中每个恰有一个割点。

证明：设G 为不是块的连通图，由于G 连通且不是块⇒G 有割点①当G 只有1个割点v 时，延割点分开，G1，G2内无割点，且连通，由块的定义知⇒G1,G2是块，且分别含一个割点v 。

②当G 含有2个及2个以上割点时，取相距距离最远的两个割点u 和v ，此时分G 为三部分G1,G2,G3。

习题一1. 一个工厂为一结点；若两个工厂之间有业务联系，则此两点之间用边相联；这样就得到一个无向图。

若每点的度数为3,则总度数为27,与图的总度数总是偶数的性质矛盾。

若仅有四个点的度数为偶数，则其余五个点度数均为奇数，从而总度数为奇数，仍与图的总度数总是偶数的性质矛盾。

（或者利用度数为奇数的点的个数必须为偶数个）m <= (n-1)( n-2)/2,与题设矛盾。

3•记a i为结点V i的正度数，a「为结点V i的负度数，则n n n nv a j 2「[ (n -1) - a" ]2 = n(n -1)2-2( n-1)、a「a「i 4 i 4n因为Z a「= c n = n(n -1)/2,i討4. 用向量（a1,a2,a3）表示三个量杯中水的量，其中a i为第i杯中水的量,i = 1,2,3.以满足a1+a2+a3 = 8 （a1,a2,a3为非负整数）的所有向量作为各结点，如果⑻耳厲）中某杯的水倒满另一杯得到（a' a' a'）,则由结点到结点画一条有向边。

这样可得一个有向图。

本题即为在此图中找一条由（8, 0, 0 ）到（4, 4, 0 ）的一条有向路，以下即是这样的一条：(8 0 0 ).(5 0 3 )■( 5 3 0 )• f 0 Q \(2, 5, 1 ) (8, 0, 0丿 f ( 5, 0, 3丿r ( 5, 3, 0丿----- r■t / 4 4 O \ -----►(4, 4, 0 )T(7, 0, 1 )■ ( 7, 1, 0 )1^ ( 4, 1, 3 )5. 可以。

6若9个人中没有4个人相互认识，构造图G,每个点代表一个点，两个人相互认识则对应的两个点之间有边。

1）若可以找到点v, d（v）＞5，则与v相连的6个点中，要么有3个相互认识，要么有3个相互不认识（作K6并给边涂色：红=认识，蓝=不认识，只要证图中必有同色三角形。

)2214(题后两个算法不作要求题，除第图的基本概念<1.>若G 是简单图，证明：()()2V G E G ⎛⎫≤ ⎪⎝⎭。

证明：()()1()()()1v Gd v V G d v V G V G ∈≤-∴≤-∑（当且仅当G 是完全图时取等号） 又11()()()()122v G E G d v V G V G ∈=≤-∑ ()()2V G E G ⎛⎫∴≤ ⎪⎝⎭。

<2.>设G 是(,)p q 简单图，且12p q -⎛⎫>⎪⎝⎭。

求证G 为连通图。

证明：反证法，假设G 为非连通图。

设G 有两个连通分支1G 和2G ，且112212()1,()1,V G p V G p p p p =≥=≥+= 则1212()()22p p E G E G q ⎛⎫⎛⎫+=≤+⎪ ⎪⎝⎭⎝⎭而1211221(1)(1)(1)(2)222222p p p p p p p p p -⎛⎫⎛⎫⎛⎫----+-=+-⎪ ⎪ ⎪⎝⎭⎝⎭⎝⎭2222221212121222()2()222p p p p p p p p p p +-+-+-+++-==12(1)(1)0p p =--≤（因为121,1p p ≥≥），矛盾。

<3.>超图H 是有序二元组((),())V H E H ，其中()V H 是顶点非空有限集合，()E H 是()V H 的非空子集簇，且()()i i E E H E V H ∈=。

其中，()E H 中的元素i E 称为超图的边，没有相同边的超图称为简单超图。

证明：若H 是简单超图，则21υε≤-，其中,υε分别是H 的顶点数和边数。

证明：()V H υ=，有一条边的子集个数为1υ⎛⎫ ⎪⎝⎭，有i 条边的子集个数为,1,,.i n i υ⎛⎫= ⎪⎝⎭又02,211i i υυυυυυυ=⎛⎫⎛⎫⎛⎫=∴++=- ⎪ ⎪ ⎪⎝⎭⎝⎭⎝⎭∑ 。

<4.>若G 是二部图，则2()()4V G E G ≤。

习 题 11. 证明在n 阶连通图中（1） 至少有n -1条边。

（2） 如果边数大于n -1，那么至少有一条闭通道。

（3） 如恰有n -1条边，那么至少有一个奇度点。

证明 (1) 假设对∀v ∈V(G),有d(v)≥2,那么：2m=∑d(v)≥2n ⇒ m ≥n >n-1,矛盾！ 假设G 中有1度顶点，对顶点数n 作数学归纳。

当n=2时，G 显然至少有一条边，结论成立。

设当n=k 时，结论成立，当n=k+1时，设d(v)=1，那么G-v 是k 阶连通图，因此至少有k-1条边，所以G 至少有k 条边。

(2) 考虑v 1→v 2→⋯→v n 的途径，假设该途径是一条路，那么长为n-1,但图G 的边数大于n-1,因此存在v i ,v j ,使得v i adgv j ,这样，v i →v i+1→⋯→v j 并上v i v j 构成一条闭通道；假设该途径是一条非路，易知，图G 有闭通道。

(3) 假设不然，对∀v ∈V(G),有d(v)≥2,那么：2m=∑d(v)≥2n ⇒ m ≥n >n-1,与矛盾！ 2. 设G 是n 阶完全图，试问（1） 有多少条闭通道？（2） 包含G 中某边e 的闭通道有多少？ （3） 任意两点间有多少条路？答 (1) (n-2)! (2) (n-1)!/2 (3) 1+(n-2)+(n-2)(n-3)+(n-2)(n-3)(n-4)+…+(n -2)…1.3. 证明图1-27中的两图不同构：证明 容易观察出两图中的点与边的邻接关系各不相同，因此，两图不同构。

4. 证明图1-28中的两图是同构的证明 将图1-28的两图顶点标号为如下的(a)与(b)图图1-27 图1-28作映射f : f(v i )→u i (1≤ i ≤ 10)容易证明，对∀v i v j ∈E((a)),有f(v i v j )=u i u j ∈E((b)) (1≤ i ≤ 10, 1≤j ≤ 10 ) 由图的同构定义知，图1-27的两个图是同构的。

图论及应用习题答案图论及应用习题答案图论是数学中的一个分支，研究的是图的性质和图之间的关系。

图论在现实生活中有着广泛的应用，涵盖了许多领域，如计算机科学、通信网络、社交网络等。

本文将为读者提供一些关于图论及应用的习题答案，帮助读者更好地理解和应用图论知识。

1. 图的基本概念题目：下面哪个不是图的基本概念？A. 顶点B. 边C. 路径D. 线段答案：D. 线段。

图的基本概念包括顶点、边和路径。

线段是指两个点之间的连线，而在图论中，我们使用边来表示两个顶点之间的关系。

2. 图的表示方法题目：以下哪个不是图的表示方法？A. 邻接矩阵B. 邻接表C. 边列表D. 二叉树答案：D. 二叉树。

图的表示方法包括邻接矩阵、邻接表和边列表。

二叉树是一种特殊的树结构，与图的表示方法无关。

3. 图的遍历算法题目：以下哪个不是图的遍历算法？A. 深度优先搜索B. 广度优先搜索C. 迪杰斯特拉算法D. 克鲁斯卡尔算法答案：D. 克鲁斯卡尔算法。

图的遍历算法包括深度优先搜索和广度优先搜索，用于遍历图中的所有顶点。

迪杰斯特拉算法是用于求解最短路径的算法，与图的遍历算法有所不同。

4. 最小生成树题目：以下哪个算法不是用于求解最小生成树？A. 克鲁斯卡尔算法B. 普里姆算法C. 弗洛伊德算法D. 公交车换乘算法答案：D. 公交车换乘算法。

最小生成树是指包含图中所有顶点的一棵树，使得树的边的权重之和最小。

克鲁斯卡尔算法和普里姆算法是常用的求解最小生成树的算法，而弗洛伊德算法是用于求解最短路径的算法，与最小生成树问题有所不同。

5. 图的应用题目：以下哪个不是图的应用？A. 社交网络分析B. 路径规划C. 图像处理D. 数字逻辑电路设计答案：D. 数字逻辑电路设计。

图的应用广泛存在于社交网络分析、路径规划和图像处理等领域。

数字逻辑电路设计虽然也涉及到图的概念，但与图的应用有所不同。

总结：图论是一门重要的数学分支，具有广泛的应用价值。

通过本文提供的习题答案，读者可以更好地理解和应用图论知识。

学号：201321010808 姓名：马涛习题14．证明图1-28中的两图是同构的证明 将图1-28的两图顶点标号为如下的(a)与(b)图作映射f : f(v i )→u i (1≤ i ≤ 10)容易证明，对∀v i v j ∈E((a)),有f(v i v j )=u i u j ∈E((b)) (1≤ i ≤ 10, 1≤j ≤ 10 ) 由图的同构定义知，图1-27的两个图是同构的。

6．设G 是具有m 条边的n 阶简单图。

证明：m =⎪⎪⎭⎫⎝⎛2n 当且仅当G 是完全图。

证明 必要性 若G 为非完全图，则∃ v ∈V(G),有d(v)< n-1 ⇒ ∑ d(v) < n(n-1) ⇒ 2m <n(n-1)⇒ m < n(n-1)/2=⎪⎪⎭⎫⎝⎛2n , 与已知矛盾！充分性 若G 为完全图，则 2m=∑ d(v) =n(n-1) ⇒ m= ⎪⎪⎭⎫⎝⎛2n 。

9.证明：若k 正则偶图具有二分类V = V 1∪V 2，则 | V 1| = |V 2|。

(a)v 1v 2 v 3 v 4v 5 v 6v 7v 8 v 9v 10 u 1 u 2u 3u 4u 5 u 6 u 7 u 8 u 9 u 10 (b)证明 由于G 为k 正则偶图，所以，k | V 1 | =m = k | V 2 | ⇒ ∣V 1∣= ∣V 2 ∣。

12.证明：若δ≥2，则G 包含圈。

证明 只就连通图证明即可。

设V(G)=｛v 1,v 2,…,v n ｝,对于G 中的路v 1v 2…v k ,若v k 与v 1邻接，则构成一个圈。

若v i1v i2…v in 是一条路，由于δ≥ 2，因此，对v in ，存在点v ik 与之邻接，则v ik ⋯v in v ik 构成一个圈 。

17.证明：若G 不连通，则G 连通。

证明 对)(,_G V v u ∈∀,若u 与v 属于G 的不同连通分支，显然u 与v 在_G 中连通；若u 与v 属于g 的同一连通分支，设w 为G 的另一个连通分支中的一个顶点，则u 与w ，v 与w 分别在_G 中连通，因此，u 与v 在_G 中连通。

图论及应用参考答案图论及应用参考答案图论是数学中的一个重要分支，研究的是图的性质和图之间的关系。

图由节点（顶点）和边组成，节点代表对象，边代表对象之间的关系。

图论不仅在数学中有广泛的应用，也在计算机科学、物理学、生物学等领域中发挥着重要的作用。

本文将介绍图论的基本概念和一些应用。

一、图论的基本概念1. 图的类型图分为有向图和无向图。

有向图中的边有方向，表示节点之间的单向关系；无向图中的边没有方向，表示节点之间的双向关系。

2. 图的表示方法图可以用邻接矩阵或邻接表来表示。

邻接矩阵是一个二维数组，其中的元素表示节点之间是否有边相连；邻接表是一个链表数组，数组中的每个元素对应一个节点，链表中存储了该节点相邻的节点。

3. 图的性质图的性质包括节点的度、连通性和路径等。

节点的度是指与该节点相连的边的数量；连通性指的是图中任意两个节点之间是否存在路径；路径是指由边连接的节点序列。

二、图论在计算机科学中的应用1. 最短路径算法最短路径算法是图论中的经典问题之一，它用于计算图中两个节点之间的最短路径。

著名的最短路径算法有迪杰斯特拉算法和弗洛伊德算法。

这些算法在网络路由、地图导航等领域中有广泛的应用。

2. 最小生成树算法最小生成树算法用于找到一个连通图的最小生成树，即包含所有节点且边的权重之和最小的子图。

普里姆算法和克鲁斯卡尔算法是常用的最小生成树算法。

这些算法在电力网络规划、通信网络设计等领域中有重要的应用。

3. 图的着色问题图的着色问题是指给定一个图，将每个节点着上不同的颜色，使得相邻节点之间的颜色不同。

这个问题在地图着色、任务调度等方面有实际应用。

三、图论在物理学中的应用1. 粒子物理学在粒子物理学中，图论被用来描述和分析粒子之间的相互作用。

图论模型可以帮助研究粒子的衰变、散射等过程，为理解物质的基本结构提供了重要的工具。

2. 统计物理学图论在统计物理学中也有应用。

例如，渗透模型中的图可以用来研究流体在多孔介质中的渗透性质，为石油勘探、水资源管理等提供了理论基础。

电子科技大学研究生试题《图论及其应用》(参考答案)考试时间：120分钟一．填空题(每题3分，共18分)1．4个顶点的不同构的简单图共有__11___个；2．设无向图G 中有12条边，已知G 中3度顶点有6个，其余顶点的度数均小于3。

则G 中顶点数至少有__9___个；3．设n 阶无向图是由k(k ≥2)棵树构成的森林，则图G 的边数m= _n-k____;4．下图G 是否是平面图？答__是___; 是否可1-因子分解？答__是_.5．下图G 的点色数=)(G χ______, 边色数=')(G χ__5____。

图G图G二．单项选择(每题3分，共21分)1．下面给出的序列中，是某简单图的度序列的是( A )(A) (11123); (B) (233445); (C) (23445); (D) (1333).2．已知图G 如图所示，则它的同构图是（ D ）3． 下列图中，是欧拉图的是（ D ）4． 下列图中，不是哈密尔顿图的是（B ）5． 下列图中，是可平面图的图的是（B ）A Bb c123A B 3CDAD6．下列图中，不是偶图的是（ B ）7．下列图中，存在完美匹配的图是（B ）三．作图(6分)1．画出一个有欧拉闭迹和哈密尔顿圈的图；2．画出一个有欧拉闭迹但没有哈密尔顿圈的图；3．画出一个没有欧拉闭迹但有哈密尔顿圈的图；解：四．(10分)求下图的最小生成树，并求其最小生成树的权值之和。

A B DC123A B DC解：由克鲁斯克尔算法的其一最小生成树如下图：权和为：20.五．(8分)求下图G 的色多项式P k(G).解：用公式)()()(e G P G P e G P k k k •+=-，可得G 的色多项式：)3)(2()1()()(3)()(2345---=++=k k k k k k k G P k 。

六．(10分) 一棵树有n 2个顶点的度数为2，n 3个顶点的度数为3，…，n k 个顶点的度数为k ，而其余顶点的度数为1，求1度顶点的个数。

图论作业 1⼀、填空题1. ⾮同构的阶和阶树的个数分别为和⽅法：按照树中存在的最⻓路进⾏枚举 (从开始)注意：对于的树来说，路的最短⻓度为234 阶树2345 阶树2. 阶正则图的补图的边数为考点⼀：完全图每个点的度数是✨考点⼆：⼀个图和其补图的并是完全图⼀个点在原图和补图中的度数和为图是正则，那么图的补图为正则。

故补图的度数之和为根据握⼿定理：3. 设图中各顶点度数均为，且，则 n = ，m =考点：握⼿定理根据握⼿定理：4. 设简单图的邻接矩阵为，且则图的边数为考点：邻接矩阵的性质定理 10：令是⼀个有推⼴邻接矩阵的阶标定图，则的⾏列元素等于由到的⻓度为的途径的数⽬推论：设为简单图的邻接矩阵，则：的元素是的度数。

的元素是含的三⻆形的数⽬的两倍 （考过填空）5. 设是⼀个完全部图，是第部分的顶点数，则它的边数为考点：完全多部图的概念与结构完全部图的点数：；边数：（考过填空）6. 设是阶简单图，且不含完全⼦图，则其边数⼀定不会超过考点：Turán 定理定理 18 (T urán)：若是阶简单图，并且不包含，则边数。

此外，仅当时，✨计算公式：，则例：阶简单图，，则最多有条边例： 9 阶简单图，，则最多有 27 条边7. 设阶图是具有个分⽀的森林，则其边数为树的边数 = 顶点数 - 1森林的边数 = 顶点数 - 连通分⽀数8. ⼀棵树有个度为的结点，，则它有个度数为的顶点考点：握⼿定理 + 树的性质（边数 = 顶点数 - 1），其中由握⼿定理：故：整理得：9. 完全图的⽣成树的个数为定理 27：⼆、不定项选择题1. 关于图的度序列，下列命题正确的是（ABCD）A. 同构的两个图的度序列相同B. ⾮负整数序列是图的度序列当且仅当是偶数C. 如果正整数序列是⼀棵树的度序列且，那么序列中⾄少有两个D. 正整数序列是⾮平凡树的度序列当且仅当E. 若图的顶点度数之和⼤于等于图的顶点度数之和，则图度优于图❌F. 如果⾮负整数序列是简单图的度序列，那么在同构意义下只能确定⼀个图❌考点：度序列 && 图序列关系：简单图的度序列简称图序列注意：判断⾮负整数序列是否为简单图的度序列暂⽆好的⽅法，只有等价转换的⽅法A 显然正确（已经默认递增或递减排列）B 正确：定理 3：⾮负整数组是图的度序列的充分必要条件是：为偶数C 正确：定理 20：每棵⾮平凡树⾄少有两⽚树叶D 正确：存在⼀棵⾮平凡树，以该序列为度序列的充要条件握⼿定理E 错误：先有度弱或度优，才有度数之和⼩于或⼤于；反过来不成⽴F 错误：不⽌确定⼀个图2. 对于序列，下列说法正确的是（BD）A. 可能是简单图的度序列❌B. ⼀定不是简单图的度序列C. 只能是简单图的度序列❌D. 只能是⾮简单图的度序列E. 不是任意图的度序列❌考点：度序列 && 图序列对于简单图，顶点的最⼤度顶点数 - 1A 错B 对C 错：对于该题，⻓度为 6，说明有 6 个点，同时最⼤度为 7，显然不是简单图！！D 对E 错：定理 3：⾮负整数组是图的度序列的充分必要条件是：为偶数3. 下列说法错误的是（ACE）A. 若⼀个图中存在闭途径，则⼀定存在圈❌B. 偶图中不存在奇圈C. 若图不含三⻆形，则为偶图❌D. 图的顶点之间的连通关系⼀定是等价关系E. 存在每个顶点的度数互不相同的⾮平凡简单图❌A 错误：闭途径（），但不存在圈B 正确：定理 9：⼀个图是偶图当且仅当它不包含奇圈C 错误：可能存在⻓度不为 3 的奇圈，如 5，7 等等D 正确：即便在有向图中，也存在弱连通E 错误：定理 5：⼀个简单图的个点的度不能互不相同4. 关于简单图的邻接矩阵，下列说法错误的是（C）A. 矩阵的⾏和等于该⾏对应顶点的度数B. 矩阵的所有元素之和等于该图边数的倍C. 矩阵的所有特征值之和等于该图边数的倍❌D. 矩阵的所有特征值的平⽅和等于该图边数的倍E. 矩阵的主对⻆线的元素之和等于该图边数的倍F. 若是⾮连通图，则相似于某个准对⻆矩阵考点：简单图邻接矩阵的性质A 正确：矩阵的「⾏和」或「列和」等于该「⾏」或「列」对应顶点的度数B 正确：所有元素之和等于度数之和，根据握⼿定理判断正确C 错误：矩阵的所有特征值之和等于矩阵的迹；矩阵的迹⼜是矩阵主对⻆线上的元素之和；对于简单图，邻接矩阵主对⻆线元素均为D 正确：所有特征值的平⽅和等于的所有特征值之和；的迹就是主对⻆线之和，也就是图的所有度数之和，就等于边数的两倍E 显然正确F 正确：⽆法解释，因为不懂5. 图⼀定是树的是（BDE）A. 连通图❌B. ⽆回路但任意添加⼀条边后有回路的图C. 每对顶点间都有路的图❌D. 连通且E. ⽆圈且考点：树的基本性质A 错误：树是连通的⽆圈图B 正确：回路是边不重圈的并；⽆回路肯定⽆圈，加⼀条边有回路，肯定就有圈C 错误：每对顶点间存在唯⼀的⼀条路DE 显然正确三、解答题1. 设⽆向图 有条边， 度与 度顶点各 个，其余顶点度数均⼩于 ，问 中⾄少有⼏个顶点？在顶点数最少的情况下，写出 的度序列，该度序列是⼀个图序列吗？考点：握⼿定理 + 图序列解：由于求顶点数量最少，故假设 0 度顶点为 0 个，1 度顶点为 0 个，同时设 2 度顶点有 个根据握⼿定理得：；解得：所以 中⾄少有 7 个顶点；图 的度序列为 根据 Havel-Hakimi 定理，可得下⾯推导过程：显然 是可图的，所以 是可图的2. 证明整数序列是简单图的度序列，并构造⼀个对应的简单图。

第一章图和子图§1.1 图和简单图°图的概念：一个图G是指一个有序三元组G=(V G,E G,ψG)。

其中：V(G)是非空顶点集，E(G)是不与V(G)相交的边集，ψG:E(G)→V(G)×V(G)的函数，称为关联函数。

若e∈E(G)是一条边，而ψG e=u,v,则称e连接u和v; 顶点u 和v称为e的端点。

例1：G=(V G,E G,ψG)，其中：V G={v1,v2,v3,v4,v5}E G={e1,e2,e3,e4,e5,e6,e7,e8}而ψG定义为：ψG e1=v1,v2ψG e2=(v2,v3)ψG e3=v3,v3ψG e4=(v3,v4)ψG e5=v2,v4ψG e6=(v4,v5)ψG e7=v2,v5ψG e8=(v2,v5)(见图1.1)*我们现在讨论的是无向图，即边没有方向，顶点对u,v=(v,u)。

我们还可以定义有向图。

例2：定义有向图D=(V D,E D,ψD)，其中：V D={a,b,c,d}E D={e1,e2,e3,e4,e5,e6,e7}ψD e1=<a,a>ψD e2=<a,b>ψD e3=<a,b>ψD e4=<a,d>ψD e5=<c,b>ψD e6=<d,c>ψD e7=<c,d>*这里ψD e=<u,v>，表示e是一条从u到v的弧。

<u,v>≠<v,u>。

°υ=V G,ε=|E G|分别表示图G的顶点数和边数，|V G|=n称为n阶图。

°若V G和|E G|均为有限数，则称G为有限图。

° E G=∅时，则称G为零图，υ=1的零图称为平凡图。

° V G=∅时，则称G为空图。

°邻接相邻：若e k=u,v∈E(G)，称u和v邻接。

°关联：若e k=u,v∈E(G)，则称e k与u和v关联。