图论_5_树

图论知到章节测试答案智慧树2023年最新长安大学

绪论单元测试

1. 下列选项中正确的是（ ）.

参考答案:

图论的研究对象是图;图论中图是顶点集合上的一种二元关系;图的结构是图论的重要研究方向之一;图论中的图由若干给定的顶点及连接某些顶点对的边所构成

2. 著名的哥尼斯堡七桥问题最初由哪位数学家给出解答（ ）.

参考答案:

欧拉

3. 在任意6个人的聚会上，总有3个人互相认识，或者3个人互不认识.（ ）

参考答案:

对

4. 图论中著名的中国邮递员问题是由中国管梅谷教授提出的.（ ）

参考答案:

对

5. 图论与数学的其他分支形成的交叉研究方向有（ ）.

参考答案:

随机图论;代数图论;模糊图论;拓扑图论

第一章测试

1. 四个顶点的非同构简单图有（ ）.

参考答案:

11个

2. 序列称为图序列，如果d是某一个简单图的度序列. 则下列不是图序列的是（ ）.

参考答案:

(7,6,5,4,3,2,2);(6,6,5,4,3,3,1)

3. 设图G有21条边，12个3度顶点，其余顶点的度均为2，则图G的顶点数为（ ）.

参考答案:

15

4. 下列哪些矩阵是本题中所给图的邻接矩阵？（ ） 参考答案:

;

5. 本题中所给的两个图G与H不同构.（ ）

参考答案:

错

第二章测试

1. 边数比顶点数少1的简单图一定是树.（ ）

参考答案:

错

2. 六个顶点的非同构的树有（ ）.

参考答案:

6个

3.

本题中所给图的非同构生成树的个数等于（ ）.

参考答案:

3个

4. 设G是五个顶点的标号完全图（即给G的每个顶点标号），则G的不同的生成树（注意“不同”是指标号不同，不是不同构）的个数等于（ ）.

参考答案:

125

5. 若G是单圈图（即G是仅含一个圈的连通图）, 则G的边数一定等于它的顶点数.（ ）

参考答案:

对

第三章测试

1. 若图G的每条边是割边, 则G是森林.（ ）

图论综述

一、简介

图论是数学的一个分支。它以图为研究对象。图论中的图是由若干给定的点及连接两点的线所构成的图形，这种图形通常用来描述某些事物之间的某种特定关系，用点代表事物，用连接两点的线表示相应两个事物间具有这种关系。

图G=（V,E）是一个二元组（V,E）使得E⊆[V]的平方，所以E的元素是V的2-元子集。集合V中的元素称为图G的定点（或节点、点），而集合E的元素称为边（或线）。通常，描绘一个图的方法是把定点画成一个小圆圈，如果相应的顶点之间有一条边，就用一条线连接这两个小圆圈，如何绘制这些小圆圈和连线时无关紧要的，重要的是要正确体现哪些顶点对之间有边，哪些顶点对之间没有边。

图论本身是应用数学的一部份，因此，历史上图论曾经被好多位数学家各自独立地建立过。关于图论的文字记载最早出现在欧拉1736年的论著中，他所考虑的原始问题有很强的实际背景。目前，图论已形成很多分支：如随机图论、网络图论、代数图论、拓扑图论、极值图论等。图论的应用已经涵盖了人类学、计算机科学、化学、环境保护、非线性物理、心理学、社会学、交通管理、电信以及数学本身等。

二、基本内容

2.1 图的基本概念

本章首先介绍了图的一些基本性质和一些不同模型的图，包括偶图，完全图和补图，引入了定点度的来描述图的性质。其次介绍了子图的相关概念，介绍了图的一些基本运算规则，对图的路和连通性进行了阐释。紧接着讲解了最短路算法，定义设G为边赋权图。u与v是G中两点，在连接u与v的所有路中，路中各边权值之和最小的路，称为u与v间的最短路。图的代数表示，包括图的邻接矩阵和图的关联矩阵。最后对极图理论进行了简介，主要介绍了极值图论中的一个经典结论——托兰定理。

2.2 树

本章主要介绍了树的概念与性质，阐述了生成树与最小生成树的基本概念与一些常用结论与定理。

