图论期末考试整理复习资料

图论与组合数学期末复习试题含答案组合数学部分第1章排列与组合例1：1)、求⼩于10000的含1的正整数的个数；2、)求⼩于10000的含0的正整数的个数；解：1)、⼩于10000的不含1的正整数可看做4位数,但0000除外.故有9×9×9×9－1＝6560个.含1的有：9999－6560=3439个2)、“含0”和“含1”不可直接套⽤。

0019含1但不含0。

在组合的习题中有许多类似的隐含的规定，要特别留神。

不含0的1位数有19个，2位数有29个，3位数有39个，4位数有49个不含0⼩于10000的正整数有()()73801919999954321=--=+++个含0⼩于10000的正整数9999－7380=2619个。

例2：从[1,300]中取3个不同的数，使这3个数的和能被3整除，有多少种⽅案？解：将[1,300]分成3类：A={i|i ≡1(mod 3)}={1,4,7,…,298},B={i|i ≡2(mod 3)}={2,5,8,…,299},C={i|i ≡0(mod 3)}={3,6,9,…,300}.要满⾜条件，有四种解法：1)、3个数同属于A;2)、3个数同属于B ；3)、3个数同属于C;4)、A,B,C 各取⼀数；故共有3C(100,3)+1003=485100+1000000=1485100。

例3：（Cayley 定理：过n 个有标志顶点的数的数⽬等于2-n n ）1）、写出右图所对应的序列；2）、写出序列22314所对应的序列；解：1）、按照叶⼦节点从⼩到⼤的顺序依次去掉节点（包含与此叶⼦节点相连接的线），⽽与这个去掉的叶⼦节点相邻的另外⼀个内点值则记⼊序列。

如上图所⽰，先去掉最⼩的叶⼦节点②，与其相邻的内点为⑤，然后去掉叶⼦节点③，与其相邻的内点为①，直到只剩下两个节点相邻为⽌，则最终序列为51155.。

2）、⾸先依据给定序列写出（序列长度+2）个递增序列，即1234567，再将给出序列按从⼩到⼤顺序依次排列并插⼊递增序列得到：112223344567。

图论复习题（二）图论复习题一、选择题1．设图G ＝<V , E >，v ∈V ，则下列结论成立的是 ( C ) ． A ．deg(v )=2∣E ∣ B ． deg(v )=∣E ∣ C ．E v Vv 2)deg(=∑∈ [PPT 23] D ．Ev Vv =∑∈)deg(定理1 图G=（V ，E ）中，所有点的次之和为边数的两倍 2．设无向图G 的邻接矩阵为⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎣⎡0101010010000011100100110则G 的边数为( B )．A ．6B ．5C ．4D ．33、 设完全图K n 有n 个结点(n ≥2)，m 条边，当（ C ）时，K n 中存在欧拉回路．A ．m 为奇数B ．n 为偶数C ．n 为奇数D ．m 为偶数解释：K n 每个结点的度都为n －1，所以若存在欧拉回路则n －1必为偶数。

n 必为奇数。

4．欧拉回路是（ B ）A. 路径B. 简单回路[PPT 40]C. 既是基本回路也是简单回路D.既非基本回路也非简单回路5．哈密尔顿回路是（ C ）A. 路径B. 简单回路C. 既是基本回路也是简单回路D.既非基本回路也非简单回路[PPT 40]：哈密尔顿回路要求走遍所有的点，即是基本回路的点不重复，也可以是简单回路的边不重复。

6．设G 是简单有向图，可达矩阵P(G)刻划下列关系中的是（ C ） A 、点与边 B 、边与点 C 、点与点 D 、边与边7．下列哪一种图不一定是树（C ）。

A.无简单回路的连通图B. 有n 个顶点n-1条边的连通图C. 每对顶点间都有通路的图D. 连通但删去一条边便不连通的图8．在有n 个结点的连通图中，其边数（B ）A.最多有n-1条B.至少有n-1条C.最多有n 条D.至少有n 条9．下列图为树的是（C ）。

A 、>><><><=<},,,,,{},,,,{1d c b a a a d c b a GB 、>><><><=<},,,,,{},,,,{2d c d b b a d c b a GC 、>><><><=<},,,,,{},,,,{3a c d a b a d c b a GD 、>><><><=<},,,,,{},,,,{4d d c a b a d c b a G 10、下面的图7-22是（C ）。

组合数学部分第1章 排列与组合例1：1)、求小于10000的含1的正整数的个数；2、)求小于10000的含0的正整数的个数；解：1)、小于10000的不含1的正整数可看做4位数,但0000除外.故有9×9×9×9－1＝6560个.含1的有：9999－6560=3439个2)、“含0”和“含1”不可直接套用。

