简单
1. 顶点 v 的度数 deg(v) 是什么？
正确答案：C
顶点的度数定义为与该顶点关联的边的数量。对于多重图，环要计算两次。
简单
2. 在多重图中，环对顶点度数的贡献是？
正确答案：B
环连接的是同一个顶点，但在概念上占用了该顶点的两个"连接槽位"，因此贡献度数2。
简单
3. 度数为0的顶点叫什么？
正确答案：D
度数为0的顶点称为孤立顶点，就像社交圈中没有朋友的人。
简单
4. 度数为1的顶点叫什么？
正确答案：B
度数为1的顶点称为悬挂顶点，就像风铃中只被一根绳子吊着的那一个。
简单
5. 握手定理的内容是什么？
正确答案：B
握手定理：∑deg(v) = 2|E|，因为每条边对两个端点各贡献1度。
简单
6. 根据握手定理，奇度顶点的数量必须是？
正确答案：B
因为奇数个奇数相加不能得到偶数，而握手定理要求总度数为偶数。
简单
7. 什么是正则图？
正确答案：B
正则图是指所有顶点的度数都相同的图。例如，环图是2-正则图。
简单
8. 完全图 Kn 是几正则图？
正确答案：B
在完全图Kn中，每个顶点都与除自己外的所有n-1个顶点相连。
简单
9. 度数序列 (3,3,2,2,1) 能否构成一个图？
正确答案：D
度数之和为3+3+2+2+1=11（奇数），违反了握手定理，因此无法构成任何图。
简单
10. 两个图同构意味着什么？
正确答案：A
图同构意味着两个图在结构上是等价的，存在保持邻接关系的双射映射。
简单
11. 图不变量是什么？
正确答案：A
图不变量是同构图必须共有的性质，如顶点数、边数、度数序列等。
简单
12. 路径(Walk)的长度指什么？
正确答案：B
路径的长度等于它所包含的边的数量。
简单
13. 什么是闭合路径？
正确答案：A
闭合路径是指起点和终点是同一个顶点的路径。
简单
14. 连通图的定义是什么？
正确答案：A
连通图是指任意两个顶点之间都存在路径的图。
简单
15. 邻接矩阵的(i,j)位置表示什么？
正确答案：A
邻接矩阵的(i,j)位置表示顶点i和j之间连接的边数。
简单
16. 小径(Trail)与路径(Walk)的区别是什么？
正确答案：A
小径是不重复边的路径，但可以重复顶点。
简单
17. 圈(Cycle)的定义是什么？
正确答案：A
圈是闭合且不重复顶点的路径（除了起点和终点相同）。
简单
18. 二分图与奇数环的关系是什么？
正确答案：A
二分图当且仅当不包含奇数长度的环。
简单
19. 欧拉小径是什么？
正确答案：A
欧拉小径是经过图中每条边恰好一次的小径。
简单
20. 欧拉环路存在的条件是什么？
正确答案：A
欧拉环路存在当且仅当图连通且所有顶点度数为偶数。
简单
21. 哈密顿路径是什么？
正确答案：A
哈密顿路径是经过图中每个顶点恰好一次的路径。
简单
22. 欧拉问题和哈密顿问题的复杂度差异是什么？
正确答案：A
欧拉问题有多项式时间算法，而哈密顿问题是NP完全问题。
简单
23. 立方图Qn是几正则图？
正确答案：A
立方图Qn中每个顶点的度数都是n。
简单
24. 环图Cn是几正则图？
正确答案：A
环图Cn中每个顶点的度数都是2。
简单
25. 无向图的邻接矩阵有什么特点？
正确答案：A
无向图的邻接矩阵是对称的，因为ai,j = aj,i。
简单
26. 邻接矩阵Am的含义是什么？
正确答案：A
邻接矩阵Am的(i,j)位置表示从顶点i到j长度为m的路径数量。
简单
27. 欧拉小径存在的条件是什么？
正确答案：A
欧拉小径存在当且仅当图连通且恰好有两个奇度顶点。
简单
28. 度数为1的顶点对哈密顿圈的影响是什么？
正确答案：A
度数为1的顶点（悬挂顶点）阻止哈密顿圈的存在，因为圈必须经过每个顶点的恰好2条边。
简单
29. 连通分量的定义是什么？
正确答案：A
连通分量是图的最大连通子图。
简单
30. 度数序列(4,3,3,3,3)能否构成图？
正确答案：A
度数之和=16（偶数），奇度顶点=4个（偶数），根据事实4可以构成多重图。
中等
31. 如果图G有8个顶点，每个顶点度数为3，那么G有多少条边？
正确答案：B
根据握手定理：∑deg(v) = 2|E|，所以8×3 = 2|E|，因此|E| = 12。
中等
32. 立方图Q₃有多少个顶点和边？
正确答案：A
Q₃有2³=8个顶点，边数=3×2³⁻¹=3×4=12条边。
中等
33. 在邻接矩阵中，主对角线上的1表示什么？
正确答案：A
主对角线上的1表示顶点i有环（自己连接自己）。
中等
34. 如果两个图有相同的度数序列，它们一定同构吗？
正确答案：B
度数序列相同是同构的必要条件但不充分，还需要检查其他图不变量。
中等
35. 完全二分图K₃,₄的度数序列是什么？
正确答案：A
K₃,₄中，3个顶点的度数是4，4个顶点的度数是3。
中等
36. 从路径到路径的定理说明了什么？
正确答案：A
该定理说明如果两点间存在路径，则必存在不重复顶点的简单路径。
中等
37. n个顶点的图中，简单路径的最大长度是多少？
正确答案：B
简单路径不重复顶点，最多经过n个顶点，因此最大长度为n-1条边。
中等
38. 哪个图既有欧拉环路又有哈密顿圈？
正确答案：A
K₄中所有顶点度数为3（奇数），不存在欧拉环路。实际上应该是偶数度数的图如K₅。
中等
39. Dirac定理的条件是什么？
正确答案：A
Dirac定理：如果n≥3且每个顶点度数≥n/2，则图有哈密顿圈。
中等
40. 连通性关系是等价关系，需要满足哪些性质？
正确答案：A
等价关系必须满足自反性、对称性和传递性三个性质。
中等
41. 风扇图有哪种类型的路径？
正确答案：A
风扇图有两个奇度顶点（存在欧拉小径）且可以遍历所有顶点（存在哈密顿路径）。
中等
42. 星图为什么没有哈密顿路径？
正确答案：A
星图有多个度数为1的顶点，而哈密顿路径最多只能有2个端点。
中等
43. 完全图K₅的度数序列是什么？
正确答案：A
K₅中每个顶点连接其他4个顶点，所以度数都是4。
中等
44. 环路(Tour)和圈(Cycle)的区别是什么？
正确答案：A
环路是闭合且不重复边的路径，但可以重复顶点；圈不重复顶点（除起终点）。
中等
45. Ore定理的条件是什么？
正确答案：A
Ore定理：如果任意不相邻顶点的度数之和≥n，则图有哈密顿圈。
困难
46. 证明两个图G₁和G₂同构：G₁有顶点{a,b,c,d}和边{ab,bc,cd,da,ac}，G₂有顶点{w,x,y,z}和边{wy,yz,zx,xw,wz}。构造同构映射f。
正确答案：A
验证：度数序列都是(3,3,2,2)。映射f(a)=w, f(b)=y, f(c)=z, f(d)=x保持所有邻接关系。
困难
47. 在4×4的邻接矩阵A中，A²的(1,3)位置值为5。这意味着什么？
正确答案：A
矩阵A^m的(i,j)位置表示从顶点i到j长度为m的路径数量。
困难
48. 给定度数序列(5,4,4,3,3,3,2,2)，分析其构成图的可能性。
正确答案：A
度数之和=26（偶数），奇度顶点=4个（3,3,3,5，偶数个），满足构成多重图的必要条件。
困难
49. 在轮图W₅中，执行一步Dijkstra算法，从中心顶点开始，初始时到各顶点的距离如何更新？
正确答案：A
轮图的中心顶点连接所有外圈顶点，因此第一步后所有外圈顶点距离都更新为1。
困难
50. 分析图G：有6个顶点，度数序列为(3,3,3,3,2,2)。判断G是否一定包含三角形（长度为3的圈）。
正确答案：B
可以构造不含三角形的图，如修改后的二分图结构，证明度数序列不能唯一确定图的结构。
困难
51. 在包含环的图中，如何修改握手定理来正确计算度数？
正确答案：A
环连接同一顶点但算作2度，所以握手定理仍然成立：∑deg(v) = 2|E|。
困难
52. 证明：如果图G有哈密顿圈，且删除任意一个顶点v，剩余图的连通分量数不超过deg(v)。
正确答案：A
哈密顿圈经过每个顶点一次，删除顶点v最多将圈分成deg(v)段，因此连通分量数≤deg(v)。
困难
53. 在8×8的邻接矩阵中，如何快速确定图是否是二分图？
正确答案：A
二分图的邻接矩阵可以重排成分块形式：左上和右下为零矩阵，体现了二分图的结构特征。
困难
54. 柯尼斯堡七桥问题的现代变形：如果允许增加一座桥，最少需要几座桥使得存在欧拉路径？
正确答案：A
原问题有4个奇度顶点，添加1座桥连接其中两个，使得只剩2个奇度顶点，满足欧拉小径条件。
困难
55. 在完全二分图K₃,₄中，从一个度数为3的顶点开始，长度为4的路径有多少条？
正确答案：A
需要计算邻接矩阵的4次方。K₃,₄的二分结构使得路径在两个集合间交替，长度4的路径数为48。
困难
56. 分析Peterson图：它是3-正则图，有10个顶点。判断它是否有哈密顿圈。
正确答案：B
Peterson图是著名的反例：3-正则图但无哈密顿圈，说明正则性不保证哈密顿性。
困难
57. 在度数序列为(4,4,3,3,2,2)的图中，应用Ore定理分析哈密顿圈的存在性。
正确答案：A
Ore定理要求不相邻顶点度数之和≥n=6。最小度数和为2+2=4<6，条件不满足，但这不意味着不存在哈密顿圈。
困难
58. 证明：树T有n个顶点，则T的补图（完全图K_n去掉T的边）的边数为？
正确答案：A
K_n有n(n-1)/2条边，树T有n-1条边，补图边数=n(n-1)/2-(n-1)=(n-1)(n-2)/2。
困难
59. 在连通图G中，如果删除一条边后图变为非连通，这条边叫什么？证明树的每条边都具有此性质。
正确答案：A
桥是删除后使图不连通的边。树中任意两点间只有唯一路径，删除任何边都会破坏连通性。
困难
60. 在图论中，证明：如果图G的每个顶点度数≥k，则G包含长度≥k的路径。
正确答案：A
构造性证明：从任意顶点开始构造最长路径，由于每个顶点度数≥k，路径长度至少为k。
超难
61. 证明Turán定理的特例：n个顶点的三角形免费图（不含K₃）最多有⌊n²/4⌋条边。
正确答案：A
Turán定理确定了不含r-团的图的最大边数。对于r=3（三角形），最优结构是完全二分图。
超难
62. 在随机图G(n,p)模型中，当p=ln(n)/n时，图几乎必然具有什么性质？
正确答案：A
这是随机图理论中的经典结果：ln(n)/n是连通性的阈值概率。
超难
63. 分析图的谱性质：如果图G的邻接矩阵的第二大特征值λ₂满足λ₂≤d-1（d是正则度），证明G是强扩展图。
正确答案：A
这是代数图论的核心结果：谱间隙（λ₁-λ₂）与图的扩展性质密切相关。
超难
64. 在图G中，定义独立数α(G)为最大独立集的大小。证明：α(G)·ω(G)≥n，其中ω(G)是团数。
正确答案：B
原不等式错误。实际的关系更复杂，涉及色数χ(G)≥ω(G)和χ(G)·α(G)≥n等。
超难
65. 考虑图的Ramsey数R(s,t)：证明R(3,3)=6的关键思想是什么？
正确答案：A
经典证明：在K₆的任意红蓝着色中，选择一个顶点，其5个邻居中至少有3个同色，这3个顶点要么形成单色三角形，要么与选择的顶点形成单色三角形。
超难
66. 分析网络流问题：在最大流最小割定理中，如果所有边容量都是整数，证明存在整数最大流。
正确答案：A
整数容量网络的重要性质：如果所有容量都是整数，则存在整数最大流，这在实际应用中很重要。
超难
67. 在极值图论中，证明：不含4-圈（C₄）的n个顶点图最多有(1+o(1))n^(3/2)/2条边。
正确答案：A
这是极值图论的经典结果，使用线性代数方法（特别是关联矩阵的秩）可以证明。
超难
68. 分析图的张量积：如果G和H都是强正则图，它们的张量积G⊗H具有什么性质？
正确答案：A
强正则图的张量积仍是强正则图，这是代数图论中关于图运算的重要结果。
超难
69. 在量子图论中，考虑图G的量子色数χ_q(G)。证明χ_q(G)≤χ(G)（经典色数）。
正确答案：A
量子图着色是经典图着色的推广，量子策略提供了更大的灵活性，因此量子色数不超过经典色数。
超难
70. 综合分析：给定图G，如果G既有欧拉环路又有哈密顿圈，且所有顶点度数≥3，证明|E|≥3|V|/2。
正确答案：A
由握手定理：2|E|=∑deg(v)≥3|V|（因为度数≥3），所以|E|≥3|V|/2。欧拉和哈密顿条件确保了额外的结构性质。