图论入门

前言

可能有锅

内容

比较基础的定义

图的定义：一个 $G=\{V,E,w\}$ 分别为边集，点集，关系
也有二元组定义
重边的定义： $(u,v)$ 重复的边
独立集(或者稳定集)定义：图 $G $中两两互不相邻的顶点构成的集合
二部图(或二分图)定义:设 $G=(V,E)$ 是一个无向图，如果顶点 $V$ 可分割为两个互不相交的子集 $(A,B)$ ，并且图中的每条边 $(i，j)$ 所关联的两个顶点 $i$ 和 $j$ 分别属于这两个不同的顶点集
图的色数 $\chi(G)$ 给定图形边缘所需的最少颜色数量称为图形的边色数。
一个图是 $k-$ 分的当且仅当色数为 $k$
子图的定义 $V(H) \subseteq V(G),E(H)\subseteq E(G)$ 或者说 $G$ 包含 $H$
同构是在数学对象之间定义的一类映射，它能揭示出在这些对象的属性或者操作之间存在的关系。若这两个数学结构之间存在同构映射，那么这两个结构叫做是同构的。一般来说，如果忽略掉同构的对象的属性或操作的具体定义，单从结构上讲，同构的对象是完全等价的 (在图上就是两个图的邻接矩阵等价)
完全图，符号为 $K_n$ ,完全二部图 $K_{n,m}$
结论:顶点集为n的图中简单图的数目为 $2^{\frac{n}{2}}$
自补的定义自补图是相对于完全图来说,把一个图添加边是的其成为完全图所构成的图叫补图。当一个图和它的补图相同时,为自补图。
$Peterson$ 图
描述图的形状(三角形，爪形，掌形等)
三角形的定义: $K_3$ 的一个拷贝
围长的定义:最短环的长度
自同构，顶点传递的定义(二分图有 $2(t!)^2$ 个同构)
有关图的连通性的定义(通道，迹，端点，路径，内定点，长度，闭合的)
联通的定义
联通分量
$n$ 个顶点 $k$ 条边至少有 $max{1,n-k}$ 个连通分量
割边和割点的定义( $G[T] \to G-\overline{T},\overline{T}=V(G)-T$ )
割边
一个图有奇数环可以判定不是二分图
图的并的定义
定理：完全图能被表达成n个二部图
欧拉回路定义
有穷图必然存在一条极大路径
图的每一个点度为2，则必然存在一个环
如果有一个图有一条不是环的边，则至少有两个点不是割点
定义：偶图，度全为偶数的图
偶图可以分解为若干个环
$TONCAS$ 这东西没找到什么引用，估计就是本书给的定义,意思是显然的必要条件也是充分的
$TONCAS$ 证明的东西
度，领域
图的最大度 $\Delta(G)$ 最小度 $\delta(G)$ ,如果 $\delta(G)=\Delta(G)=k$ 则说明这张图是 $k-$ 正则的，V的邻接顶点叫做领域 $N(V)$
图 $G$ 的大小 $e(G)$ 即为边数， $n(G)$ 为图的阶，即为顶点数
度-和公式 $\sum\limits_{e\in{G}} d(v)=2*e(v)$
顶点的平均度 $\frac{2*e(G)}{n(G)}=k,\delta(G)\leq k\leq \Delta(G)$
桥 $low[t]>dfn[son[t]]$ 即为桥
顶点删除子图的定义
如果 $k>0$ 那么 $k-$ 正则的二部图的部集中含有相同个数的顶点
极值问题有关内容：
如果 $G$ 是一个简单的 $n$ 顶点的图且满足 $\delta(G)\geq(n-1)/2$ 那么 $g$ 是联通的
顶点集合互不相交的两个图 $G,H$ 的非交并或者和，记为 $G+H$
如果 $G+H$ 是联通的，那么 $G,H$ 就是 $G+H$ 的分支， $K_m+K_m=\overline{k}_{n,m}$
任意图中含有偶数个度数为奇数的顶点
每个无圈图都有一个二部子图包含 $\frac{e(G)}{2}$ 条边(用一个算法证明)
二部子图的全局最大边数是 $e(G)-k,k$ 表示从每一个奇环中删去一条边的最小边数
只有完全二部图中可以最大的取得不包含三角形的最大边数
$X-$ 无关图 $G$ 是 $X-$ 无关的，则他没有同构与 $X$ 的诱导子图
$Mantel$ 定理，在一个 $n-$ 顶点的三角形无关的简单图的最大边数为 $\lfloor\frac{n^2}{4}\rfloor$ （二分图得到极值）
归纳陷阱
$3-$ 正则的简单图不能通过 $k_4$ 扩张得到
图解序列（度序列）就是每个点的度从大到小排列
$d_1,d_2,...,d_n$ 是一个度序列的话当且仅当 $\sum{d_i}$ 是一个偶数
$2-$ 调换 $(x,y),(m,z)\to (x,z),(y,m)$ （这里是无向图）
显然，每个 $2-$ 调换都保持了原图的度
如果顶点集 $G,H$ 均为 ${V}$ 的简单图，如果 $d_H(v)=d_G(v)$ 对 $\forall v\in V$ 成立那么可以通过 $2-$ 调换从 $G$ 变成 $H$
有向图的定义：三元组 $V(G),E(G)$ 以及一个有序顶点对的函数（关系），第一顶点是尾部，第二顶点是头部
圈（环），重边，简单的有向图，后继，前驱的定义（太简单了之后写）
有穷状态机（也叫有穷自动机，或者离散系统），这东西可以用有向图表示（用顶点表示状态，边表示状态的转换，边上的标记表示触发转换的事件，自环表示这件事件对结果没有影响）
$Markov$ 链，即马尔科（可）夫链，一个有穷状态机的边上的标记表示状态转化发生的概率，如果离开这个点的所有概率之和为1，那么称之为 $markov$ 链
一个有向图是一条路径，当其拓扑排序唯一
函数有向图，沿一条路劲进行就是函数的迭代
在图和有向图中，子图，同构，分解，并的定义是相同的，在有向图的 $G$ 的邻接矩阵 $A(G)$ 中， $i,j$ 代表 $v_i,v_j$ 的边数，在他们的关联矩阵 $M(G)$ 中，如果 $i,j$ 的元素为 $+1$ 那么说明 $v_i$ 是 $e_j$ 的尾部，反之为头部
一个有向图是弱联通的，当且仅当底图（有向边变成无向边）联通的，一个有向图是强连通的，那么任意两点可达
核的定义 $S \subseteq V(D)$ 并且 $S$ 不包含边并且每个不在 $S$ 的顶点都在 $S$ 中又一个后继
有向图的任意闭合奇通道中包含一个环
没有奇环的有向中均有一个核
出度 $d^+$ ，入度 $d^-$ ,出邻域(后继集) $N^+$ ,入邻域(前驱集) $N^-$ 。最小入度最大入度等(P44)
有向图 $D$ 的分裂是一个二部图 $G$ ,其部集 $V^+,V^-$ 是 $V(D)$ 的两个拷贝，原图的 $(u,v)$ 变成了 $(u^+,v^-)$
欧拉迹是包含所有边的一个闭合迹，一个有欧拉回路的有向图是欧拉图。
对有向图 $G$ 如果 $\delta^{+}(G)\geq 1$ 或者 $\delta^{-}(G)\geq 1$ 那么图中又一个有向环
欧拉图的判定1. $\forall v ,d^+(v)=d^-(v)$ ，2.底图最多又一个非平凡分量
$ de~Brujin $环:有 $2^n$ 个长度为n的二进制字符串，有方法使得以循环顺序防止 $2^n$ 个二进制数字使得其中 $2^n$ 个连续数字的字符串彼此不同（这里咕一下）
定向和竞赛图， $G$ 的定向是一个有向图 $D$ ,一个定向图是一个简单图的定向，一个竞赛图是完全图的定向
竞赛图方向指向被赢的方向，任意竞赛图有一个王，王到每个点的距离不超过二（证明比较简单）
非负整数对是一个有向图的度对序列当且仅当他们的和是一个偶数（或者说这个度序列是可图的）

