初赛知识点整理

Orange_qwq · 2022-07-02 16:52:01 · 个人记录

可能有点乱……

数学问题

排列组合

排列

公式推导及结果： $$\begin{aligned} A_m^n &= m \times (m - 1) \times m \times (m - 2) \times \dots \times m \times (m - n+1)\\ \color{red}A_m^n & \color{red}= {\dfrac{m!}{(n-m)!}} \end{aligned}$$ ### 组合 $C_m^n$：从 $1-m$ 个不同元素种取出 $n$ 个元素的不同方案个数（**不考虑顺序**）。公式推导及结果： $$\begin{aligned}A_m^n &= C_m^n \times n!\\C_m^n&=\dfrac{A_m^n}{n!}\\ \color{red}C_m^n&\color{red}= {\dfrac{m!}{(n-m)!\times n!}} \end{aligned}$$ ### 附加 + $\large C_x^0 = 1 ,\space C_x^x = 1, \space C_x^1 = x

\large C_n^m = C_{n - 1}^{m-1} + C_{n-1}^m
（不选第 n 个加上选第 n 个的）
\large C_n^m = C_n^{n-m}

技巧 & 归类

插板法

有 n 个物品，分为 m 组，每组最少 k 个，求有多少种分法。

相当于有 n 个 1，n-1 个空，要用 m-1 个隔板进行分组，每组不少于 k 个。
\begin{matrix}\underbrace{1+1+\cdots+1}\\n \texttt 个 \end{matrix} = n
可以将问题简化成：每组 \ge 1，共有 n - (k - 1) \times m 个 1，有多少种分法。

可得 x_1 + x_2 + \cdots + x_m = n - (k-1) \times m。

这时每组 \ge 1，有 n - (k-1) \times m-1 个空，用 m-1 个隔板，所以是 \large C_{n - (k-1) \times m-1}^{m-1}。
分组问题
容易想到：如果有多于一个的组所分的数目相同（类似于第一个组分 $x$ 个，第二个组也分 $x$ 个），就会被重复计算。（如果不相同则不会被重复计算）设有 $m$ 组数目相同，则答案为 $\dfrac{ C_n^{k_1} \cdot C_{n-k_1} ^ {k_2}\cdot C_{n-k_1 - k_2} ^ {k_3} \cdots C^{k_k}_{k_k}}{A_m^m}$。

例题

从黄瓜、白菜、油菜、扁豆 4 种蔬菜品种中选出 3 种，分别种在不同土质的三块土地上，其中黄瓜必须种植，不同的种植方法共有 ({\color{blue}18}) 种。
书架上原来并排放着 5 本不同的书，现在要再插入 3 本不同的书，那么不同的插法共有 ({\color{blue}336}) 种。

解析：首先考虑插入第一本书，5 本书共有 6 个空。然后插入第二本，此时有 6 本书，7 个空。以此类推插入第三本时有 8 个空。

固答案为 6 \times 7 \times 8=336。
解析：每人只有2个选择，报名方法有 $2^5=32$ 种.
甲乙两人从 4 门课程种各选修 2 门，两人恰好选择同一门科目的情况有 ({\color{blue}24}) 种。

解析：首先，同一门科目的选择有 C_4^1 种；其次，甲的另一门科目能选择的有 3 种，所以乙的另一门科目有 2 种选择，固答案为 4 \times 3 \times 2 = 24。
由 4 个不同点构成的简单无向联通图的个数是 ({\color{blue}38})。

解析：考虑有 3 条边，共有 C_6^3 = 20 种情况。此时，不一定是一个连通图，需要减去。三条边构成环的 4 种情况，即有 20-4 = 16 种

考虑有 4 条边，共有 C_6^4 = C_6^2 = 15 种情况。

考虑有 5 条边，共有 C_6^5 = C_6^1 = 6 种情况。

考虑有 6 条边，共有 1 种情况。

求和，答案为 16+15+6+1=38。
把 1,2,3,4,5 组成没有重复数字且 1,2 不相邻的五位数，则所有不同的排法有 ({\color{blue}72}) 种。

