图论

简单辨析一些问题：

一、图的基本组成

1.图，组成，无向有向问题

2.平行边（注意有向图里情况），结点邻接，环（注意度数），孤立点，边关联于结点，边集元素重复，n 阶图？零图？平凡图？空图（及符号表示）？结点的度数，入度，出度（重复的边算吗，符号表示）？最大/小度及其符号？悬挂结点/边？图的度数序列？

3.简单图？多重图？n 阶无向完全图及符号表示？有向完全图？默认的完全图？n 阶有向/无向完全图的边数？什么是 k - 正则图？n 阶无向完全图是 (n-1) - 正则图吗 ？什么是环图？什么是轮图？轮图最低阶数？什么是 n 方体图？二分图？完全二分图及其记法？带权图的权在边上还是结点，还是都行？

4.删除边/边集/结点/结点集运算？边的收缩及其符号？加新边及其符号？子图 / 母图？生成子图？由结点集 / 边集导出子图及其符号？G(E-E₁) 与 G-E₁ 的区别？G 的补图与符号表示？（注意其结点）图的同构，自互补图？

5.通路，简单通路，基本通路（又叫初级通路，路径）；回路，简单回路，基本回路（又叫初级回路、圈），奇 / 偶回路，短程线与d(u, v)，连通图、非连通图（无向图）？连通关系（无向图）？连通关系是等价关系吗？W(G) 指什么？简单图里 n-w<=e？点割集与割点？边割集与割边（桥）？可达、相互可达（有向图）？有向图中：单向连通？强连通 / 弱连通？单向连通一定是弱连通？有向连通图？强分图？强连通图判定定理（有点像废话）？

6.邻接表（局限，有向图、无向图上的表现），有向图的邻接矩阵及某行 / 列和的意义？有向图邻接矩阵 k 次幂的元素意义？无向图的邻接矩阵及其幂？如何通过邻接矩阵判断图的连通性？邻接矩阵与同构的关系？什么是有向图的可达矩阵？怎么利用可达矩阵求强连通分支？什么是有向图的关联矩阵？什么是无向图的关联矩阵（行列代表什么？什么情况下元素为 2 ？每行元素和代表？）
邻接，可达，关联矩阵各有什么字母？

二、特殊图

1.欧拉回路，欧拉通路，欧拉图，半欧拉图？欧拉图的判定？半欧拉图呢？欧拉有向图、半欧拉有向图中的“有向”？欧拉有向图/半欧拉有向图的充要条件？（半）哈密顿回路 / 图（像欧拉图一样分有向无向吗）？判定哈密顿图的两个充分条件、一个必要条件？半哈密顿图的充分条件？彼得森图？格雷码？格雷码怎么找？

2.旅行商问题？最短路径问题及 Dijkstra 算法？中国邮路问题？

3.匹配？极大匹配？最大匹配？（VS 最大元，极大元）M 饱和点 / 非饱和点？完美匹配？M 交错路？M 可扩充路？最大匹配判定定理？

4.二分图？怎么判断一个图是不是二分图？互补结点集？完全二分图及其符号表示？完全二分图充要条件？【弄错了？】二分图的完备匹配 / 完美匹配？从 V₁ 到 V₂ 的完备匹配呢？怎么判断二分图是否存在完备匹配？ t 条件是二分图完备匹配存在的充分条件还是必要条件？

5.平面图？平面嵌入？G 的面？f₀ 的中文名与意义？f₁ ，f₂ …呢？面的边界？deg(f)？∑deg(f_i) 与 e 的关系？连通平面图的欧拉公式与记忆技巧？非连通的平面图呢？什么叫两个图同胚？判定一个图是平面图的充要条件？

6.G* 是什么，怎么作？G* 是连通的吗？与原图的结点数，面数，边数关系？同构平面图的对偶图也一定同构吗？G* 的对偶图的对偶图和 G* 一定同构吗？什么是对简单图（结点）着色？什么是 k - 可着色的？什么是色数和 k 色图？无环图色数最大是？Brooks 定理（ G 不是完全图或长度为奇数的基本回路时色数最大值）？二分图的色数？色数为 2 能否说明是二分图？k - 可边着色？简单图的边色数？二分图的边色数？

三、树

1.无向树？无向树的树叶、分支点、内点？平凡树？森林？T 是连通图且 e=n-1 能判定是无向树吗？T 无回路且 e=n-1 能判定是无向树吗？T 无回路且任意两结点间增加一条边，得到一条且仅一条回路，能判定 T 是无向树吗？证明 T 中结点数不小于 2 时 T 至少有两片树叶。生成树，弦，余树。图 G 有生成树的等价条件。给出求无向连通图的生成树的算法？给出求无向连通图的最小生成树的算法？

2.有向树？其边的方向是怎样的？有向根树？有向根树的树叶、分支点、树根、内点的定义？某结点的级数（层数）的定义，树的高度的定义？结点间的关系：祖先，后代，父子，兄弟？什么是根子树？什么是 m 元树，m 元正则树，完全 m 元正则树，完全 m 元树（学校的定义）？m 元正则树中结点数，分支点数，m 的关系？利用此关系与定义，能否互推出结点数、分支点数、树叶数的关系式？高为 h 的 m 元树里至多有多少树叶？

3.什么是有序根树？二元有序根树的左儿子，右儿子，左子树，右子树？介绍二元有序根树的前序遍历算法，中序遍历算法，后序遍历算法？什么是波兰、逆波兰记法？前缀码与二元树？前缀码是唯一的吗？如何生成最优二元树，最佳前缀码？

四、证明定理：

握手定理+性质。（单独的度数可以用求和的方法转到度数和再借助不等式求解）结点总数超过 3 时平面简单图中每个面次数至少为 3。

某些定量性质：

图论基本定理（握手定理）？度数为奇数的结点一定有偶数个吗？有向图中所有结点入度之和与出度之和等于什么？怎么判断自然数序列是不是图的度数序列？

简单图里 n-w<=e？

连通平面图的欧拉公式

m 元正则树中结点数，分支点数， m 的关系？利用此关系与定义，能否互推出结点数、分支点数、树叶数的关系式？高为 h 的 m 元树里至多有多少树叶？

旅行商问题？最短路径问题及 Dijkstra 算法？中国邮路问题？

G* 是什么，怎么作？

介绍二元有序根树的前序遍历算法，中序遍历算法，后序遍历算法？

如何生成最优二元树，最佳前缀码？

五、部分错题

1.把平面分成 x 个区域，每两个区域相邻，问 x 最大为？

我的答案：5 正确答案：4

2.给设 d=(d₁, d₂, …, d_n)，其中 d_i 为正数，i = 1, 2, …, n。若存在 n 个结点的简单图，使得结点 v_i 的度数为 d_i，则称 d 是可图解的。下面给出的各序列中，（ ）不是可图解的。

A. (1, 1, 1, 2, 3) B. (2, 3, 3, 4, 5, 6) C. (0, 1, 1, 2, 3, 3) D. (1, 3, 3, 4, 5, 6, 6) E. (1, 2, 2, 3, 4, 5)

我的答案：B E 正确答案：B D E

3.设 G 是一棵根树，则 G 一定是（ ）

A. 强连通图 B. 单向连通图 C. 弱连通图 D. 有向连通图

我的答案：B C D 正确答案：C D

4.若有向图中无回路，则其每条边都是割边。

我的答案：对 正确答案：错

5.K_m,n，当 m 不等于 n 时不是哈密顿图。

我的答案：错 正确答案：对