简单题目 (1-20)
简单
1. 图论的创始人是谁？
正确答案：B
欧拉在1735年通过解决柯尼斯堡七桥问题创立了图论，成为图论的创始人。
简单
2. 图 G = (V, E) 中，V 表示什么？
正确答案：A
在图的定义 G = (V, E) 中，V 代表顶点集合（Vertex set），E 代表边集合（Edge set）。
简单
3. 握手定理说明什么？
正确答案：B
握手定理表明：∑deg(v) = 2|E|，即所有顶点度数之和等于边数的两倍，因为每条边对两个顶点各贡献1度。
简单
4. 完全图 K₄ 有多少条边？
正确答案：C
完全图 Kₙ 的边数公式为 n(n-1)/2。对于 K₄：4×3/2 = 6 条边。
简单
5. 树的定义是什么？
正确答案：A
树是连通且无圈的图。这个定义等价于：连通且|E|=|V|-1，或无圈且|E|=|V|-1。
简单
6. 度数为1的顶点叫什么？
正确答案：B
度数为1的顶点称为叶子节点（leaf），特别是在树中，叶子节点只连接一个顶点。
简单
7. 什么是连通图？
正确答案：A
连通图是指任意两个顶点之间都有路径相连的无向图。
简单
8. 有n个顶点的树有多少条边？
正确答案：B
树的基本性质之一：有n个顶点的树恰好有n-1条边。
简单
9. 什么是图的子图？
正确答案：A
子图G'=(V',E')满足V'⊆V且E'⊆E，即顶点集和边集都是原图的子集。
简单
10. 什么是简单图？
正确答案：A
简单图是指没有自环（顶点到自身的边）和重边（两顶点间多条边）的图。
简单
11. 完全图K₃等价于什么？
正确答案：B
完全图K₃有3个顶点，每两个顶点之间都有边，形成一个三角形结构。
简单
12. 什么是图的路径？
正确答案：A
路径是顶点和边的交替序列v₀e₁v₁e₂...eₖvₖ，其中相邻顶点通过边连接。
简单
13. 什么是圈（回路）？
正确答案：A
圈（回路）是起点和终点相同的路径，通常要求除起点外不重复其他顶点。
简单
14. 二分图的定义是什么？
正确答案：A
二分图的顶点集可以分割为两个独立集，使得所有边都连接不同独立集中的顶点。
简单
15. 星图S₄有多少个顶点？
正确答案：B
星图Sₙ有n+1个顶点，其中一个中心顶点连接其他n个顶点。所以S₄有5个顶点。
简单
16. 什么是图的直径？
正确答案：A
图的直径是任意两个顶点之间最短距离的最大值，即图中最远两点的距离。
简单
17. 图的连通分量是什么？
正确答案：A
连通分量是图的最大连通子图，即不能再添加顶点而保持连通性的连通子图。
简单
18. 轮图W₄有多少条边？
正确答案：C
轮图Wₙ由圈Cₙ加上一个中心顶点构成，边数为2n。所以W₄有2×4=8条边。
简单
19. 什么是独立集？
正确答案：A
独立集是图中两两不相邻的顶点集合，即独立集中任意两个顶点之间都没有边。
简单
20. 什么是顶点覆盖？
正确答案：A
顶点覆盖是图中的一个顶点集合，使得图中每条边都至少有一个端点在该集合中。
中等题目 (21-40)
中等
21. 根据欧拉定理，连通图存在欧拉回路的充要条件是什么？
正确答案：A
欧拉定理：连通图存在欧拉回路当且仅当每个顶点的度数都是偶数。如果恰好有两个奇度顶点，则存在欧拉路径（不是回路）。
中等
22. 完全二分图 K₃,₄ 有多少条边？
正确答案：C
完全二分图 K_{m,n} 的边数为 m×n。因此 K₃,₄ 有 3×4 = 12 条边。
中等
23. 图G是平面图的必要条件是什么（欧拉公式）？
正确答案：B
对于连通平面图，由欧拉公式推导出：|E| ≤ 3|V| - 6（当|V| ≥ 3时）。
中等
24. 什么是哈密顿路径？
正确答案：A
哈密顿路径是经过图中每个顶点恰好一次的路径。哈密顿回路则是起点和终点相同的哈密顿路径。
中等
25. 根据狄拉克定理，图G有哈密顿回路的充分条件是？
正确答案：A
狄拉克定理：如果简单图G有n个顶点（n≥3），且每个顶点的度数都至少为n/2，则G有哈密顿回路。
中等
26. 什么是图的着色数？
正确答案：A
图的着色数（色数）是对图进行正当着色（相邻顶点颜色不同）所需的最少颜色数，记作χ(G)。
中等
27. 完全图Kₙ的着色数是多少？
正确答案：D
完全图Kₙ中每两个顶点都相邻，所以每个顶点都需要不同的颜色，着色数为n。
中等
28. 二分图的着色数最多是多少？
正确答案：B
二分图的两个独立集可以分别用两种不同的颜色着色，所以二分图的着色数最多为2。
中等
29. 什么是图的匹配？
正确答案：A
匹配是图中两两不相邻（不共享顶点）的边的集合。完美匹配覆盖图中所有顶点。
中等
30. 根据霍尔定理，二分图G=(X∪Y,E)有完美匹配的充要条件是？
正确答案：A
霍尔定理：二分图有完美匹配当且仅当|X|=|Y|且对X的任意子集S，其邻居集N(S)的大小至少为|S|。
中等
31. 什么是图的团（clique）？
正确答案：A
团是图中两两相邻的顶点集合，即由这些顶点诱导的子图是完全图。
中等
32. 对于树T，以下哪个性质是错误的？
正确答案：D
树中必然存在叶子节点（度数为1），所以"每个顶点的度数都大于1"是错误的。
中等
33. 生成树的定义是什么？
正确答案：A
生成树是连通图的一个子图，它包含图的所有顶点且是一棵树（连通且无圈）。
中等
34. 根据Kruskal算法，应该如何构造最小生成树？
正确答案：A
Kruskal算法：将边按权重从小到大排序，依次选择不形成圈的边，直到构成生成树。
中等
35. 根据Prim算法，应该如何构造最小生成树？
正确答案：A
Prim算法：从任一顶点开始，逐步添加连接当前树和未访问顶点的最小权重边。
中等
36. 什么是图的割点？
正确答案：A
割点（关节点）是指删除该顶点及其关联边后，图的连通分量数增加的顶点。
中等
37. 什么是图的割边？
正确答案：A
割边（桥）是指删除该边后图的连通分量数增加的边。
中等
38. 深度优先搜索(DFS)的时间复杂度是多少？
正确答案：B
DFS需要访问所有顶点O(V)和检查所有边O(E)，总时间复杂度为O(V+E)。
中等
39. 广度优先搜索(BFS)可以用来解决什么问题？
正确答案：A
BFS可以找到无权图中从源点到其他所有顶点的最短路径（最少边数）。
中等
40. 拓扑排序适用于什么类型的图？
正确答案：A
拓扑排序只适用于有向无圈图(DAG)，用于将顶点线性排序，使得对于每条有向边(u,v)，u都在v之前。
困难题目 (41-60)
困难
41. 根据库拉托夫斯基定理，以下哪个图不是平面图？
正确答案：B
库拉托夫斯基定理：图是平面图当且仅当它不包含与 K₅ 或 K₃,₃ 同胚的子图。K₅ 本身就是非平面图。
困难
42. 根据四色定理，平面图的着色数最多是多少？
正确答案：C
四色定理：任何平面图都可以用至多4种颜色进行正当着色。
困难
43. 什么是图的边连通度？
正确答案：A
边连通度κ'(G)是使图不连通需要删除的最少边数，也等于最小边割的大小。
困难
44. 什么是图的顶点连通度？
正确答案：A
顶点连通度κ(G)是使图不连通需要删除的最少顶点数（对于完全图定义为n-1）。
困难
45. 根据孟格尔定理，两个不相邻顶点间的最大不相交路径数等于什么？
正确答案：A
孟格尔定理：两个不相邻顶点间的最大不相交路径数等于分离它们的最小顶点割的大小。
困难
46. 完全二分图K₃,₃是平面图吗？
正确答案：B
K₃,₃不是平面图。根据库拉托夫斯基定理，包含K₅或K₃,₃子图的图都不是平面图。
困难
47. 对于连通平面图，欧拉公式V - E + F = 2中，F表示什么？
正确答案：C
在欧拉公式V - E + F = 2中，F表示面数，包括外部无限面。
困难
48. 什么是图的支配集？
正确答案：A
支配集是图中的一个顶点集合D，使得图中每个顶点要么在D中，要么与D中某个顶点相邻。
困难
49. 根据韦伯定理，图G是二分图当且仅当什么？
正确答案：A
韦伯定理：图G是二分图当且仅当G中不包含奇圈（奇数长度的圈）。
困难
50. 最大流最小割定理说明什么？
正确答案：A
最大流最小割定理：在网络中，从源点到汇点的最大流量等于分离源点和汇点的最小割的容量。
困难
51. 什么是图的核？
正确答案：A
图的核是既是独立集又是支配集的顶点集合，即集合中顶点两两不相邻，且每个不在集合中的顶点都与集合中某个顶点相邻。
困难
52. 图的树宽的概念与什么相关？
正确答案：A
树宽是衡量图与树相似程度的参数，定义为图的最优树分解中最大包大小减1。
困难
53. 彼得森图的着色数是多少？
正确答案：B
彼得森图是3-正则图，包含奇圈，所以不是二分图，但可以用3种颜色着色。
困难
54. 什么是图的线图？
正确答案：A
线图L(G)以原图G的边为顶点，当且仅当两条边在G中有公共端点时，它们在L(G)中相邻。
困难
55. 根据拉姆塞理论，R(3,3)等于多少？
正确答案：B
拉姆塞数R(3,3)=6，意味着任何6个顶点的完全图的边用红蓝两色着色，必存在单色三角形。
困难
56. 什么是图的禁用子图特征？
正确答案：A
禁用子图特征通过禁止包含某些特定子图来刻画图类，如森林（禁用圈）、二分图（禁用奇圈）等。
困难
57. 什么是图的谱？
正确答案：A
图的谱是其邻接矩阵的特征值集合，图谱理论研究图的组合性质与其谱性质的关系。
困难
58. 强正则图的定义涉及哪些参数？
正确答案：A
强正则图由参数(n,k,λ,μ)刻画：n个顶点，每个顶点度数为k，相邻顶点有λ个公共邻居，不相邻顶点有μ个公共邻居。
困难
59. 图的团数ω(G)与独立数α(G)有什么关系？
正确答案：A
图G的团数等于其补图Ḡ的独立数，因为G中的团对应Ḡ中的独立集。
困难
60. 什么是图的围长？
正确答案：A
图的围长是图中最短圈的长度。如果图是森林（无圈），则围长定义为无穷大。
超难进阶题目 (61-70)
超难
61. 根据凯莱公式，完全图 K₆ 有多少棵不同的生成树？
正确答案：B
凯莱公式：完全图 Kₙ 的生成树数量为 n^(n-2)。对于 K₆：6^(6-2) = 6⁴ = 1296。
超难
62. 根据布鲁克斯定理，连通图G的着色数χ(G)与最大度数Δ(G)有什么关系？
正确答案：A
布鲁克斯定理：对于连通图G，χ(G) ≤ Δ(G)，等号成立当且仅当G是完全图或奇圈。
超难
63. 什么是图的边着色数（色指数）？
正确答案：A
边着色数χ'(G)是对图的边进行正当着色（相邻边不同色）所需的最少颜色数。
超难
64. 根据维兹定理，简单图G的边着色数χ'(G)满足什么条件？
正确答案：A
维兹定理：对于简单图G，边着色数χ'(G)要么等于最大度数Δ(G)，要么等于Δ(G)+1。
超难
65. 什么是图的点边连通度？
正确答案：A
点边连通度是指同时删除顶点和边以使图不连通所需的最少元素（顶点或边）总数。
超难
66. 完全图Kₙ的边着色数是多少？
正确答案：B
完全图Kₙ的边着色数：当n为偶数时为n-1，当n为奇数时为n，这等于其最大度数。
超难
67. 什么是图的完美图？
正确答案：A
完美图是指图及其每个导出子图的着色数都等于其团数的图。
超难
68. 根据强完美图定理，图G是完美图当且仅当什么？
正确答案：A
强完美图定理（洛瓦兹定理）：图G是完美图当且仅当G和其补图都不包含长度至少为5的奇圈。
超难
69. 什么是图的分数着色数？
正确答案：A
分数着色数χ_f(G) = sup{ω(H)/α(H) : H是G的导出子图}，它总是小于等于普通着色数。
超难
70. 在图论的哈达马德猜想背景下，什么是强正则图的参数可行性条件？
正确答案：A
对于强正则图(n,k,λ,μ)，参数可行性的一个必要条件是判别式Δ = (λ-μ)² + 4μ必须是完全平方数，这来自于特征值的整数性要求。