树

无向树

无向树：一个连通无回路的无向图

森林：每个连通分支都是树的无向图

树叶v：

d

(

v

)

=

1

d(v)=1

d(v)=1

分支点v：

d

(

v

)

≥

2

d(v)\ge2

d(v)≥2

平凡树：平凡图，既无树叶，也无分支点

六个等价定义

G是树（连通无回路）

⇔

\Harr

⇔ G中任二顶点之间存在唯一路径

⇔

\Harr

⇔ G中无圈且

m

=

n

−

1

m=n-1

m=n−1

⇔

\Harr

⇔ G连通且

m

=

n

−

1

m=n-1

m=n−1

⇔

\Harr

⇔ G连通且每条边均为桥

⇔

\Harr

⇔ G无圈，但在任二不同顶点之间增加新边，所得图含唯一的一个 圈

无向树的性质

定理9.2：任一n阶非平凡树至少有两片树叶

生成树

生成树T：T是G的生成子图，且T为树 (T与G顶点相同)

树枝：生成树的边

弦：G中的边但不是树的边

余树（补）：G[E(G)-E(T)]

注意余数不一定是树

生成数的存在性定理

定理9.3：无向图G具有生成树当且仅当G是连通的

注意：连通图的生成树不唯一

基本回路 割集

基本回路：加弦，则生成树中有唯一的圈，该弦对应的圈称为基本回路

共有m-n+1条弦，则每条弦对应了一个基本回路，所有的基本回路的集合叫做基本回路系统

m-n+1为圈秩

ξ

(

G

)

\xi(G)

ξ(G)

基本割集：取生成树的某一条树枝，该树枝和其他部分弦构成图G的割集，则共有n-1条树枝，对应n-1个基本割集构成的集合叫做基本割集系统，n-1为G的割集秩，记为

η

(

G

)

\eta(G)

η(G)

G的生成树的个数$\tau (G)$

定理9.6：G是n阶无向连通标定图，则对于G的任意非环边有

η

(

G

)

=

η

(

G

−

e

)

+

η

(

G

收

缩

e

)

\eta(G)=\eta(G-e)+\eta(G 收缩e)

η(G)=η(G−e)+η(G收缩e)

定理9.7：

η

(

K

n

)

=

n

n

−

2

(

n

≥

2

)

\eta(K_n)=n^{n-2}(n\ge2)

η(Kn​)=nn−2(n≥2)

环路空间 断集空间

环路：G中圈或若干个边不重的圈的并

定理9.11：设G为 无向连通图，T是G的任意一棵生成树，则G中任一回路或为T的基本回路或为若干个基本回路的环合

定理9.12：设G是n阶m条边的无向连通图，则

C

环

C_环

C环​是

Ω

\varOmega

Ω的m-n+1维的子空间

环路空间：对基本回路不断作对称差运算

断集：G图中的两部分点之间的边

注意：割集是断集，断集不一定是割集（不满足极小性）

定理9.16：设G为无向连通图，T是G的一棵生成树，则G中任一断集为T的基本割集或为若干个基本割集的对称差

定理9.17：G是n阶m条边的无向连通图，则

S

断

S_断

S断​为

Ω

\varOmega

Ω的n-1维子空间

根树

根数: 只有一个顶点入度为0，其余顶点入度为1

层高：从树根到点v的路径长度

树高：顶点的最大层数

家族树