图 G G G 的定义： G = < V , E , φ > G = G=。其中， V V V 是点集， E E E 是边集， φ \varphi φ 是点与边的对应关系

点 a a a 到点 b b b 的有向边，记 < a , b > ；点 a a a 到点 b b b 的无向边，记 ( a , b ) (a,b) (a,b)

边与其两个端点相连。无向图中，称之为关联；有向图中，称之为相邻

点的度：该点作为边端点的次数

孤立点：度为 0 的点

悬挂顶点：度为 1 的点

悬挂边：悬挂顶点的边

平行边：两条边的起点和终点分别相同

环：起点和终点是同一个点的边

图 G G G 的最大度，记 Δ ( G ) \Delta (G) Δ(G)；最小度，记 δ ( G ) \delta (G) δ(G)

有向图还细分为出度、入度

握手定理：无向图和有向图中，所有顶点度数之和等于图的边数的二倍；有向图中，所有顶点出度之和等于所有顶点入度之和等于图的边数

数列可图化，当且仅当数列所有元素之和为偶数

多重图：含平行边的图

简单图：不含平行边和环的图

n n n 阶完全图：有 n n n 个顶点的完全图，记为 K n K_n Kn​

完全无向图：每个节点都与其余节点相连，构成的简单无向图；

完全有向图：每对节点中都有相反的两条有向边，构成的简单有向图

正则图：所有顶点的度数都一样。完全图是正则图的特例

子图：对原来图中的边和节点进行删减后的图

生成子图：对原来图中的边进行删减后的图。生成子图是子图的特例

带权图：边有权值的图

通路、回路

初级通路（路径）、初级回路（圈）：所有的点不同

简单通路、简单回路：所有的边不同

连通图：任意点都是连通的；等价定义，连通图的连通分支为 1

连通分支：连通关系的导出子图，记 W ( G ) W(G) W(G)

强连通图：有向图中，任意两个节点都相互可达

单向连通图：有向图中，任意两个节点至少存在一个点到另一个点

弱连通图：将有向图变为无向图，仍然是连通图

G − v G-v G−v：在图 G G G 中删除点 v v v 以及关联的边

G − V ′ G-V' G−V′：在图 G G G 中删除集合 V ′ V' V′ 中所有的点以及点所关联的边

G − e G-e G−e：在图 G G G 中删除边 e e e

G − E ′ G-E' G−E′：在图 G G G 中删除集合 E ′ E' E′ 中所有的边

设 V ′ V' V′ 是 V V V 真子集， V ′ ′ V'' V′′ 是 V ′ V' V′ 真子集。首先进行 G − V ′ G-V' G−V′ 操作后，是非连通图，再将原来的图进行 G − V ′ ′ G-V'' G−V′′ 操作后，连通性不变。则 V ′ V' V′ 就是点割集。点割集只含一个元素，则该元素称之为割点

设 E ′ E' E′ 是 E E E 真子集， E ′ ′ E'' E′′ 是 E ′ E' E′ 真子集。首先进行 G − E ′ G-E' G−E′ 操作后，是非连通图，再将原来的图进行 G − E ′ ′ G-E'' G−E′′ 操作后，连通性不变。则 $ E’ $ 就是边割集。边割集只含一个元素，则该元素称之为桥

出度是所有横向元素和，入度是所有纵向元素和

A 1 , A 2 , . . . , A n A^1, A^2,...,A^n A1,A2,...,An 矩阵的第 [ i ] [ j ] [i][j] [i][j] 个元素代表长度为 1 , 2... , n 1,2...,n 1,2...,n 从 v i v_i vi​ 到 v j v_j vj​ 的边的个数

A 1 , A 2 , . . . , A n A^1, A^2,...,A^n A1,A2,...,An 矩阵的主对角线元素之和代表长度为 1 , 2... , n 1,2...,n 1,2...,n 的回路个数

A 1 , A 2 , . . . , A n A^1, A^2,...,A^n A1,A2,...,An 矩阵的所有元素之和代表长度为 1 , 2... , n 1,2...,n 1,2...,n 的通路个数

无向图是对称矩阵；简单图是布尔矩阵，且主对角线元素为 0

可达矩阵 P P P，若 v i v_i vi​ 到 v j v_j vj​ 可达，则 $ P[i][j]$ 置 1，否则为 0

可达矩阵主对角线元素全为 1；图为强连通图，当且仅当可达矩阵元素全为 1

A 1 + A 2 + . . . + A n A^1+ A^2+...+A^n A1+A2+...+An 得到矩阵，将其非 0 元素改为 1，就是可达矩阵 P P P

欧拉通路：通过图中所有边一次且仅一次的通路

欧拉回路：通过图中所有边一次且仅一次的回路

欧拉图：有欧拉回路的图

半欧拉图：有欧拉通路无欧拉回路的图

欧拉通路是简单通路；欧拉回路是简单回路；环不影响欧拉性

无向图 G G G 为欧拉图当且仅当 G G G 连通且无奇度顶点

无向图 G G G 为半欧拉图当且仅当 G G G 连通且恰有两个奇度顶点

有向图 G G G 为欧拉图当且仅当 G G G 连通且每个顶点出度等于入度

有向图 G G G 有欧拉通路当且仅当 G G G 连通且恰有两个奇度顶点，其中一个入度比出度大，另一个出度比入度大一，其余出度、入度相等

哈密顿通路：经过图中所有顶点一次且仅一次的通路

哈密顿回路：经过图中所有顶点一次且仅一次的回路

哈密顿图：有哈密顿回路的图

半哈密顿图：有哈密顿通路无哈密顿回路的图

哈密顿通路是初级通路；哈密顿回路是初级回路；环与平行边不影响哈密顿性

无向哈密顿图的必要条件：设无向图 G G G 是哈密顿图， V 1 V_1 V1​ 是 V V V 非空真子集，均有 W ( G − V 1 ) ⩽ ｜ V 1 ｜ W(G-V_1) \leqslant ｜V_1｜ W(G−V1​)⩽｜V1​｜

无向哈密顿图的充分条件：设 G G G 是 n ( n > 2 ) n(n>2) n(n>2) 阶无向简单图，对任意不相邻的顶点 u , v u ,v u,v，均有 n ⩽ d ( u ) + d ( v ) n \leqslant d(u)+d(v) n⩽d(u)+d(v)

无向哈密通路的充分条件：设 G G G 是 n n n 阶无向简单图，对任意不相邻的顶点 u , v u ,v u,v，均有 n − 1 ⩽ d ( u ) + d ( v ) n-1 \leqslant d(u)+d(v) n−1⩽d(u)+d(v)

若图能重新绘制成边不想交的图，则称为平面图

欧拉公式：设 G G G 为 n n n 阶 m m m 条边 r r r 个面的连通平面图，则 n − m + r = 2 n-m+r=2 n−m+r=2

树：无回路的连通无向图。度数等于 1 的顶点称作树叶，度数大于等于 2 的顶点称作分支点.

平凡树：平凡图

森林：每个连通分支都是树的非连通的无向图

设 G G G 是 n n n 阶级 m m m 条边无向图，以下命题等价

设 G G G 为无向连通图， G G G 的生成子图是树，则称为生成树，记 T T T

生成树的树枝： G G G 在 T T T 中的边

生成树的弦： G G G 不在 T T T 中的边

余树：所有生成树的弦构成的导出子图

最小生成树：带权图中权值最小的生成树

最小生成树的算法：破圈法（删最大边）和避圈法（加最小边）

Kruskal 算法和 Prim 算法都是避圈法