解析：先考虑 3,4,5 相邻的情况，共有 A_3^3 = 6 种。于是有：\texttt{\_x\_x\_x\_ (x 表示已填数)}。

然后用插板法，将 1,2 插入空中，共有 A_4^2 = 12 种插法。

所以答案为 6 \times 12 = 72。
马路上有编号为 1,2,\cdots,9 九盏路灯，现在要关掉其中的三盏，但不能关掉相邻的两盏或三盏，也不能挂掉两端的两盏，满足条件的关灯方案有 ({\color{blue}30}) 种。

解析：插板法。先把要关的三盏灯拿出来，剩下 6 栈灯，有 5 个空，因为不能相邻，所以是要选 3 个空。答案为 C_5^3 = 30。

数据结构

二叉树

性质

1. 在二叉树的第 i 层上至多有 2^{i - 1} 个结点。（i \ge 1）
1. 深度为 k 的二叉树至多有 2^k-1 个结点。（k \ge 1）
1. 对任意一棵二叉树，如果度为 2 的结点数为 n_2，则其叶子结点数为 n_2+1。
  
  证明：设叶子结点数为 n_0，度为 1 的结点数为 n_2，则该树结点总数为：
  n = n_0 + n_1 + n_2 \space \;\;\;\;\;\;\;\;\; (1)
  树中结点之间的连线成为分支。树中除根结点外，其余每个结点都有一个分支进入，设 A 为二叉树分支的总数，则有：
  A = n - 1
  另一方面，这些分支都是由度为 1 或 2 的结点射出的，所以：
  A = n_1 + 2 \times n_2
  所以
  n - 1 = n_1 + 2 \times n_2 \;\;\;\;\;\; (2)
  联立 (1),(2)，可得
  n_0 = n_2 + 1
1. 具有 n 个结点的完全二叉树的深度为 \left\lfloor \log _2 n \right\rfloor + 1。
  
  证明：设深度为 k 的完全二叉树的结点数为 n。
  
  所以有
  2^{k-1} - 1 < n \le 2^k - 1
  转换为
  2^{k-1} \le n < 2^k
  于是有
  k-1 \le \log_2 n < k
  因为 k 是整数，所以 k=\left\lfloor \log _2 n \right\rfloor + 1。
1. 对于一颗具有 n 个结点的完全二叉树编号，对于每个编号为 i 的结点：
- 当 i=1，结点 i 为根；当 i>1，其双亲结点为 \dfrac{i}{2}。
- 若 2 i > n，则结点 i 无做孩子，结点 i 为叶子；否则，左孩子为 2i。
- 若 2i+1>n，则结点 i 无右孩子；否则，右孩子为 2i+1。

扩充二叉树

概念：扩充二叉树是指将原二叉树中每个凡缺少左、右孩子的结点，均扩充为带左、右两个孩子。

1. 若扩充二叉树有 n 个内部结点（扩充前具有的结点），则有 n+1 个外部结点。
  
  证明：根据二叉树性质 3（对任意一棵二叉树，如果度为 2 的结点数为 n_2，则其叶子结点数为 n_2+1），扩充二叉树的内部结点的度都是 2，有 n 个内部结点，则外部结点（即叶子）有 n+1 个。
1. 扩充二叉树的内外路径长度长度 I、E 的关系是 E = I + 2n。
  
  证明：（数学归纳法）
  
  当 n=1 时，由于只有一个内部结点 I=0 ，E=2，所以 E=I+2n。
  
  假设对于所有的 k，都有 E_k = I_k + 2k。
  
  当 k+1 时，即添加一个内部结点，设其路径长度为 L，
则
I_k+1 = I_k + L \\ & = E_k + L + 2 \\ & = ( I_k + 2 k ) + L + 2\\ & = I_k + L + 2 k + 2 \\ & = I_{k+1} + 2 (k+ 1) \end{aligned}

哈夫曼树

构造

哈夫曼（Huffman）最早给出一个带有一般规律的算法（哈夫曼算法）：