0019含1但不含0。

在组合的习题中有许多类似的隐含的规定，要特别留神。

不含0的1位数有19个，2位数有29个，3位数有39个，4位数有49个 不含0小于10000的正整数有()()73801919999954321=--=+++个含0小于10000的正整数9999－7380=2619个。

例2：从[1,300]中取3个不同的数，使这3个数的和能被3整除，有多少种方案？解：将[1,300]分成3类：A={i|i ≡1(mod 3)}={1,4,7,…,298},B={i|i ≡2(mod 3)}={2,5,8,…,299},C={i|i ≡0(mod 3)}={3,6,9,…,300}.要满足条件，有四种解法：1)、3个数同属于A;2)、3个数同属于B ；3)、3个数同属于C;4)、A,B,C 各取一数；故共有3C(100,3)+1003=485100+1000000=1485100。

例3：（Cayley 定理：过n 个有标志顶点的数的数目等于2-n n ）1）、写出右图所对应的序列；2）、写出序列22314所对应的序列；解：1）、按照叶子节点从小到大的顺序依次去掉节点（包含与此叶子节点相连接的线），而与这个去掉的叶子节点相邻的另外一个内点值则记入序列。

如上图所示，先去掉最小的叶子节点②，与其相邻的内点为⑤，然后去掉叶子节点③，与其相邻的内点为①，直到只剩下两个节点相邻为止，则最终序列为51155.。

2）、首先依据给定序列写出（序列长度+2）个递增序列，即1234567，再将给出序列按从小到大顺序依次排列并插入递增序列得到：112223344567。

离散数学图论部分期末复习辅导一、单项选择题 1．设图G ＝<V , E >，v V ，则下列结论成立的是 ( ) ．A ．deg(v )=2EB ．deg(v )=EC ．deg()2||v Vv E ∈=∑ D ．deg()||v Vv E ∈=∑解 根据握手定理（图中所有结点的度数之和等于边数的两倍）知，答案C 成立。

答 C2．设无向图G 的邻接矩阵为⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎣⎡0101010010000011100100110， 则G 的边数为( )．A ．6B ．5C ．4D ．3解 由邻接矩阵的定义知，无向图的邻接矩阵是对称的．即当结点v i 与v j 相邻时，结点v j 与v i 也相邻，所以连接结点v i 与v j 的一条边在邻接矩阵的第i 行第j 列处和第j 行第i 列处各有一个1，题中给出的邻接矩阵中共有10个1，故有102=5条边。

答 B3．已知无向图G 的邻接矩阵为⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎣⎡0111110101110001000111010，则G 有（ ）．A ．5点，8边B ．6点，7边C ．6点，8边D ．5点，7边解 由邻接矩阵的定义知，矩阵是5阶方阵，所以图G 有5个结点，矩阵元素有14个1，14÷2=7，图G 有7条边。

