这里主要是我自己的一些笔记，帮助我自己快速记忆所用，可能没有定义这么完美。
1.简单图
简单图：无环无平行边的图。下图：左环右平行边
平凡图：
G
=
(
1
,
0
)
G=(1,0)
G=(1,0)
零图：
G
=
(
p
,
0
)
G=(p,0)
G=(p,0)
边数：
e
≤
C
n
2
e\leq C_n^2
e≤Cn2
2.简单图的补图
补图：对于
G
=
(
V
,
E
)
G=(V,E)
G=(V,E)，有
E
1
=
{
u
v
∣
u
≠
v
且
u
,
v
∈
V
}
E_1=\{uv|u \neq v 且 u,v\in V\}
E1={uv∣u=v且u,v∈V}，则
G
G
G 的补图为：
G
‾
=
H
=
(
V
,
E
1
\
E
)
\overline{G}=H=(V,E_1 \backslash E )
G=H=(V,E1\E) 注意：
1、简单图才有补图；
2、
n
n
n 阶简单图与其补图的顶点集是相同的；
3、
n
n
n 阶简单图任意一对顶点邻接(有边)的充要条件是这对顶点在补图中不邻接；
4、
n
n
n 阶简单图与其补图的边数之和等于完全图
K
n
K_n
Kn 的边数。
3.图的同构
有
G
=
(
V
,
E
)
,
H
=
(
U
,
F
)
，
∣
V
∣
=
∣
U
∣
G=(V,E),\quad H=(U,F)，\quad |V|=|U|
G=(V,E),H=(U,F)，∣V∣=∣U∣
若
∃
φ
:
V
→
U
(
φ
是
双
射
)
若 \exists \quad \varphi:V\rightarrow U\quad(\varphi是双射)
若∃φ:V→U(φ是双射)
且
v
1
v
2
∈
E
⇔
φ
(
v
1
)
φ
(
v
2
)
∈
F
且\quad v_1v_2 \in E\Leftrightarrow\varphi(v_1)\varphi(v_2)\in F
且v1v2∈E⇔φ(v1)φ(v2)∈F 则称
G
G
G 和
H
H
H 同构 ，记为
G
≅
H
G\cong H
G≅H（即给
V
V
V 中的顶点重新命名得到新的集合
U
U
U）。例如下图中，第一行的两个图是相等的，只是画法不同；在第二行，左图选出两个不同颜色的点交换位置，得到右图，则左图和右图为同构。
4.完全图
完全图：是一个简单图，图中任意一个顶点都与其他顶点有且只有一条边连接。
n
n
n 个顶点的完全图用
K
n
K_n
Kn 表示，称为
n
n
n 阶完全图。例如：
从左往右依次为：1至5阶完全图，即为
K
1
,
K
2
,
K
3
,
K
4
,
K
5
K_1,K_2,K_3,K_4,K_5
K1,K2,K3,K4,K5 ，完全图的边数为
C
n
2
=
n
(
n
−
1
)
2
C_n^2=\frac{n(n-1)}{2}
Cn2=2n(n−1)。
5.偶图
偶图：在一个图
G
=
(
V
,
E
)
G=(V,E)
G=(V,E) 中，顶点集
V
V
V 可分解为两个非空子集
X
X
X 和
Y
Y
Y，且边的两个顶点分别属于
X
X
X 和
Y
Y
Y （两个顶点不在同一个子集中），且属于同一子集的顶点不邻接，也没有环。偶图可以有平行边。如下图：
现实生活中的例子有很多，比如：老师和课程，一个老师可以教多个课程，一个课程可以有多个老师来教。
6.完全偶图
完全偶图：首先是简单偶图（简单图+偶图），其次
X
X
X 中的每个顶点都与
Y
Y
Y 中每个顶点相连。 若
∣
X
∣
=
n
|X|=n
∣X∣=n，
∣
Y
∣
=
m
|Y|=m
∣Y∣=m，则完全偶图记为
K
n
,
m
K_{n,m}
Kn,m，边数为
n
m
nm
nm；如下完全偶图
K
3
,
3
K_{3,3}
K3,3，顶点分为两部分，蓝色集和红色集，每一个蓝色顶点都与全部红色的顶点邻接，且相同颜色的顶点不邻接。
7. k k k-正则图
k
k
k-正则图：设
G
=
(
V
,
E
)
G=(V,E)
G=(V,E) 为简单图，若
∀
v
∈
V
\forall v\in V
∀v∈V，有
d
(
v
)
=
k
d(v)=k
d(v)=k（顶点度数都为
k
k
k，环算2度），则
G
G
G 为
k
k
k-正则图。
8.途径-迹-路
途径： 图
G
=
(
V
,
E
)
G=(V,E)
G=(V,E) 中的一个有限非空序列
w
=
v
0
e
1
v
1
e
2
v
2
⋯
e
n
v
n
w=v_0e_1v_1e_2v_2\cdots e_nv_n
w=v0e1v1e2v2⋯envn，顶点和边交替出现；途径中边数为途径的长度，
v
0
v_0
v0 和
v
n
v_n
vn 分别为途径的起点与终点，其余顶点为途径的内部点。
迹： 不包含重复边的途径，可以有重复顶点。
路： 不包含重复顶点的途径（一定是迹）。
注： 起点和终点重合的途径、迹、路分别称为图的闭途径、闭迹、圈，闭迹也称为回路。长度为
k
k
k 的圈称为
k
k
k 圈，
k
k
k 为奇数时称为奇圈，
k
k
k 为偶数时称为偶圈。
9.邻接矩阵
邻接矩阵：表示图中各顶点之间的关系，若邻接则为1，反之为0。如下图：
邻接矩阵为：
[
0
1
1
1
1
0
1
1
1
1
0
0
1
1
0
1
]
\begin{bmatrix} 0 & 1 & 1 & 1\\ 1 & 0 & 1 & 1\\ 1 & 1 & 0 & 0\\ 1 & 1 & 0 & 1 \end{bmatrix}
⎣⎢⎢⎡0111101111001101⎦⎥⎥⎤
10.关联矩阵
关联矩阵：表示图中顶点与边之间的关系，通过关联次数来表示，0，1，2（环）。如下图：
关联矩阵为：
[
1
0
0
1
1
0
1
1
1
0
0
0
0
1
0
1
0
0
0
0
1
0
1
2
]
\begin{bmatrix} 1 & 0 & 0 & 1 & 1 & 0 \\ 1 & 1 & 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 & 1 & 2 \end{bmatrix}
⎣⎢⎢⎡110001100101101010010002⎦⎥⎥⎤ 每列相加的和为2（因为一条边关联两个顶点）；每行和是对应顶点度数。
11.匹配
匹配：如果 F F F 是图 G = ( V , E ) G=(V,E) G=(V,E) 的边子集（不含环），且 F F F 中任意两条边没有共同顶点，则称 F F F 为 G G G 的一个匹配或对集或边独立集。匹配是关于边的。如果图 G G G 中的顶点是 F F F 中某条边的端点，则称为 F F F 饱和点，反之为 F F F 非饱和点。
最大匹配： F F F 是图 G G G 的包含边数最多的匹配。
完美匹配：最大匹配包含了图 G G G 中的所有顶点。文章来源：https://www.toymoban.com/news/detail-489591.html
注意：这些匹配都不一定唯一。文章来源地址https://www.toymoban.com/news/detail-489591.html
到了这里，关于图论基础学习笔记的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