根据给定的 n 个权值 \{W_1 ,W_2 ,\cdots, W_n\} 构成 n 棵二叉树的集合 F=\{T_1 ,T_2 ,\cdots,T_n\}，其中每棵二叉树 T_i 中只有一个带权为 W_i 的根结点，其左右子树均空。
在 F 中选取两棵根结点的权值最小的树作为左右子树构造一棵新的二叉树，且置新树的根结点的权值为其左右子树根结点的权值之和。
在 F 中删除这两棵树，同时将新树加入 F 中。
重复 \texttt{2} 和 \texttt{3}，直到 F 中只含一棵树为止。

计算机相关

二进制

运算

例题

在 C++ 语言中,表达式 23 | 2 \oplus 5 的值是 ({\color{blue}23})。

解析：C++ 中，\oplus 的优先级大于 |。

算法

排序

排序算法	是否稳定
选择	非稳定
插入	稳定
冒泡	稳定
希尔	非稳定
归并	稳定
快排	非稳定
堆排	非稳定
计数	稳定
桶	稳定
基数	稳定

错题笔记

梦熊联盟·提高组CSP-S 2024初赛考前模拟卷

Linux 命令

命令

sudo 命令管理员权限执行命令。

vi 编辑命令

man 显示命令的手册页，获取命令的详细信息。

nano 编辑文件/打开新文件

echo 输出文本，文本重定向，转义字符，向文件追加文本，将文本写入新文件，输出提示信息，生成配置文件，写入日志文件，逻辑处理，好像什么都能用

文件和目录管理

ar 创建、修改备存文件或从备存文件中提取文件。

r：添加或替换文件到归档文件中。
c：创建归档文件。
t：列出归档文件的内容。
x：从归档文件中提取文件。
d：从归档文件中删除文件。
q：快速添加文件到归档文件中，不进行排序和重复检查。
s：创建归档文件的索引。
v：显示详细信息。

ls：列出目录内容，

ls -l 以长格式显示文件和目录的详细信息
ls -a 显示所有文件和目录，包括隐藏文件。
ls -lh 查看文件和目录的详情列表（增强文件大小易读性）
ls -lSr 查看文件和目录列表（以文件大小升序查看）
tree 查看文件和目录的树形结构（如果没有需要先安装 yum install tree）
ls -R 连同子目录的内容一起列出（递归列出），等于该目录下的所有文件都会显示出来

cd 改变当前工作目录，cd /path/to/directory 切换到指定目录，cd .. 切换到上一级目录，cd \~ 切换到用户主目录。

pwd 显示当前工作目录的路径。

mkdir 创建新目录，mkdir new_directory 创建新目录，mkdir -p /path/to/new_directory 递归创建多级目录。

rm 删除文件和目录。

rm file 删除文件。
rm -r directory 递归删除目录及其内容。
rm -i 互动模式，在删除前询问用户是否操作。
rm -f 忽略不存在文件，不会出现警告消息。
rmdir dir 删除 dir 目录
rmdir -rf dir 删除 dir 目录及其内容

cp：复制文件和目录

cp source_file destination_file 复制文件。
cp -r source_directory destination_directory 递归复制目录。
ln -s file1 link1 创建指向文件/目录的软链接
ln file1 link1 创建指向文件/目录的物理链接

mv：移动或重命名文件和目录，mv old_name new_name 重命名文件或目录，mv file /path/to/destination 移动文件或目录到指定位置。

touch：创建空文件或更新文件时间戳，touch new_file 创建新文件或更新现有文件的时间戳。

cat：显示文件内容，适合查看较小文件。

more：分页打开文件。

less：分页查看文件内容，适合查看较大文件，类似于 more，但允许方向操作。

head：显示文件的前几行。

tail：显示文件的最后几行。

scp：在本地计算机和远程计算机之间复制文件。

tar：打包和解压文件。

gzip 和 gunzip：压缩和解压文件。

find：在目录树中查找文件。

chmod：改变文件或目录的权限。

