还是记一下吧，方便看博客的人(真的会有人看吗喂！)
图论基本概念
好多啊,还是英文,记不住.....
这里的图默认是有限图
点(vertex/vertices),边(edge)
边\(\left\{x,y\right\}\)可简记为\(xy\)
基本符号
\(\left[n\right]=\left\{1,\dots,n\right\},n\in\mathbb N\)
\(\binom{n}{k}=\left\{ {x\subseteq \left[n\right]|\left|x\right|=k}\right\}\)
\(\binom{V}{k}=\left\{x\subseteq V|\left|x\right|=k\right\}\)
图(graphs)
图的严格定义由有序二元组表示,\(G=(V,E)\)表示以\(V\)为点集,\(E\)为边集的图,这里\(E\subseteq \binom{V}{2}\)
这里的图又叫无向简单图,不含重边(multi edge)和自环(loops)
无向图中的边用集合定义，连接 \(x,y\) 的边实际上是 \(\left\{\;x,\;y\;\right\}\)，简记为 \(xy\)
其中用\(V(G)\)和\(E(G)\)分别表示图\(G\)的点集，边集
有向图(directed graphs)
\(G=(V,E)\) 其中 \(E\subseteq V^2\)
有向图中的边用有序二元组定义
多重图(multi graph)
\(G=(V,E)\),其中\(E\)是一个多重集且\(\forall x\in E\)都有\(x\in \binom{V}{2}\cup\binom{V}{1}\)
也就是可以有重边和自环
超图(hypergraph)
\(G=(V,E)\),其中\(E\subseteq 2^V-\varnothing\)
也就是一条边可以连接任意多个点,这个可以用建立辅助点来理解
下面默认讨论的是简单图
相邻(adjacent/neighbors)
两个点\(x,y\)相邻定义为\(\left\{x,y\right\}\in E\)
两条边\(e_1,e_2\)相邻定义为\(e_1\cap e_2\neq\varnothing\)
完全图/团(complete graphs/cliques)
对于\(G=(V,E)\)若\(\forall x,y\in V\)都有\(\left\{x,y\right\}\in E\)那么称\(G\)是一个完全图/团
我们记含有\(n\)个点的完全图为\(K_n\)或\(K^n\).特别地,\(K_3\)叫做三角形(triangle)
独立(independent)
不相邻的点对被称为是独立(independent)的
对于图\(G=(V,E)\)若\(\exists V'\subseteq V\)使得\(\forall x,y\in V'\)都有\(\left\{x,y\right\}\notin E\),那么我们称点集\(V'\)是独立集(independent set)
独立集的性质也被称为stable(不会翻,也可能是读错了)
同态(homomorphism)和同构(isomorphism)
考虑两个图\(G=(V,E)\)和\(G'=(V',E')\),若存在映射\(f:V\mapsto V'\)使得\(\forall x,y\in V\)都有\(\left\{x,y\right\}\in E\Rightarrow \left\{f(x),f(y)\right\}\in E'\),那么我们称\(G\)和\(G'\)同态
若同态映射同时是一个双射(bijection),那么就得到了一个\(G\)和\(G'\)的同构,写作\(G\simeq G'\)
很显然\(G\)与\(G'\)同构\(\iff \begin{aligned} G\)与\(G'\)同态\(\and G'\)与\(G\)同态,且易得同构是一个等价关系(equivalence relation)
在不关注点和边的标号时,我们认为同构的图相等,此时记作\(G=G'\)
图的运算
一下记 \(G=(V,E)\),\(G'=(V',E')\)
图的并交补
定义\(G\cup G'=(V\cup V',E\cup E')\),交同理
若\(G\cap G'=\varnothing\)则称它们不相交(disjoint)
定义\(\overline G=(V,\binom{V}{2}-E)\)为图\(G\)的补图(complement)
子图(subgraph)
若\(V\subseteq V'\and E\subseteq E'\),则说\(G\)是\(G'\)的子图,记作\(G\subseteq G'\)
导出子图(induced subgraph)
若\(G\subseteq G'\and \forall x,y\in V(xy\in E\iff xy\in E')\),则称\(G\)是\(G'\)的导出子图,记作\(G=G'[V]=G'[V(G)]\)
生成图/支撑子图
若\(G=G'[V(G')]\),则称\(G\)是\(G'\)的一个生成图/支撑子图
连通分支/分量(component)
极大的连通子图被称为一个连通分支/连通分量
图的特性(property)
若\(G'\subseteq G\and G'\simeq H\),则记\(P(G,H)=1\),表示图\(G\)具有特性\(H\);否则为\(0\),表示不具有该特性
极大/极小图(maximal/minimal)
我们称一个\(G'\)的子图\(G\)是具有某类特性的极大子图意味着:
\(\forall G''\subseteq G\),都有\(P(G',H)=1\and P(G'',H)=0\)
极小同理.类似的定义还可以用在边的数量上/图的size上等等
图的乘法
若\(G\)和\(G'\)不交,则定义\(G*G'=(V\cup V',\left\{xy|xy\in E\or xy\in E'\or (x\in V\and y\in V')\right\})\)
比如说\(K_2*K_3=K_5\)
line graph(不会翻)
对于图\(G=(V,E)\),构造图\(G'=(E,E')\),其中\(xy\in E'\iff\) 边\(x\)和边\(y\)在\(G\)中相邻
邻点(set of neighbours)
对于图\(G\)中的点\(v\),定义\(N_G(v)=\left\{x|xy\in E\right\}\),把这个集合称为\(v\)的邻点集
度数(degree/valency)
定义图\(G\)上点\(v\)的度数为\(d_G(v)=|E(v)|\),其中\(E(v)=\left\{xv|xv\in E\right\}\)
度数为\(0\)的点被称为孤立点(isolated vertex)
记\(\delta(G)=\max\left\{d_G(v)|v\in V\right\}\)
记\(\Delta(G)=\max\left\{d_G(v)|v\in V\right\}\)
正则图(regular graph)
我们称所有点度数相等的图为正则图.所有点度数为\(k\)的图称为\(k-\)正则图
显然有\(G\)是正则图\(\iff\delta(G)=\Delta(G)\)
特殊地,\(3-\)正则图也叫做cubic
距离(distance)
\(x,y\) 之间的距离定义为 \(\min{xPy}\)，\(P\) 为一条 \(x-y\) 路。距离记作 \(\text{dist}(x,y)\)
直径(diameter)
图 \(G\) 的直径定义为 \(\max{(\text{dist}(x,y))}\)，记作 \(\text{diam} \;G\)
半径(radius)
定义半径为 \(\min\limits_{x\in V(G)}\max\limits_{y\in V(G)}{\text{dist}(x,y)}\)，记作 \(\text{rad}\; G\)
取到半径的端点记作中心点(central vertex)
森林(forest)
森林是无圈图
树(tree)
树是连通的森林
代数基础
考虑集合 \(\left\{\;0,1\;\right\}\) 和其上模2的加法、乘法运算，容易验证这是一个数域，记作 \(F_2\)。
考虑 \(V={F_2}^{|G|}\)，\(V\) 中的元素都是长度为 \(|G|\) 的01向量，很显然 \(V\) 是 \(F_2\) 上的线性空间，我们称之为点空间
类似的考虑 \(E={F_2}^{||G||}\)，这是边空间
不难发现 \(V\) 中的每个向量对应着一个顶点的集合(特征函数)，\(E\) 有类似的结论。
\(E\) 有一个特殊的子空间 \(C\)，\(C\) 中是所有圈组成的线性空间。