答 D4．如图一所示，以下说法正确的是 ( ) ． A ．{(a, e )}是割边 B ．{(a, e )}是边割集C ．{(a, e ) ,(b, c )}是边割集D ．{(d, e)}是边割集定义3.2.9 设无向图G =<V ,E >为连通图，若有边集E 1ÌE ，使图G 删除了E 1的所有边后，所得的子图是不连通图，而删除了E 1的任何真子集后，所得的子图仍是连通图，则称E 1是G 的一个边割集．若边割集为单元集{e }，则称边e 为割边（或桥）．解 割边首先是一条边，因为答案A 中的是边集，不可能是割边，因此答案A 是错误的．删除答案B 或C 中的边后，得到的图是还是连通图，因此答案B 、C 也是错误的．在图一中，删去(d , e )边，图就不连通了，所以答案D 正确． 答 D注：如果该题只给出图的结点和边，没有图示，大家也应该会做．如：若图G =<V , E >，其中V ={ a , b , c , d , e }，E ={ (a , b ), (a , c ) , (a , e ) , (b , c ) , (b , e ) , (c , e ) , (e , d )}，则该图中的割边是什么？5．图G 如图二所示，以下说法正确的是 ( )． A ．a 是割点 B ．{b, c}是点割集 C ．{b , d }是点割集 D ．{c }是点割集定义3.2.7 设无向图G =<V ,E >为连通图，若有点集V 1ÌV ，使图G 删除了V 1的所有结点后，所得的子图是不连通图，而删除了V 1的任何真子集后，所得的子图仍是连通图，则称V 1是G 的一个点割集．若点割集为单元集{v }，则称结点v 为割点．οοο ο a bc d图一 οe ο οο a b c d图二ο解 在图二中，删去结点a 或删去结点c 或删去结点b 和d 图还是连通的，所以答案A 、C 、D 是错误的．在图二中删除结点b 和c ，得到的子图是不连通图，而只删除结点b 或结点c ，得到的子图仍然是连通的，由定义可以知道，{b, c }是点割集．所以答案B 是正确的． 答 B6．图G 如图三所示，以下说法正确的是 ( ) ． A ．{(a, d )}是割边 B ．{(a, d )}是边割集C ．{(a, d) ,(b, d)}是边割集D ．{(b , d )}是边割集解 割边首先是一条边，{(a, d )}是边集，不可能是割边．在图三中，删除答案B 或D 中的边后，得到的图是还是连通图．因此答案A 、B 、D 是错误的．在图三中，删去(a,d )边和(b, d )边，图就不连通了，而只是删除(a, d )边或(b, d )边，图还是连通的，所以答案C 正确．7．设有向图（a ）、（b ）、（c ）与（d ）如图四所示，则下列结论成立的是( )．图四A ．（a ）是强连通的B ．（b ）是强连通的C ．（c ）是强连通的D ．（d ）是强连通的复习：定义3.2.5 在简单有向图中，若在任何结点偶对中，至少从一个结点到另一个结点可达的，则称图G 是单向（侧）连通的；若在任何结点偶对中，两结点对互相可达，则称图G 是强连通的；若图G 的底图，即在图G 中略去边的方向，得到的无向图是连通的，则称图G 是弱连ο ο ο a bcd图三ο通的．显然，强连通的一定是单向连通和弱连通的，单向连通的一定是弱连通，但其逆均不真．定理3.2.1一个有向图是强连通的，当且仅当G中有一个回路，其至少包含每个结点一次．单侧连通图判别法：若有向图G中存在一条经过每个结点至少一次的路，则G是单侧连通的。

图论及网络总复习题一、选择题1、设G是由5个顶点构成的完全图，则从G中删去（）边可以得到树。

A．6 B．5 C．8 D．42、下面哪几种图不一定是树（）。

A．无回路的连通图B．有n个结点，n-1条边的连通图C．对每对结点间都有通路的图D．连通但删去任意一条边则不连通的图。

3、5阶无向完全图的边数为（）。

A．5 B．10 C．15 D．204、把平面分成x个区域，每两个区域都相邻，问x最大为（）A．6 B．4 C．5 D．35、设图G有n个结点，m条边，且G中每个结点的度数不是k，就是k+1，则G中度数为k的节点数是（）A．n/2 B．n(n+1) C．nk-2m D．n(k+1)-2m 6、图G1和G2的结点和边分别存在一一对应关系是G1和G2同构的（）。

A．充分条件B．必要条件C．充分必要条件D．既不充分也不必要条件7、设G=<V，E>为有向图，V={a,b,c,d,e,f}，E={<a,b>,<b,c>,<a,d>,<d,e>,<f,e>}是（）。

A．强连通图B．单向连通图C．弱连通图D．不连通图8、无向图G中的边e是G的割边（桥）的充分必要条件是（）。

A．e是重边B．e不是重边C．e不包含在G的任一简单回路中D．e不包含在G的某一简单回路中9、在有n个结点的连通图中，其边数（）A．最多有n-1条B．至少有n-1条C．最多有n条D．至少有n条10．设无向简单图的顶点个数为n，则该图最多有（）条边。

A．n-1 B．n(n-1)/2 C． n(n+1)/2 D．n211．n个结点的完全有向图含有边的数目（）。

A．n*n Ｂ．n（n＋１） C．n／2 D．n*（n－l）12．在一个无向图中，所有顶点的度数之和等于所有边数（）倍。

A．1/2 B．2 C．1 D．413．连通图G是一棵树，当且仅当G中（）A．有些边不是割边B．所有边都是割边C．无割边集D．每条边都不是割边14．4个顶点的完全图G，其生成树个数是（）。

