证明 由于G为k正则偶图,所以,k V1 =m = k V2 V1 = V2 。 12.证明:若δ≥2,则G包含圈。
证明 只就连通图证明即可。设V(G)={v1,v2,…,vn},对于G中的路v1v2…vk,若vk与v1邻接,则构成一个圈。若vi1vi2…vin是一条路,由于 2,因此,对vin,存在点vik与之邻接,则vik vinvik构成一个圈 。
17.证明:若G不连通,则连通。
证明 对 u,v V(G),若u与v属于G的不同连通分支,显然u与v在G中连通;若u与v属于g的同一连通分支,设w为G的另一个连通分支中的一个顶点,则u与w,v与w分别在G中连通,因此,u与v在G中连通。
_
_
__
习题2
证明:每棵恰有两个1度顶点的树均是路。
证明:设树T为任意一个恰有两个1度顶点的树,则T是连通的,且无圈,令V1
、V2 为度为1的顶点,由于其他的顶点度数均为0或者2,且T中无圈,则从V1到V2 有且只有一条连通路。所以,每棵恰有两个1度顶点的树均是路。得证。
证明:正整数序列(d1,d2,...,dn)是一棵树的度序列当且仅当 di 2(n 1)。
i 1n
证明:设正整数序列(d1,d2,...,dn)是一棵树T的度序列,则满足 di 2E,E
i 1
n
为T的边数,又有边数和顶点的关系n E 1,所以 di 2(n 1)
i 1
n
证明:若e是Kn的边,则 (Kn e) (n 2)nn 3。
若e为Kn的一条边,由Kn中的边的对称性以及每棵生成树的边数为n-1,Kn的所有生成树的总边数为:(n 1)nn 2,所以,每条边所对应的生成树的棵数
(n 1)nn 2
2nn 3,所以,K n - e 对应的生成树的棵数为: 为:
n(n 1)2
(Kn e) nn 2 2nn 3 (n 2)nn 3
Kruskal算法能否用来求:
图论及其应用1-3章习题答案(电子科大)_计算机软件及应用_IT/计算机_专业资料...(2)假设 e 为 T 中的一条边,根据(1)得 T +e 中仍不含 G 的极小割...
图论及其应用答案(电子科大版)第2章习题二: ? 度的。 证明设 是非平凡树 T...? 16.Kruskal 算法能否用来求: (1)赋权连通图中的最大权的树? (2)赋权图...
3页 1下载券 图论及其应用1-3章习题答... 4页 2下载券 电子科技大学国家...11.证明:序列(7,6,5,4,3,3,2)和(6,6,5,4,3,3,1)不是图序列。 ...
? 价: (1) (2) 个圈上; (3) G 无环且任意三个不同点都位于同一条... 成都电子科大2007年春博... 15页 4下载券 图论及其应用1-3章习题答... ...
2004图论复习题答案 4页 1下载券 图论及其应用第三章答案... 3页 1下载券图论及其应用第2章答案(电子...
习题一: ? v2 v7 v8 v3 v9 v4 (a) 4. 证明下面两图同构。 v 1 ...? 11.证明:序列(7,6,5,4,3,3,2)和(6,6,5,4,3,3,1) 不是图序列...
图论及其应用 第一章答案 13页 5财富值 第十一章图论及其应用初步 7页 免费... 图论及其应用,电子科大图论及其应用,电子科大隐藏>> 1 0.5 n 0 ?0.5 ?...
电子科大,图论及其应用电子科技大学数学科学学院王也洲...例 v1 v3 v4 图中 d (v1) = 5 d (v3)...解决得不好;(3) 构造问 题(如何画出图序列对应...
电子科大图论ppt1_工学_高等教育_教育专区。1 0.5 n 0 ?0.5 ?1 2 1.5 t 1 0.5 0 0 0.2 0.4 x 0.8 0.6 1 图论及其应用任课教师: 任课...
电子科大,图论及其应用第三章 图的连通度考察: u ...G1 G2 G3 G4 (2) λ(G1) =1(非平凡树的...G是完全图,各边的权均为1的特殊情况,问 题是有...
热门文档