chown：改变文件或目录的所有者和所属组。

grep：在文件中搜索特定的字符串。

系统管理

reboot：重启计算机。

shutdown：关闭计算机。

top：查看系统进程信息。

ps：查看进程状态。

kill：终止进程。

ssh：远程登录其他计算机。

df：显示磁盘空间使用情况。

du：显示目录或文件的磁盘使用情况。

网络管理

ping：测试网络连通性。

netstat：查看网络连接状态。

ifconfig 或 ip addr show：显示和配置网络接口信息。

wget 或 curl：从网络上下载文件。

GDB 命令相关

AI 生成：

GDB（GNU调试器）是一个强大的工具，主要用于调试 C、C++、Fortran 和汇编语言程序。以下是 GDB 的一些核心命令：

启动与退出‌

gdb 启动GDB。 gdb <程序名> 启动GDB并加载指定的可执行文件。 quit 或 q 退出GDB。

断点操作‌

break <行号>或b <行号>：在指定行号设置断点。 break <文件名>:<行号>：在指定文件的指定行号设置断点。 info break 或 i b：查看断点信息。 delete [breakpoint number]：删除一个或多个断点。

‌程序执行‌

run 或 r：开始或重新开始程序的执行。 continue 或 c：继续执行程序直到下一个断点或其它停止条件。 next 或 n：执行下一条指令，不进入函数体。（单步执行） step 或 s：执行下一行代码，进入函数体。（单步执行） display：在每次程序暂停时自动显示指定的变量或表达式的值。 finish：执行到当前函数返回，然后停下来等待用户输入。 until：执行到指定的行号停下来，但不进入函数内部。 call：在当前位置调用一个函数，并可以传递参数。 return：强制函数返回，并可以指定返回值。 x：检查存储器和寄存器的内容。 thread：用于多线程调试，可以切换当前线程、查看线程信息等。 backtrace（或bt）：打印栈帧的调用序列，用于查看函数的调用关系。

其他

print（或 p）：打印表达式的值。 list（或 l）：列出源代码。可以指定行号或函数名来列出相关的源代码。 info：提供关于程序的各种信息，如断点、寄存器、栈帧等。 watch：设置一个监视点，当指定的变量或表达式的值发生变化时，程序会暂停执行。 set：用来设置或改变 GDB 中的变量或参数的值。 undo：撤销上一个 GDB 命令。

语法相关

构造函数不能有返回值，也不能被重载。
纯虚函数是在基类中声明的虚函数，它在基类中没有定义，但要求任何派生类都要定义自己的实现方法。在C++中，纯虚函数是通过在函数声明的末尾添加“= 0”来指定的。纯虚函数主要用于定义接口，让派生类去实现具体的功能。
1. ‌无实现‌：纯虚函数在基类中不提供实现，派生类必须提供纯虚函数的实现，除非派生类也是抽象类。
2. ‌抽象类‌：包含纯虚函数的类是抽象类，这意味着它不能被实例化。只有提供了所有纯虚函数实现的派生类才能被实例化。
3. ‌多态性‌：纯虚函数是实现多态性的一种方式。基类指针或引用可以指向派生类的对象，并通过纯虚函数调用派生类的实现。
静态成员函数是类中的一种特殊成员函数，它不属于类的任何对象，而是属于类本身。因此，静态成员函数没有this指针，它不能直接访问类的非静态成员变量或非静态成员函数。静态成员函数在类的所有对象之间共享，并且可以在没有类实例的情况下调用。静态成员函数是面向对象编程中的一种有用特性，它允许你定义与类紧密相关的函数，同时又不需要创建类的实例。这使得代码更加组织化，并且提高了代码的可读性和可维护性。
1. 不属于对象‌：静态成员函数不属于类的任何对象，而是属于类本身。
2. ‌无this指针‌：由于静态成员函数不属于任何对象，因此它没有this指针。
3. 访问限制‌：静态成员函数不能直接访问类的非静态成员变量或非静态成员函数，但可以通过对象来访问。
4. 共享性‌：静态成员函数在类的所有对象之间共享。
5. 无需实例化‌：可以在没有类实例的情况下调用静态成员函数。
new 是关键字。now 不是关键字。
析构函数是C++中的一个特殊成员函数，它的主要任务是在对象生命周期结束时执行清理工作。当对象的生命周期结束时，比如一个局部对象离开其作用域，或者一个动态分配的对象被delete时，析构函数会被自动调用。析构函数是C++中资源管理的重要机制之一，它确保了即使在异常情况下，对象所使用的资源也能被正确释放，从而避免了资源泄漏等问题。因此，在设计类时，应该始终考虑是否需要定义析构函数来执行必要的清理工作。
1. ‌自动调用‌：析构函数在对象生命周期结束时自动被调用，无需手动调用。
2. ‌无法继承‌：析构函数不能被继承，每个类都需要定义自己的析构函数。
3. ‌无法重载‌：一个类只能有一个析构函数，且析构函数的名称和参数都是固定的，因此无法重载。
4. ‌虚拟析构函数‌：当类中有虚函数时，通常建议将析构函数也声明为虚函数，以确保在删除指向派生类的基类指针时，能够正确地调用派生类的析构函数。
析构函数的名称由波浪号（~）后跟类名组成，它没有返回类型，也不接受任何参数。