图论试题及答案解析图片一、选择题1. 图论中，图的基本元素是什么？A. 点和线B. 点和面C. 线和面D. 点和边答案：A2. 在无向图中，如果两个顶点之间存在一条边，则称这两个顶点是：A. 相邻的B. 相连的C. 相等的D. 相异的答案：A3. 在有向图中，如果从顶点A到顶点B有一条有向边，则称顶点A是顶点B的：A. 父顶点B. 子顶点C. 邻接顶点D. 非邻接顶点答案：B4. 一个图的度是指：A. 图中顶点的总数B. 图中边的总数C. 一个顶点的边数D. 图的连通性答案：C5. 一个图是连通的，当且仅当：A. 图中任意两个顶点都是相邻的B. 图中任意两个顶点都可以通过边相连C. 图中任意两个顶点都可以通过路径相连D. 图中任意两个顶点都可以通过子顶点相连答案：C二、填空题1. 在图论中，一个顶点的度数是该顶点的________。

答案：边数2. 如果一个图的任意两个顶点都可以通过边相连，则称该图为________。

答案：完全图3. 一个图中，如果存在一个顶点到其他所有顶点都有边相连，则称该顶点为________。

答案：中心顶点4. 图论中，最短路径问题是指在图中找到两个顶点之间的________。

答案：最短路径5. 如果一个图的任意两个顶点都可以通过有向路径相连，则称该图为________。

答案：强连通图三、简答题1. 请简述图论中的欧拉路径和哈密顿路径的定义。

答案：欧拉路径是指在图中经过每条边恰好一次的路径，而哈密顿路径是指在图中经过每个顶点恰好一次的路径。

2. 什么是图的着色问题？答案：图的着色问题是指将图中的顶点用不同的颜色进行标记，使得相邻的两个顶点颜色不同。

四、计算题1. 给定一个无向图G，顶点集为{A, B, C, D, E}，边集为{AB, BC, CD, DE, EA}，请画出该图，并计算其最小生成树的权重。

答案：首先画出图G的示意图，然后使用克鲁斯卡尔算法或普里姆算法计算最小生成树的权重。

图论复习题第一章图主要内容：1．图的基本概念和基本定理（重点是完全图、二部图、图的同构、握手定理等）2．轨道和圈（最长轨理论）练习题目：1．5阶无向完全图的边数为__10_____。

2．图G1和G2的结点和边分别存在一一对应关系是G1和G2同构的_充分必要条件______。

3．图G1和G2的结点和边分别存在一一对应关系是G1和G2同构的_充分必要条件______。

4．设无向简单图的顶点个数为n，则该图最多有_n(n-1)/2_ 条边。

5．一个有n个结点的图，最少有___1____个连通分支。

6．有三个顶点的所有互不同构的简单无向图有___4____个。

7．单连通无向图G有12条边，G中有2个1度结点，2个2度结点，3个4度结点，其余结点度数为3．求G中有多少个结点．试作一个满足该条件的简单无向图．解：设G中有x各结点，则3度的结点有x-7根据握手定理有，1x2+2x2+4x3+3x(x-7)=2x12解得x=9,故G中有9个结点。

满足条件的图如下：8．单连通无向图G有9条边，G中有4个3度结点，2个1度结点，其余结点度数为2．求G中有多少个结点．试作一个满足该条件的简单无向图．9．面上有n个点S＝{x1,x2,……,x n}，其中任两个点之间的距离至少是1，证明在这n个点中距离为1的点对数不超过3n。

（38题）10．若图G是简单图，且(1)(2)2p pq-->，则G连通。

（42题）11．如果G是具有m条边的n阶简单图，证明：若G的直径为2且△= n-2，则m≥2n-4。

（50题）12．证明：在任何图中，奇度点个数为偶数。

（推论1.1）13．证明：图G是二部图当且仅当G无奇圈。

（定理1.2）14．证明：每个顶点度数都大于等于2的简单图必有圈。

（例1.9）15．证明：每个顶点度数都大于等于3的简单图必有偶圈。

（例1.11）16．画出4个顶点的不同构的图（包括连通和不连通图）。

第二章 树主要内容：1．树的定义和简单性质； 2．树的几个等价条件；3．生成树的个数（Cayley 公式）练习题目：1．设树T 中有2个3度顶点和3个4度顶点，其余的顶点都是树叶，则T 中有____片树叶。

