图论笔记 - 极简极入门级

图的概念

• 环(loop, selfloop) ：两个端点相同的边
• 棱(link) ：两个端点不同的边
• 孤立点(isolated vertex) ：不与任何顶点相邻的顶点
• 简单图(simple graph) ：无环，无重边的图
• 平凡图(trival graph) ：仅有一个顶点的图（可有多条环）
• 空图(empty graph)/零图 ：没有边的图（注意：任何一图都有$V\neq \emptyset$）
• 奇点(odd vertex)/偶点(even vertex) ：度为奇/偶的点
• 悬挂点(end vertex)/叶点(leaf) ：度为1的顶点
• 悬挂边(end edge) ：悬挂点的关联边
• 邻域(neighborhood) ：点$u$相邻的点的集合称为点$u$的邻域，记作$N(u)$
• 独立集(independent set) ：若图$G$的顶点子集$V’(V’\subseteq V(G))$中任意两个顶点在图$G$中都互不相邻，则称$V’$为图$G$的独立集
• 有向图的基础图 ：将有向图每条边改为无向边得到的图
• 无向图的定向图 ：将无向图每条边改为有向边得到的图
• 完全图(Complete graph) ：任意两点之间都有边的图（$n$个顶点的完全图记为$K_n$）
• 二部图(偶图, bipartite graph) ：$G=(X, Y; E)$，其中$X\cap Y=\emptyset$且$V(G)=X+Y$（将$G$分为$X$和$Y$两个独立集）
• 完全二部图 ：$K_{m, n}$指$|X|=m, |Y|=n$的二部图
• k-正则图(k-regular g.) ：每个顶点度都为$k$的_无向_简单图
• 线图 / 边图 ：以图的边为顶点所做的图
• 联图 ： 不相交的图$G_1$和$G_2$，将$G_1$中的每个顶点分别和$G_2$中每个顶点相连得到的图
• 途径(walk) 例如$AaBcEdB$；迹(trail) 是边各不相同的途径；路(path) 是顶点各不相同的途径（顶点不同说明边也一定不同）

  	节点重复情况	边重复情况
  途径(Walks)	允许	允许
  迹(Trails)	允许	不允许
  路(Paths)	不允许	不允许
  回路(Circuits) ⇔ 闭迹	允许	不允许
  圈(Cycle) ⇔ 起点终点相同的路	不允许(起点除外)	不允许

• 边割 / 割集 ： 连接$S$和$V\backslash S$的所有边（$S$非空）；关联边割 ：$V={v}$（只有一个顶点）
• 强连通 ：任意两点相互可达；单向连通 ：任意两点有可达方式；弱连通： 有向图的基础图连通
• 关联矩阵(Incidence Matrix) ：“点”行“边”列的矩阵（点1有向外的边2则$mat[1][2]=1$，若边2指向点1则$mat[1][2]=-1$，其余为$0$）若边有权则增加一行代表权，若边有多个权则增加多行。两图同构$\Leftrightarrow$关联矩阵可通过行列变换转化
• 邻接矩阵(Adjacency Matrix) ：“点”行“点”列的矩阵（点1有指向点3的边则$mat[1][3]=1$，其余为$0$）若边有权则值为权而不是$1$
• 弧表(Arc List) ：3（或2）行“边（+1）”列的矩

  起点	1	1	2	3	4	4	5	5
  终点	2	3	4	2	3	5	3	4
  权	8	9	6	4	0	3	6	7

• 邻接表(Adjany Lists) ：“点”大小的指针数组，数组中每个指针是链表头节点，链表节点是从这个点出发的所有的边
• 割边(cut edge) ：$e$为图$G$的割边$\Leftrightarrow\omega(G - e) = \omega(G) + 1$
• 偏心率 / 离心率 ：$e(v) = max({d(u, v)|u\in V(G)})$
• 半径 ：$r(G) = min{e(v)|v\in V(G)}$
• 直径 ：最大偏心率
• 中心点 ：偏心率等于半径的点
• 中心 ：中心点的集合
• 边割(cut edge) ：一端在$S$一端在$\overline{S}$的边的集合
• 键(bond) ：极小非空边割
• 余树 ：图$G$生成树$T$的补图$\overline{T}$称为$G$的余树
• 竞赛图 ：无向完全图的定向图
• 团 ：$V$的子集$S$中任意两点在$G$中相邻，称$S$为图$G$的团
• 覆盖(covering) / 点覆盖(vertex cover) ：$V$的子集$K$，$G$中每条边都至少有一端点在$K$中

• TODO: 匹配

记号：

• $\mathcal{v}=|V(G)|$，$\varepsilon =|E(G)|$（点的个数、边的个数）
• $\Delta(G)$：最大度；$\delta(G)$：最小度
• $d^-(v)$：点$v$的入度；$d^+(v)$：点$v$的出度
• $uv$一般指无向边，$<u, v>$一般指有向边
• $G^C$图$G$的补图
• $=$ ：恒等（完全相同。a和a’是同构不是恒等）；$\cong$：同构（非标号图一般称为同构）
• $\omega(G)$： $G$的分支数
• $W(G)$： 赋权图的权（每条边的权的和）
• $e(v)$：点$v$的 偏心率/离心率
• $r(G)$：图$G$的 半径
• $G[E\setminus E’]$: $G$的边导出子图（点可能变少）；$G-E’$：$G$的边去掉$E’$后的图（点不变）
• $\alpha(G)$：独立数(independent number) 最大独立集的元素个数； $\beta(G)$：覆盖数(covering number) 最小覆盖的元素个数。$\alpha + \beta = v$

End

The End, thanks!

原创不易，转载经作者同意后请附上原文链接哦~