运算

\oplus$ 的优先级大于 $|

优先级

一级：() [] -> .
二级：! ~ ++ -- - * & sizeof 类型转换运算符
三级：* / %
四级：+ -
五级：<< >>
六级：< <= > >=
七级：== !=
八级：&
九级：^
十级：|
十一级：&&
十二级：||
十三级：?
十四级：= += -= *= /= %= <<= >>= &= ^= |=
十五级：,

算法相关

ST 表 = 稀疏表

树

先序遍历 + 中序遍历 = 一棵确定的二叉树

后序遍历 + 中序遍历 = 一棵确定的二叉树

先序遍历 + 后序遍历 = 啥也不是

哈夫曼树

哈夫曼（Huffman）最早给出一个带有一般规律的算法（哈夫曼算法）：

根据给定的 n 个权值 \{W_1 ,W_2 ,\cdots, W_n\} 构成 n 棵二叉树的集合 F=\{T_1 ,T_2 ,\cdots,T_n\}，其中每棵二叉树 T_i 中只有一个带权为 W_i 的根结点，其左右子树均空。
在 F 中选取两棵根结点的权值最小的树作为左右子树构造一棵新的二叉树，且置新树的根结点的权值为其左右子树根结点的权值之和。
在 F 中删除这两棵树，同时将新树加入 F 中。
重复 \texttt{2} 和 \texttt{3}，直到 F 中只含一棵树为止。

扩充二叉树

概念：扩充二叉树是指将原二叉树中每个凡缺少左、右孩子的结点，均扩充为带左、右两个孩子。

若扩充二叉树有 n 个内部结点（扩充前具有的结点），则有 n+1 个外部结点。

证明：根据二叉树性质 3（对任意一棵二叉树，如果度为 2 的结点数为 n_2，则其叶子结点数为 n_2+1），扩充二叉树的内部结点的度都是 2，有 n 个内部结点，则外部结点（即叶子）有 n+1 个。
扩充二叉树的内外路径长度长度 I、E 的关系是 E = I + 2n。

证明：（数学归纳法）

当 n=1 时，由于只有一个内部结点 I=0 ，E=2，所以 E=I+2n。

假设对于所有的 k，都有 E_k = I_k + 2k。

当 k+1 时，即添加一个内部结点，设其路径长度为 L，

则

I_k+1 = I_k + L

\\ & = E_k + L + 2 \\ & = ( I_k + 2 k ) + L + 2\\ & = I_k + L + 2 k + 2 \\ & = I_{k+1} + 2 (k+ 1) \end{aligned}

二叉树

