图论01 基本概念&定义
Published:
\newcommand\norm[1]{\left\lVert#1\right\rVert} \newcommand\abs[1]{\left\lvert#1\right\rvert} 还是记一下吧，方便看博客的人(真的会有人看吗喂！)
图论基本概念
好多啊,还是英文,记不住…..
这里的图默认是有限图
点(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$ 中是所有圈组成的线性空间。