三、树和割集

1、树

1.1 树的定义

\qquad 定义： 一个连通的无圈的图称为树。
\qquad 只有一个顶点的树叫做平凡树。
\qquad 树中度为1的节点称为叶子结点。
\qquad 推论1： 非平凡树中至少有两个叶子结点。
\qquad 推论2： 树是双图。
\qquad 定义： 一个无圈的图称为森林。

1.2 树的性质

\qquad 定理1： 设$G=(V,E)$是一个$(p,q)$图，则下列命题是等价的：

• $G$是树
• $G$中任意两个顶点之间有唯一的一条路
• $G$是连通的，且$p=q+1$
• $G$中无圈，且$p=q+1$
• $G$中无圈，$G$中任意两个不相邻的顶点之间加一条边，则得到一个有唯一圈的图
  \qquad 要证明上述定理成立，需要证明任意两个结论之间互为充分必要条件，则可以将5条结论围成一圈，依次证明前一条结论是后一条结论的充要条件即可。在证明第二条到第三条的结论时，可以使用数学归纳法进行证明。证明第三条到第四条结论，从第四条结论到第一条结论和从第五条结论到第一条结论时，可以使用反证法进行证明。

1.3 极小连通图

\qquad 定义： 去掉一条边就不连通的连通图叫做极小连通图。
\qquad 定理： $G$是树的充要条件为$G$是极小连通图。

1.4 树的中心

\qquad 偏心率： 给定一个树$G=(V,E)$，和任意一个$v\in V$，定义节点$v$的偏心率为 e ( v ) = m a x u ∈ V { d ( u , v ) } e(v)=max_{u \in V}\{d(u,v)\} e(v)=maxu∈V​{d(u,v)}。
\qquad 树的半径： 树中所有顶点的最小偏心率为树的半径， r ( G ) = m i n v ∈ V { e ( v ) } r(G)=min_{v \in V}\{e(v)\} r(G)=minv∈V​{e(v)}。
\qquad 树的中心： 树的中心表示为一个节点集合 H = { v ∣ v ∈ V , e ( v ) = r ( v ) } H=\{v|v \in V, e(v)=r(v)\} H={v∣v∈V,e(v)=r(v)}。

1.5 生成树

\qquad 给定一个图$G=(V,E)$, 若$G$的一个生成子图是树，则称其为$G$的生成树。
\qquad 图$G=(V,E)$生成树存在的充要条件：$G$是连通图。
\qquad 给定一个图$G=(V,E)$是一个$(p,q)$图，$G$中至多有$p^{p-2}$个生成树(上界)。

1.5.1 最小生成树

\qquad 对于一个图$G=(V,E)$中所有的生成树，其中权值最小的生成树叫做最小生成树，求最小生成树的两个算法如下：
\qquad Prime 算法随机从图中选择一个顶点加入到最小生成树树集合中，之后选择和最小生成树集合中已经存在的顶点相邻接的其他顶点中边权值最下的顶点添加到最小生成树集合中(在此过程中判断是否有圈存在，排除生成圈的顶点)，直到所有的顶点都检查完毕，其算法复杂度为$O(p^2)$。
\qquad Kryscal 算法： 将图中所有的边按照权值进行从小到大排序，依次向生成树集合中添加权值最小的边，每添加一条边需要判断是否有圈产生，跳过有圈生成的边，直到所有的边均检查完毕为止，算法复杂度为$O(q\ast logq)$。

2、 割点和桥

\qquad 割点定义： 给定一个图$G=(V,E)$，$v\in V$，假如$G-v$的分支数大于$G$的分支数，则称$v$为$G$的一个割点。
\qquad 每一个非平凡的图中至少有两个顶点不是割点(从最长路来证明)。哈密顿图中一定没有割点，从哈密顿图的定义来证明，哈密顿图中一定有哈密顿回路。
\qquad 定理1(割点的特征性质)： 给定一个图$G=(V,E)$，$v\in V$，则下述命题等价：

• $v$是割点
• $\exists u,v\in V,u\ne w$, $u$和$v$之间的所有的路均通过$v$.
• ∃ V / { v } \exist V /\ \{v\} ∃V/ {v}的一个划分 { U , W } \{U, W\} {U,W}，使得$\forall u\in U,\forall v\in V$，$u,v$之间的路均通过$v$

\qquad 桥定义： 给定一个图$G=(V,E)$，$x\in E$，假如$G-x$的分支数大于$G$的分支数，则称$x$为$G$的一个桥。
\qquad 定理1(桥的特征性质)： 给定一个图$G=(V,E)$，$x\in E$，则下述命题等价：

• $x$是桥
• $\exists u,v\in V,u\ne w$, $u$和$v$之间的所有的路均通过$x$.
• ∃ E / { x } \exist E /\ \{x\} ∃E/ {x}的一个划分 { U , W } \{U, W\} {U,W}，使得$\forall u\in U,\forall v\in V$，$u,v$之间的路均通过$x$
• $x$不在任何圈上

THE END