树和距离

1.定义：无环图，森林，树，叶子，悬垂点，生成子图（顶点集为 $v(G)$ 的一张子图）

2.引理：每棵至少具有两个顶点的树至少有两个叶子，从一颗 $n-$ 顶点的树删除一片叶子后得到一颗有 $n-1$ 顶点的树

3.对于 $n-$ 顶点的图，有以下等价的东西

A.G是联通且无环的

B.G是联通且具有n-1条边

C.G有n-1条边且无环

D.G无环且对任意一条 $u,v$ 恰好有一条 $u \to v$ 的路径

A.树的每一条边都是割边 B.树添加一条边恰好成环 C.每个联通的包含一个生成树（TONCAS）
如果 $T$ 是连通图且 $G$ 的生成树 $e \in E(T)-E(T')$ 则存在 $e'\in E(T')-E(T)$ 使得 $T-e+e'$ 也是一颗生成树
$Wiener$ 指数$D(G)=\sum_{u,v\in V(G)}\limits{d_G(u,v)} $,在$ P $上取$ MAX $在星形图上取$ min$
推论，若 $H\subseteq G$ 那么 $d_{G}(u,v)\leq d_{H}(u,v)$
$cayley$ 公式 $[n]$ 含有 $n^{n-2}$ 棵树
$prufer$ 编码， $f(T)=(a_1,a_2,...,a_{n-2})$ , $a_i$ 表示编号最小的叶节点相邻节点（动态拆树），双指针可以 $O(N)$ 构造回去
显然这这东西对应回去的树一一对应，因此 $n^{n-2}$ 恰好对应了 $cayley$ 公式（实际上这东西就是用来证明 $cayley$ 的）
具有指定顶点的树有 $\frac{(n-2)!}{\Pi((d_i-1)!)}$ 棵证明也比较简单（ $prufer$ 方法可以构造，即先确定叶节点再确定非叶节点）
图的基本操作：边 $e$ 的收缩，表示为 $G\cdot e$ 表示 $e=(u,v)$ 合并成一个点（不过要保留重边）
因此可以得到结论 $\iota (G)=\iota(G-e)+\iota(G\cdot e)$ 这个结论似乎一目了然
矩阵树： $M=$ 度矩阵-邻接矩阵， $M$ 的行列式即为所求
矩阵树定理咕咕咕
优美标记 $f:V(G)={0,1,2,3,...,m}$ 使得不同的顶点被标记成不同的整数且 $|f(u)-f(v)|$ 对 $\forall (u,v)\in E(G)={1,2,3,4,...,m}$ ，推论 $K_{2m+1}$ 可以分解为 $T_{2m+1}$ 个拷贝，证明首先证明每个值会被取 $2m+1$ 次，然后把这些放到每一棵树中即可
毛虫形，极大的 $P$ 关联于所有的边判断的充要条件，不包含 $k_{1,3}$ 悬垂点向外拓展的图
分叉，出流树，是一棵树的定向
有向图的矩阵树定理咕咕咕