图论基础

由于毕业论文是图论方向的，所以写一篇图论的基础知识笔记.

基础知识

Define 对于连通图 $G = (V,E)$ ，若有 $V’ \subseteq V$， 且 $G[V \setminus V’]$ （即从 $G$ 中删去 $V’$ 中的点），则 $V’$ 是图 $G$ 的一个 点割集（vertex cut），大小为一的点割集称作 割点（cut vertex）.

Define 若连通图 $G$ 对整数 $k$ 满足 $\vert V \vert \geq k + 1$， 且不存在大小为 $k - 1$ 的点割集，则 $G$ 称为 $k$ - 连通图

Define 若对 $H \subseteq G$，满足 $\forall u, v \in V’$，只要 $(u, v) \in E$，均有 $(u, v) \in E’$，则称 $H$是 $G$ 的 导出子图/诱导子图 (induced subgraph).

Define 若 $H \subseteq G$ 满足 $V’ = V$ ，则称 $H$ 为 $G$ 的 生成子图/支撑子图 (spanning subgraph).

Define 设 $G$ 是有限无向图，对于顶点 $u \in V(G)$ ，集合 $N_G(u) = { v \in V(G) \vert uv \in E(G) }$ 称为顶点 $v$ 的邻域.

独立数

Define 对于图 $G=(V,E)$，如果顶点子集 $S \subseteq V$ 满足 $\forall u, v \in S$，$ { u, v } \notin E$，则称 $S$ 为 $G$ 的一个独立集，称 $\vert S \vert$ 为该独立集的基数.

Define 对于独立集 $S$，如果 $\forall v\in V\setminus S$，$\exists u\in S:{u,v}\in E$，则称 $S$ 是极大独立集.

Define 如果 $\vert S \vert$ 是所有独立集中最大的，那么称 $S$ 是最大独立集，并将 $\vert S \vert$ 称作 $G$ 的独立数（independence number），记为 $\alpha(G)$.

哈密顿图（Hamiltonian）

Define 通过图中所有顶点一次且仅一次的通路称为哈密顿通路.

Define 通过图中所有顶点一次且仅一次的回路称为哈密顿回路；具有哈密顿回路的图称为哈密顿图.（图 $G$ 中包含长为 $\vert C(G) \vert$ 的圈.

Define 具有哈密顿通路而不具有哈密顿回路的图称为半哈密顿图.

完全独立生成树（CIST）

Define 如果对于 $G$ 上的两棵生成树中的任意两个顶点 $u$ 和 $v$ ，满足 $u$ 和 $v$ 之问的路径均为顶点不相交路径，则称这两棵树相互完全独立. 若 $n$ 棵生成树两两相互独立 ，则称之为 $n$ 棵独立生成树.

Define 完全独立支撑树( CIST) 设 $G$ 是一个简单无向图，$P_1$ 和 $P_2$ 是图 $G$ 中 顶点 $x$ 到顶点 $y$ 的两条路，如果$P_1$ 和 $P_2$ 除了顶点 $x$ 和顶点 $y$ 以外没有相同的顶点和边，那么称 $P_1$ 和 $P_2$ 是内部不相交的. 设 $T_1$ ，$T_2$ ，$\cdots$，$T_k$ 是图 $G$ 的一组生成树，对图 $G$ 中的任意两个顶点 $r$ 和 $v$ ，如果 $T_1$ ，$T_2$ ，$\cdots$， $T_k$ 中顶点 $r$ 到顶点 $v$ 的路两两内部不相交，那么称 $T_1$，$T_2$，$\cdots$，$T_k$ 是图 $G$ 的一组完全独立支撑树.

Theorem $k$ 连通线图的基础图存在 $k$ 个完全独立支撑树.

Theorem 连通图 $G$ 有 $k$ 个完全独立支撑树，当且仅当 $G$ 的顶点集 $V( G)$ 存在 CIST 划分 $( V_1，V_2， … ，V_k )$ .

Theorem 设 $T_1$，$T_2$，$\cdots$，$T_k$ 是图 $G$ 的一组生成树，$T_1$，$T_2$，$\cdots$，$T_k$ 是一组完全独立支撑树当且仅当 $T_1$，$T_2$，$\cdots$，$T_k$ 是边不相交的，并且图 $G$ 中任意顶点 $v$ 仅在最多一个生成树 $T_i$ 中满足 $d_n(v) >1$.

Theorem 若图G含有$ k$ 个完全独立生成树，则图 $G$ 是 $k$ 连通的.

Lemma 若图G含有 $2$ 个完全独立生成树，则图 $G$ 是 $2$ 连通的.

图的爪（Claw）

Define 对于图 $G$ ，一个生成子图 $H$ 同构于 $K_{1,3}$ ，则称为图 $G$ 的爪. 图 $G$ 称为无爪图如果它不包含爪.

Define $G$ 是无爪图当且仅当对任意的 $x \in V(G)$，$a(N_G( x ) ) \leq 2$ ，其中 $ a(N_G( x ) )$ 表示 $N_G ( x )$ 的独立数.

$P_k - free$ 和 $K_{1,3} - free$

Define 若图 $G$ 没同构于长度为 $3$ 的路径的诱导子图，则图 $G$ 是 $P_4$-Free Graph.

Define 若$G$ 含不有诱导的 $K_{1.3}$ ，则称 $ G$ 是 $K_{1,3} - free$.

$K_{1,3} - free$ 和 $P_5 - free$ 的图中含有两个CISTs

目标是找到一个CIST划分.

$2$ 连通

设图 $G$ 是 $K_{1,3} - free$ 和 $P_5 - free$ 的，则若图 $G$ 要包含两个CISTs，则 $G$ 必须是 $2$ 连通的.