9.树
1．画出所有7阶非同构的无向树？
1.解：
7阶无向树有6条边，所以7个顶点的度数之和是12。
7个顶点的度数由小到大只能是：
1.1 1 1 1 1 1 1 6(1种)
1.2 1 1 1 1 1 2 5(1种)
1.3 1 1 1 1 1 3 4(1种)
1.4 1 1 1 1 2 2 4(2种)
1.5 1 1 1 1 2 3 3(2种)
1.6 1 1 1 2 2 2 3(3种)
1.7 1 1 2 2 2 2 2(1种)
总计11种，图略。
2，无向树有9片树叶，3个3度顶点，其余顶点的度数均为4，问T中共有几个4度顶点？根
据T的度数列，你能画出多少棵非同构的无向树？
答：9*1+3*3+4*x=2*(9+3+x-1)=>9+9+4*x=22+2x =>2x=4=>x=2 共有2个4度顶点
T(1,1,1,1,1,1,1,1,1,3,3,3,4,4)
2.1 4-3-3-3-4 (1种)
2.1.1
4-3-3-3-4
2.2 4-3-3-4 (2种)
2.2.1
4-3-3-4
|
3
2.2.2
3
|
4-3-3-4
2.3 4-3-4 (4种)
2.3.1
4-3-4-3
|
3
2.3.2
3
|
4-3-4
|
3
2.3.3
3 3
| |
4-3-4
2.3.4
3 3
| |
4-3-4
2.4 4-4 (2种)
2.4.1
3
|
4-4-3
|
3
2.4.2
3 3
| |
4-4-3
合计9种。
3.一棵无向树T，有ni个 i度定点,i=2,3,..,k其余顶点都是树叶，问T 有几片树叶？
答： x+n2*2+n3*3+….=(x+n2+n3+….-1)*2
=>x=(n2*2+n3*3+…)-2*(n2+n3+…-1)
4.设T是k+1阶无向树，G为无向简单图，且δ(G) ≥k,证明G中存在与T同构的子图
证明：T中有k条边。从T上取任意一点vt1，vt1最多与k个点相连。
从G上取任意一点vg1，vg1至少与k个顶点相连。如果vt1连接有x个点
vt2, vt3, ..., vtx, vt(x+1) (1<=x<=k)；
寻找x个与vg1相连的点，vg2, vg3, ..., vgx, vg(x+1) (1<=x<=k)，
将G中这些点和连线作为G中与T同构的子图的一部分。
T上与vt1相连的任一点vt2，除vt1, vt3, ..., vtx, vt(x+1)外最多与k-x个点相连
(只有k条边，已经有x条边与vt1相连)；
G上与vg1相连的任一点vg2，除vg1, vg3, ..., vgx, vg(x+1)外最少与k-x个点相连
(d(vg2)>=k，不考虑与vg1, vg3, ..., vgx, vg(x+1)这x点的连接，vg2除
vg1, vg3, ..., vgx, vg(x+1)外最少与k-x个点相连)；
将G中这些点和连线作为G中与T同构的子图的一部分。
这样依次遍历下去，可以在G上得到T的同构子图。
即对于任意的T，G中都存在同构子图。
5.设T1,T2是无向树T的子图，并且都是树，令T3=G[E(T1)∩E(T2)],E(T1)∩E(T2)≠φ,证
明T3也是T的树
证明，显然也是无向连通图，且无回路，否则，与T1,T2是无向树矛盾
6.设G为n阶简单图，证明G或G中必含圈
证明：用红蓝着色问题，即可证明G或G中必含圈
7,已知n阶m条边的无向图G为k(k≥2)个连通分支的森林，证明m-k
证明：利用每个连通分支都是树，且利用定理，即可证明
8,设d1,d2,…dn是n个（n≥2）个正整数，已知 di的和=2n-2,证明存在一棵顶点为
d1,d2,..dn的无向树
证明：8.1 首先证明d1, d2, ..., dn中至少有2个为1，否则d1+d2
+...+dn>=2*n-1，
这与已知矛盾。
8.2 证明d1, d2, ..., dn中至少有1个>=2，否则d1+d2+...+dn<=n，这与已知
矛盾(n>=2)。
8.3 用数学归纳法，证明存在满足题中要求的树：
8.3.1 当n=2时，显然d1=1, d2=1。此时可以构成一棵树。
8.3.2 假设当n=k时，d1, d2, ..., dk可以构成一棵树。
8.3.3 当n=k+1时，d1, d2, ..., dk, d(k+1)中至少有1个=1，至少有1个>=1，
不妨假设d(k+1)=1, dk>=2。
此时d1, d2, ..., dk-1满足d1+d2+...+(dk-1) = 2*(k+1)-2-1-1 = 2*k-2。
根据8.3.2，d1, d2, ..., dk-1可以构成一棵树。将度数为dk-1的点和度数为
d(k+1)的点连接起来，可以构成一棵树。满足d1, d2, ..., dk, d(k+1)。
即当n=k+1时，d1, d2, ..., dk, d(k+1)可以构成一棵树。
综合8.3.1、8.3.2和8.3.3，存在满足题中要求的树。
9,无向连通标定图G如图9.13所示，求τ(G)，并画出全体不同的生成树！
答：根据例题，显然 τ(G)=3，
10,实边所示子图为图9.14所试图的一棵生成树T,求T对应的基本回路系统和基本割集系统
。
Ca=aegdj
Cb=bgdji
Cc=cdg
Cf=feg
Ch=hij
基本回路系统为{Ca, Cb, Cc, Cf, Ch}
Sd={a, b, c, d}
Se={a, e, f}
Sg={a, b, c, f, g}
Si={b, h, i}
Sj={a, b, h, j}
基本割集系统为{Sd, Se, Sg, Si, Sj}
11.设T为非平凡的无向树，△(G) ≥k，证明T至少有k片树叶
证明：设T中有n个顶点，若T中至多有s片树叶(s
2m=2n-2≥2(n-s-1)+k+s=>s≥k
这与s
12．设C为无向图G中的一个圈，e1,e2为C中的两条边,证明G中存在割集S,使得
e1,e2∈S
证明：设C所在的连通分支为G1,求G1的满足下述条件的一棵生成树T,使得回路C中的边a为
T中的弦(即形成T时删除a)，于是b是T的树枝，设树枝b对应的基本割集Sb,则Sb则为所求
。
事实上,Sb中必含弦a,因为b对应的基本割集中只含有一个树枝b,其余的元素均为弦，若弦
a不在Sb中，当从G1中删除Sb中各边后，对T来说，只删除它的一条树枝b,因而T分成两棵
树T1和T2,设V(T1)=V1,V(T2)=V2,=V-V1,，则a的端点一个在V1中，一个在V2中，通过a的
连接G1-Sb仍连通，这与Sb为G1的割集矛盾，因而a∈Sb于是Sb 与C有两条公共边a,和b
13.设T1和T2是连通图G的两棵生成树，边a在T1中，但不在T2中，证明存在只在T2中不在
T1中的边b,使得(T1-a)∪{b}和(T2-b)∪{a}都是G的生成树
证明：从T1中删除树枝a,得树T11和T12，令V1=V(T11),V2=V(T12),设
Sa={e|e的端点分别属于V1和V2}
显然 a∈Sa,易知Sa是G的割，并且是对应T1的树枝a的基本割集。
因为a不在T2中，所以a为T2的弦，设Ca为对应T2的弦a的基本回路，在Ca必存在T2的树枝
b 不在T1中并且在Sa，否则Ca上的T2的所有树枝均在T1
中或者均不在Sa中，若Ca上的T2的
所有树枝均在T1中，则Ca上的所有边均在T1中，这与树中无回路矛盾，又若Ca上T2中的所
有树枝都不在Sa中，则G-Sa还仍连通，这与Sa为G的割集矛盾，所以Ca上必存在不在T1中
而在Sa中的T2的树枝，设b为其中的一条，则(T1-a)∪{b}连通无回路，且为G的生成子图
，所以它是G的生成子树，同理(T2-b)∪{a}也是G的生成树
14,设Kn是n阶标定无向完全图，e是Kn中的一条边证明τ(Kn-e)=(n-2)*n^(n-3)
证明：
（谢谢 sea_air!!!!!!!!!!!!! sea_air得原作！sea_air本人说：还需整理！呵呵）
因为kn是n阶标定无向完全图，
所以 n>=3。
因而分情况讨论：
1）当n=3时，e为非环边，
因为 T(k3-e)=1, (3-2)3^(3-3)=1,
所以 等式成立；
2）当n>3时，e必为环边，
所以，为了方便，令V(kn-e)={1,2,3,......n},
不妨设vi，则与其相连的有n-1条边。若e为vi其中的一条边，则与vi 相连的边有n-2条边
；又由于，V(kn-e)中元素构造长为n-3的序列，显然可以构造出n^(n-3),对于 vi这个特
殊点而言，此处有n-2种可能性，所以其生成树的个数就为(n-2)n^(n-3).
15.16,环路空间和断集空间去年没考！所以在此略去!
17,证明：一棵有向树T是根树，当且仅当T中有且仅有一个顶点的入度为零
证明
17.1 根据根树的定义，如果T是根树，T中只有一个顶点的入度为0。
17.2 如果T中只有一个顶点的入度为0，证明T上其余点的入度均为1：
假设T上有n个点，那么T上有n-1条边。T上所有点的入度之和是n-1。
已知T上只有1个点的入度为0，那么其余n-1个点的入度>=1。
又已知其余n-1个点的入度之和是n-1，所以只能是其余n-1个点的入度都为1。
根据根树的定义，T为根树。
综合17.1和17.2，T是根树，当且仅当T中只有一个顶点的入度为0。
18.画出六阶所有非同构的根树！，图略！
19.设T是2 叉正则树，i是分支点数，I是各分支点数的层数和，证明 L=I+2i
如果树叶的层数是n的话，树叶有2^n个，L=n*2^n。
证明
分支点数i=2^n-1，其中层数为0的分支点有1个，层数为1的分支点有2个，...
层数为n-1的分支点有2^(n-1)个。
用数学归纳法，证明I=n*2^n-2*(2^n-1)
19.1 当n=1时，I=0，满足I=n*2^n-2*(2^n-1)；
19.2 假设当n=k时，I=k*2^k-2*(2^k-1)，满足I=n*2^n-2*(2^n-1)；
19.3 当n=k+1时，I=k*2^k-2*(2^k-1)+k*2^k
=2*k*2^k-2*(2^k-1)=k*2^(k+1)-2*(2^k-1)
=(k+1)*2^(k+1)-2^(k+1)-2*2^k+2
=(k+1)*2^(k+1)-2*(2^(k+1)-1)
满足I=n*2^n-2*(2^n-1)；
综合19.1、19.2和19.3，根据数学归纳法，I=n*2^n-2*(2^n-1)=L-2*i，
即L=I+2*i。
20.设T是 2叉正则树，有t片树叶，i个分支点，证明T的边数m=2t-2
证明
：边数有：m=(3(i-1)+2 +t)/2 =>2m=3i+t-1
m=t+i-1 =>2t+2i-2=3i+t-1=>t=i+1=>i=t-1
m=t+i-1=t+t-1-1=2t-2,得证
21．求算式((a+(b*c)*d)-e)/(f+g)+(h*i)*j 的波兰符号法和逆波兰符号法表示
波兰表达式为：+÷-+a**bcde+fg**hij
逆波兰表达式为：abc*d*+e-fg+÷hi*j*+