在二叉树的第 i 层上至多有 2^{i - 1} 个结点。（i \ge 1）
深度为 k 的二叉树至多有 2^k-1 个结点。（k \ge 1）
对任意一棵二叉树，如果度为 2 的结点数为 n_2，则其叶子结点数为 n_2+1。

证明：设叶子结点数为 n_0，度为 1 的结点数为 n_2，则该树结点总数为：

n = n_0 + n_1 + n_2 \space \;\;\;\;\;\;\;\;\; (1)

树中结点之间的连线成为分支。树中除根结点外，其余每个结点都有一个分支进入，设 A 为二叉树分支的总数，则有：

A = n - 1

另一方面，这些分支都是由度为 1 或 2 的结点射出的，所以

A = n_1 + 2 \times n_2

所以

n - 1 = n_1 + 2 \times n_2 \;\;\;\;\;\; (2)

联立 (1),(2)，可得 n_0 = n_2 + 1。

具有 n 个结点的完全二叉树的深度为 \left\lfloor \log _2 n \right\rfloor + 1。

证明：设深度为 k 的完全二叉树的结点数为 n。

所以有 2^{k-1} - 1 < n \le 2^k - 1。

转换为 2^{k-1} \le n < 2^k。

于是 k-1 \le \log_2 n < k。

因为 k 是整数，所以 k=\left\lfloor \log _2 n \right\rfloor + 1。
对于一颗具有 n 个结点的完全二叉树编号，对于每个编号为 i 的结点：
- 当 i=1，结点 i 为根；当 i>1，其双亲结点为 \dfrac{i}{2}。
  - 若 2 i > n，则结点 i 无做孩子，结点 i 为叶子；否则，左孩子为 2i。
  - 若 2i+1>n，则结点 i 无右孩子；否则，右孩子为 2i+1。

二叉搜索树 BST

二叉搜索树是一种二叉树的树形数据结构，其定义如下：

空树是二叉搜索树。
若二叉搜索树的左子树不为空，则其左子树上所有点的附加权值均小于其根节点的值。
若二叉搜索树的右子树不为空，则其右子树上所有点的附加权值均大于其根节点的值。
二叉搜索树的左右子树均为二叉搜索树。
二叉搜索树上的基本操作所花费的时间与这棵树的高度成正比。对于一个有 n 个结点的二叉搜索树中，这些操作的最优时间复杂度为 O(\log n)，最坏为 O(n) （链）。随机构造这样一棵二叉搜索树的期望高度为 O(\log n)。
给定n个不同数值的点构成的二叉搜索树有卡特兰数种。

排序

排序算法	是否稳定	最优时间复杂度	平均时间复杂度	最坏时间复杂度
选择	非稳定	O(n^2)	O(n^2)	O(n^2)
插入（Insertion)	稳定	O(n)	O(n^2)	O(n^2)
冒泡	稳定	O(n)	O(n^2)	O(n^2)
希尔（Shell）	非稳定	O(n)	与选取方式有关	O(n^2)
归并	稳定	O(n \log n)	O(n \log n)	O(n \log n)
快排	非稳定	O(n \log n)	O(n \log n)	O(n^2)
堆排（Heap）	非稳定	O(n \log n)	O(n \log n)	O(n \log n)
计数	稳定	O(n+w)	O(n+w)	O(n+w)
桶	稳定	O(n)	O(n+n^2/k+k)	O(n^2)
基数（Radix）	稳定	O(kn+\Sigma w_i)	O(kn+\Sigma w_i)	无，但是会炸空间
锦标赛（树形选择）	非稳定	O(n \log n)	O(n \log n)	O(n \log n)
Tim	稳定	O(n)	O(n \log n)	O(n \log n)

注：w 为数的值域。k 为分出的块数。

数学