图论概念定理知识点梳理图论基本知识点梳理第一部分（基本概念）1.G 连通的充分必要条件是1)(=G ω。

或若k G V 2|)(|=，且对)(G V v ∈?，有k v d ≥)(，则G 是连通图。

4.图G 为二分图当且仅当G 中无奇圈。

5.在仅两个奇次顶点的图中，此二奇次顶点连通。

6.设G 为简单图，若2)(≥G δ，则G 中有圈。

7. 设G 为简单图，若3)(≥G δ，则G 中有偶圈。

具体地，(1)单星妖怪中有偶圈。

(2)在-k 正则图G 中，若3≥k ，则G 中有偶圈。

8.简单图G 与其补图c G 不能都不连通。

9.在2的三角剖分中，正常三角形为奇数个。

10.以下等价(1) G 是树（无圈连通图）。

(2) G 中任两顶点间恰有一条轨。

(3) G 无圈，1-=νε。

(4) G 是连通图，1-=νε 。

(5) G 是连通图，且对G 的任意边e ，e G -不连通。

（树每边皆割边）(6) G 无圈，且对任一不在)(G E 的边e ，e G +恰含一个圈。

11. 若G 连通，则1)()(-≥G G νε。

G 的生成树是G 最小的连通生成子图。

12. G 是连通图的充分必要条件是G 有生成树。

13. 2≥ν的树T 至少有两个叶。

14.完全图n K 的生成树个数2)(-=n n n K τ。

15. 图G 可平面嵌入的充分必要条件是G 可以球面嵌入。

（染地球上各国等价于染地图上各国）16. （Euler 公式） G 是连通平面图, 则2=+-φεν.17. 证明：若G 是3≥ν的连通平面图，则63-≤νε。

18. 证明：平面图G 的最小顶点次数5≤δ。

19 3≥ν平面图G 是极大平面图的充要条件是G 的平面嵌入的每个面皆三角形。

3≥ν平面图G 是极大平面图的充要条件是63-=νε。

20 G 是平面图当且仅当G 中不含与5K 和3,3K 同胚的子图。

21M 是图G 的最大匹配当且仅当G 中无M 的可增广轨。

集合论与图论JK211009——在线考试复习资料2021版一、单选题1.设G是简单有向图,可达矩阵P(G)刻画下列关系中的是()A.点与边B.边与点C.点与点D.边与边答案：C2.A.6B.5C.4D.3答案：B3.图中满足以下哪个条件?()A.有欧拉回路和哈密尔顿回路B.有欧拉回路,但无哈密尔顿回路C.无欧拉回路,但有哈密尔顿回路D.既无欧拉回路,又无哈密尔顿回路答案：D4.A.B.C.D.答案：B5.下面不能成为图的度数序列是()A.(1,2,3,4)B.(1,2,3,6)C.(1,3,5,7)D.(1,3,4,9)答案：D6.设简单无向图G有15条边,有3个4度结点,有4个3度结点,其余结点的度数均为2,那么G的结点总数为()A.9B.10C.11D.12答案：B7.如图所示,以下说法正确的是()A.e是割点B.{a,e}是点割集C.{b,e}是点割集D.{d}是点割集答案：A8.图G和G1的结点以及边分别存在一一对应关系,此对应关系是两图同构的()A.充分条件B.必要条件C.充要条件D.既不充分也非必要条件答案：B9.设顶点集为V={a,b,c,d,e},下列几个无向图是简单图的有()A.G1=(V,E1),E1={(a,b),(b,c),(c,b),(a,e)}B.G2=(V,E2),E2={(a,b),(b,c),(c,a),(a,d),(d,e)}C.G3=(V,E3),E3={(a,b),(b,c),(c,d),(e,e)}D.G4=(V,E4),E4={(a,a),(a,b),(c,c),(c,e)}答案：B10.若R是集合A上的等价关系,则下面哪个不一定满足()A.B.R2=RC.t(R)=RD.R-1=R答案：A11.A.B.C.D.答案：A12.A.B.C.D.答案：A13.下列哪个关系矩阵具有反自反性?()A.B.C.D.答案：A14.设集合A={1,2,3,4},A上的等价关系R={<1,3>,<3,1>,<2,4>,<4,2>}∪I A,则对应于R的A划分是()A.B.C.D.答案：B15.设集合A={1,2,3,4}上的二元关系,R={<1,1>,<2,2>,<2,3>,<4,4>},S={<1,1>,<2,2>,<2,3>,<3,2>,<4,4>},则S是R的()A.自反闭包B.传递闭包C.对称闭包D..不是任何闭包答案：C16.哈密尔顿回路是()A.只是简单回路B.是基本回路,但不是简单回路C.既是基本回路也是简单回路D.既非基本回路也非简单回路答案：C17.设A={1,2,3,4,5,6,7,8},R是A上的整除关系,B={2,4,6},则集合的最大元、最小元、上界、下界依次为()A.8、2、8、2B.无、2、无、2C.6、2、6、2D.8、1、6、1答案：B18.下列各组数中不能构成无向图的度数序列的是()A.(1,1,2,3,5)B.(1,3,1,3,2)C.(1,2,3,4,5)D.(1,2,3,4,6)答案：C19.A.自反的B.对称的C.传递且对称的D.反自反且传递的答案：B20.图中满足以下哪个条件?()A.有欧拉回路和哈密尔顿回路B.有欧拉回路,但无哈密尔顿回路C.无欧拉回路,但有哈密尔顿回路D.既无欧拉回路,又无哈密尔顿回路答案：B21.设A={a,{a}},下列命题错误的是()A.B.C.D.答案：A22.设G1、G2、G3、G4都是(4,3)的简单无向图,则它们之间至少有几个是同构的?()A.2个B.3个C.4个D.可能都不同构答案：B23.若集合A的元素个数为4,则其幂集的元素个数为()A.1个B.4个C.8个D.16个答案：D24.设结点集V={a,b,c,d},则下列与V构成强连通图的边集的是()A.E1={<a,d>,<b,a>,<b,d>,<c,b>,<d,c>}B.E2={<a,d>,<b,a>,<b,c>,<b,d>,<d,c>}C.E3={<a,c>,<b,a>,<b,c>,<d,a>,<d,c>}D.E4={<a,b>,<a,c>,<a,d>,<b,d>,<c,d>}答案：A25.在0()之间写上正确的符号。

图论知识点总结•对应简单图的度序列，在同构意义下可能不止一个•简单图的度序列最大度一定要小于等于n-1•只要和为偶数就是图的度序列•若图中两点u与v间存在途径，则u与v间存在路•若过点u存在闭迹，则过点u存在圈•一个图是偶图当且仅当它不包含奇圈•无向图的顶点之间的连通关系一定是等价关系•有向图的顶点之间的单向连通关系不是等价关系•一个简单图G的n个点的度不能互不相同•无向图的邻接矩阵的行和对应顶点的度数•无向图的邻接矩阵的所有元素之和等于边数的2倍•无向图的邻接矩阵的平方的对角线元素等于对应顶点的度数•无向图的邻接矩阵的平方的对角线元素之和等于边数的2倍•无向图的邻接矩阵的特征值的平方和等于边数的2倍•若G是非连通的，则邻接矩阵相似于某个对角矩阵•树一定是连通无圈图•树G无环且任意两点之间存在唯一的路•树无回路但任意添加一条边后有回路•回路是边不重的圈的并•如果一个闭迹不是一个圈，那么它一定是没有重边的圈的并集。

•n阶树T的形心由一个点或两个相邻点组成。

•若T只有一个形心，则形心的权小于n/2•若T有两个形心，则形心的权等于n/2•树T的对偶图全是环•G是极大平面图的充要条件各面的次数均为3且为连通图每个n方体都有完美匹配由n方体的构造知：n方体有2n个顶点，每个顶点可以用长度为n的二进制码来表示，两个顶点连线当且仅当代表两个顶点的二进制码只有一位坐标不同。

划分顶点，把坐标之和为偶数的顶点归入X，否则归入Y。

X中顶点互不邻接，Y中顶点也如此。

所以n方体是偶图。

很容易验证n方体的每个顶点度数为n，所以n方体是n正则偶图。

因此，n方体存在完美匹配。

树T有完美匹配当且仅当对所有顶点v∈T，o(T-v)=1必要性：树T有完美匹配，由Tutte定理知o(T-v)≤|{v}|=1显然T是偶数阶的图，o(T-v)≥1.因此o(T‒v)=1。

充分性：对于T的任意顶点v，假设Tv是T-v仅有的奇分支，且Tv与v之间的边为uv。

图论期末考试题库及答案一、单项选择题1. 图论的创始人是（）。

A. 欧拉B. 莱布尼茨C. 牛顿D. 高斯答案：A2. 在图论中，一个图的顶点集合为空，但边集合不为空的图称为（）。

A. 空图B. 完全图C. 树D. 多重图答案：A3. 如果一个图的任意两个顶点之间都存在一条路径，则称该图为（）。

A. 连通图B. 强连通图C. 弱连通图D. 无环图答案：A4. 在图论中，一个图的边的集合可以划分为若干个不相交的路径，使得图中的每个顶点恰好属于其中一条路径，这样的图称为（）。

A. 欧拉图B. 哈密顿图C. 树答案：C5. 图论中，一个图的边的集合可以划分为若干个不相交的回路，使得图中的每个顶点恰好属于其中一条回路，这样的图称为（）。

A. 欧拉图B. 哈密顿图C. 树D. 环答案：A二、多项选择题1. 下列哪些是图论中的基本术语（）。

A. 顶点B. 边D. 权重答案：ABCD2. 在图论中，以下哪些图是无向图（）。

A. 完全图B. 树C. 多重图D. 有向图答案：ABC3. 图论中，以下哪些图是连通图（）。

A. 完全图B. 树C. 多重图D. 空图答案：ABC三、填空题1. 图论中，一个图的顶点集合为V，边集合为E，那么图可以表示为G=（）。

答案：(V, E)2. 如果一个图的任意两个顶点之间都存在一条路径，则称该图为（）。

答案：连通图3. 在图论中，一个图的边的集合可以划分为若干个不相交的路径，使得图中的每个顶点恰好属于其中一条路径，这样的图称为（）。

答案：树四、简答题1. 请解释什么是图论中的“完全图”？答案：完全图是指图中每一对不同的顶点之间都恰好有一条边相连的图。

在完全图Kn中，n个顶点两两相连，共有n(n-1)/2条边。

2. 请解释什么是图论中的“欧拉路径”和“欧拉回路”？答案：欧拉路径是指图中存在一条路径，该路径恰好经过每条边一次。

欧拉回路是指图中存在一条回路，该回路恰好经过每条边一次。

五、计算题1. 给定一个图G=(V, E)，其中V={A, B, C, D, E}，E={(A, B), (B, C), (C, D), (D, E), (E, A), (A, C)}，请判断该图是否为连通图，并说明理由。

图论知识点总结笔记一、图的基本概念1. 图的定义图是由节点（顶点）和连接节点的边构成的一种数据结构。

图可以用来表示各种关系和网络，在计算机科学、通信网络、社交网络等领域有着广泛的应用。

在图论中，通常将图记为G=(V, E)，其中V表示图中所有的节点的集合，E表示图中所有的边的集合。

2. 节点和边节点是图中的基本单位，通常用来表示实体或者对象。

边是节点之间的连接关系，用来表示节点之间的关联性。

根据边的方向，可以将图分为有向图和无向图，有向图的边是有方向的，而无向图的边是没有方向的。

3. 度度是图中节点的一个重要度量指标，表示与该节点相连的边的数量。

对于有向图来说，可以分为入度和出度，入度表示指向该节点的边的数量，出度表示由该节点指向其他节点的边的数量。

4. 路径路径是图中连接节点的顺序序列，根据路径的性质，可以将路径分为简单路径、环路等。

在图论中，一些问题的解决可以归结为寻找合适的路径，如最短路径问题、汉密尔顿路径问题等。

5. 连通性图的连通性是描述图中节点之间是否存在路径连接的一个重要特征。

若图中每一对节点都存在路径连接，则称图是连通的，否则称图是非连通的。

基于图的连通性，可以将图分为连通图和非连通图。

6. 子图子图是由图中一部分节点和边组成的图，通常用来描述图的某个特定属性。

子图可以是原图的结构副本，也可以是原图的子集。

二、图的表示1. 邻接矩阵邻接矩阵是一种常见的图表示方法，通过矩阵来表示节点之间的连接关系。

对于无向图来说，邻接矩阵是对称的，而对于有向图来说，邻接矩阵则不一定对称。

2. 邻接表邻接表是另一种常用的图表示方法，它通过数组和链表的组合来表示图的节点和边。

对于每一个节点，都维护一个邻接点的链表，通过链表来表示节点之间的连接关系。

3. 关联矩阵关联矩阵是另一种图的表示方法，通过矩阵来表示节点和边的关联关系。

关联矩阵可以用来表示有向图和无向图，是一种比较灵活的表示方法。

三、常见的图算法1. 深度优先搜索（DFS）深度优先搜索是一种常见的图遍历算法，通过递归或者栈的方式来遍历图中所有的节点。

图论复习chapter 1⼀、重要概念1. 图、简单图、图的同构、度序列与图序列、补图与⾃补图、两个图的联图、两个图的积图、偶图简单图：⽆环⽆重边的图称为简单图。

（除此之外全部都是复合图）图的同构：点对应、边对应，两个图完全⼀样！A \cong B图同构的⼏个必要条件：1. 顶点数相同；2. 边数相同；3. 度数相等的顶点个数相同。

偶图（⼆分图）：可⼆分类(X, Y)的图，每条边的顶点均不属于同⼀类！指该图的点集可以分解为两个(⾮空)⼦集 X和 Y ，使得每条边的⼀个端点在 X 中，另⼀个端点在Y 中。

判定：不存在奇圈！！完全偶图：不是完全图！是指具有⼆分类(X, Y)的简单偶图，其中 X的每个顶点与 Y 的每个顶点相连记K_{m,n}度序列：图中各个顶点的度构成的⾮负正数组：(d_1, ...d_n)可图（对整数组⽽⾔）：存在⼀个简单图以它为度序列可图序列：简称图序列（注意图序列判定和度序列判定的区别，前者仅针对简单图，后者不限！）图序列判定：1）度序列和为偶数2）利⽤公式计算3）简单图的度最⼤为n-1，看度序列是否符合！4）简单图⼀定存在度数相同的顶点！度序列判定：1. 度序列和为偶数！补图：完全图 - 当前图若n阶图G是⾃补的(即G \cong \bar{G}，则(n~mod~4=0,1)⼀个n阶图和它的补图有相同的频序列⽣成⼦图：顶点与原图相同，边为原图边的⼦集导出⼦图：顶点为原图⾮空⼦集V'，以及原图中所有以V'中顶点为两端的边，记G[V']边导出⼦图：边为原图的⾮空⼦集，以及边对应的顶点，记G[E']简单图 G 中所有不同的⽣成⼦图（包括 G 和空图）的个数是2^m个对称差：G1 △ G2 : G1 △ G2 = (G1 ⋃ G2 ) - (G1 ⋂ G2 ) = (G1 -G2 ) ⋃ (G2 -G1 )联图：设G1，G2是两个不相交的图，作G1+G2，并且将G1中每个顶点和G2中的每个顶点连接，这样得到的新图称为G1与G2的联图。

图论复习题1、设G是由5个顶点构成的完全图，则从G中删去（）边可以得到树。

A．6 B．5 C．8 D．4 2、下面哪几种图不一定是树（）。

A．无回路的连通图B．有n个结点，n-1条边的连通图C．对每对结点间都有通路的图D．连通但删去任意一条边则不连通的图。

3、5阶无向完全图的边数为（）。

A．5 B．10 C．15 D．20 4、设图G有n个结点，m条边，且G中每个结点的度数不是k，就是k+1，则G中度数为k的节点数是（）A．n/2 B．n(n+1) C．nk-2m D．n(k+1)-2m 5、设G=<V，E>为有向图，则有（）。

A．E⊆V x V B．E⊄V x V C．V x V⊂E D．V x V=E 6、图G1和G2的结点和边分别存在一一对应关系是G1和G2同构的（）。

A．充分条件B．必要条件C．充分必要条件D．既不充分也不必要条件7、设G=<V，E>为有向图，V={a,b,c,d,e,f}，E={<a,b>,<b,c>,<a,d>,<d,e>,<f,e>}是（）。

A．强连通图B．单向连通图C．弱连通图D．不连通图8、无向图G中的边e是G的割边（桥）的充分必要条件是（）。

A．e是重边B．e不是重边C．e不包含在G的任一简单回路中D．e不包含在G的某一简单回路中9、在有n个结点的连通图中，其边数（）A．最多有n-1条B．至少有n-1条B．C．最多有n条D．至少有n条10．设无向简单图的顶点个数为n，则该图最多有（）条边。

A．n-1 B．n(n-1)/2 C． n(n+1)/2 D．n211．n个结点的完全有向图含有边的数目（）。

A．n*n Ｂ．n（n＋１） C．n／2 D．n*（n－l）12．一个有n个结点的图，最少有（）个连通分量。

A．0 B．1 C．n-1 D．n13．一个有n个结点的图，最多有（）个连通分量。