树是不含圈的无圈图，也是连通的无圈图。树是图论中应用最为广泛的一类图。在理论上，由于树的简单结构，常常是图论理论研究的“试验田”。在实际问题中，许多实际问题的图论模型就是树。

图论学习笔记

⽬录图的概念简史欧拉与⼽尼斯堡七桥问题

等价问题：“欧拉⼀笔画”\(\equiv\)与任⼀个顶点相关联的边必须是偶数条。图的基本概念图⽆向图邻接与关联

邻接与关联：

\((p,q)\)图

另⼀种表⽰⽅法：(p,q)图图相等与特殊的图

图相等、特殊的图（平凡图、零图）有向图

疑惑：⽆向图是集合反⾃反、对称的关系。有向图中为保证反⾃反性，去掉了⾃⾝到⾃⾝的有向线段\(\{(v,v)|v \in V\}\)。但是，图是不允许存在⾃⾝到⾃⾝的边吗？

答案：是的。图的表⽰图解法与邻接矩阵法

图解法与邻接矩阵法：

问题：关系的闭包在图中的意义是什么？图模型

利⽤图建模现实问题，并⽤图的理论加以解决的能⼒。

例⼦：结婚问题、地图与导航⼦图⼦图概念⽣成⼦图

特例：⽣成⼦图

记号：去除顶点u，去除边{u,v}

尤其地，注意去除边的记号不是去除u、v两个顶点。导出⼦图

（1）顶点导出⼦图：若V1⊆V(G)，则以V1为顶点集，以两个顶点均在V1中的边集组成的图，称为图G的顶点导出⼦图，记为G(V1)。

例如：求G(V1)，V1 ={1,3,5}

则G(V1)为

（2）边的导出⼦图：若E1⊆E(G),则以E1为边集，以E1中所有边的顶点为顶点集组成的图，称为图G的边的导出⼦图，记为G(E1)。

例如：求G(E1)，E1 = {13,24,35}则G(E1)为度度的概念

定理1——握⼿定理

【定理1】握⼿定理

证明：每⼀条边对度数总和的贡献为2（每⼀条边对应两个顶点），由于共有q个边，故度数总和为2q。

推论1：握过奇数次数⼿的⼈为偶数个。

证明：将⼈分为两类，握奇数次⼿\(V_1\)和握偶数次⼿\(V_2\)，

那么，\(V_1\)与\(V_2\)中顶点的度数总和为偶数（2q），

同时，\(V_2\)的度数之和必然为偶数，

那么，\(V_1\)的度数之和必然为偶数（偶数-偶数=偶数），

同时，由于\(V_1\)中均是握奇数次⼿（\(V_1\)中各顶点度均为奇数），

第1章 图论预备知识

1.1 解：(1) p={,{a},{b},{c},{a,b},{a,c},{b,c},{a,b,c}}

(2) p={,{a},{{b,c}},{a,{b,c}}}

(3) p={,{}}

(4) p={,{},{{}},{,{}}}

(5)p={,{{a,b}},{{a,a,b}},{{a,b,a,b}},{{a,b},{a,a,b}},{{a,b},{a,b,a,b}},{{a,b},{a,a,b},{a,b,a,b}}}

1.2 解：(1) 真 (2) 假 (3)假 (4)假

1.3 解：(1) 不成立，A={1} B={1,2} C={2}

(2) 不成立，A={1} B={1,2} C={1,3}

1.4 证明：设(x,y)∈(A∩B)X(C∩D) 说明x∈A∩B,y∈C∩D

由于 x∈A,y∈C 所以 (x,y) ∈A X C

由于x∈B,y∈D 所以 (x,y) ∈B X D

所以 (x,y) ∈（A X C）∩（B X D）

反过来，如果（x,y）∈(A X C) ∩（B X D）

由于 (x,y) ∈（A X C）所以 x∈A,y∈C

由于 (x,y) ∈（B X D）所以x∈B,y∈D

所以x∈(A∩B) y∈(C∩D)

所以 (x,y) ∈(A∩B)X(C∩D)

所以(A∩B)X(C∩D)= (A X C) ∩（B X D）

1.5 解：Hasse图

24

12

4 10

5 2 3 9

极大元{9,24,10,7}

极小元{3,2,5,7}

最大元{24}

最小元{2}

1.6 解 (1)R={|x整除y}