\large C_n^m = C_{n - 1}^{m-1} + C_{n-1}^m
\large C_m^n= {\dfrac{m!}{(n-m)!\times n!}}
\large A_m^n = {\dfrac{m!}{(n-m)!}}
裴蜀定理：设 a,b 为不为零的整数，对任意整数 x,y，满足 \gcd(a,b) | ax+by，即存在 ax+by=\gcd(a,b)。
卡特兰数
- 前几项（从第 0 项开始）：1,1,2,5,14,42,132。
- C_{n} = \dfrac{4\times n-2}{n+1}\times C_{n-1}=C_{n+1} = \dfrac{C^n_{2n}}{n + 1} = C^n_{2n}-C^{n-1}_{2n}
全错排：f(0)=1,f(1)=0,f(n)=(n-1)(f(n-1)+f(n-2))(n>1)

图

有向图 + 无向图 = 混合图。
图的每条边有边权，称为 赋权图。如果边权都是正实数，就称为 正权图。
图的点数也被称为图的阶。
一个顶点 v \in V 的邻域是所有与之相邻的顶点所构成的集合，记作 N(v)。
图中有自环和重边，称为 多重图。
度为 0 的点称为孤立点。
度为 1 的点称为 悬挂点/叶节点。
图中每个顶点的度数都为常数 k，称为 k- 正则图。
如果给定一个序列 a_i，可以找到一个图 G，以其为度数列，则称 a_i 是 可图化 的。
如果给定一个序列 a_i，可以找到一个简单图 G，以其为度数列，则称 a_i 是 可简单图化 的。
支配点（具体看题目，网上搜索的定义不一，此为 OI-wiki 的解释）度为总边数 -1 的点为支配点。
支配集：一个顶点子集，使得图中的每一个顶点要么属于这个子集，要么与这个子集中的某个顶点相邻。有向图中可划分出出-支配集和入-支配集。
团是图中的一个顶点子集，其中每两个顶点之间都有边相连。换句话说，团是图中的一个完全子图。
设图 G，若存在边子集 F⊆E(G)，使得 G 中的任意顶点均与 F 中的某条边关联，则称 F 为 G 的边覆盖集，即 边覆盖。边数最少的边覆盖集称为最小边覆盖，其所含边的个数称为边覆盖数。点覆盖类似。
‌图的匹配指的是图中的一个边子集，其中任意两条边都不共享顶点。换句话说，匹配中的每条边都是独立的，它们之间没有公共的端点。也可叫做边独立集。
- 最大匹配：包含边数最多的匹配。
- 完美匹配：完美匹配是指图中的每个顶点都恰好与匹配中的一条边相关联。
- 准完美匹配：图中只有一个顶点不被匹配。
- 交替路径：从一个未匹配点出发，依次经过非匹配边、匹配边、非匹配边等形成的路径。
- 增广路径：是一种特殊的交替路径，它连接两个未匹配点，并且路径上的匹配边和非匹配边交替出现。起点和终点都是未匹配点，路径上的边数为奇数。找到一条增广路径，就意味着可以得到一个更大的匹配，因此增广路径在寻找最大匹配的过程中起着关键作用‌。
- 托特定理：一个图 G 有完美匹配当且仅当对于 G 的任意子集 S，连通分支 C(S) 的数量满足以下条件：G 中属于 S 的顶点数减去 C(S) 中奇数度顶点的分支数不超过 |S| - 1。
如果一张无向连通图的每条边最多在一个环内，则称它是一棵 仙人掌。多棵仙人掌可以组成沙漠。
反图指的是点集不变，每条边反向得到的图。
无边图 = 空图 = 死图。
有向简单图中任意两点恰好有一条单向边相连，称为 竞赛图。
无向简单图中存在一个点为支配点，其余点没有边相连，称为 菊花图/星图。
无向简单图中存在一个点为支配点，其余点构成一个环（圈），称为轮图。
补图 = 完全图 - 原图。
若一张有向图的边替换为无向边后可以得到一张连通图，则称原来这张有向图是 弱连通的。
若一张有向图的节点两两互相可达，则称这张图是 强连通的。
一个具有N 个顶点的图，在去掉任意 K-1 个顶点后所得的子图仍连通，而去掉 K 个顶点后的图不连通，则称该图是 K- 点联通 的。K 称作图 G 的点连通度。边连通相似。

咕咕咕咕咕咕咕咕咕咕咕