图论及其应用1-3章习题答案(电子科大)[共3页].docVIP

PAGE / NUMPAGES 习题一 （题14）：证明图1-28中的两图是同构的 图1-28 图1-28 证明 将图1-28的两图顶点标号为如下的(a)与(b)图 作映射f : f(vi)?ui (1? i ? 10) 容易证明,对?vivj?E((a)),有f(vivj)?uiuj?E((b)) (1? i ? 10, 1?j? 10 ) 由图的同构定义知,图1-27的两个图是同构的。 （题6）设G是具有m条边的n阶简单图。证明：m =当且仅当G是完全图。 证明 必要性 若G为非完全图,则? v?V(G),有d(v)? n-1 ? ? d(v) ? n(n-1) ? 2m?n(n-1) ? m ? n(n-1)/2=, 与已知矛盾！ 充分性 若G为完全图,则 2m=? d(v) =n(n-1) ? m= 。 （题9）证明：若k正则偶图具有二分类V= V1∪V2,则 | V1| = |V2|。 证明 由于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属于G的不同连通分支,显然u与v在中连通；若u与v属于g的同一连通分支,设w为G的另一个连通分支中的一个顶点,则u与w,v与w分别在中连通,因此,u与v在中连通。 习题二 证明：每棵恰有两个1度顶点的树均是路。 证明：设树T为任意一个恰有两个1度顶点的树,则T是连通的,且无圈,令V1 、V2 为度为1的顶点,由于其他的顶点度数均为0或者2,且T中无圈,则从V1到V2 有且只有一条连通路。所以,每棵恰有两个1度顶点的树均是路。得证。 证明：正整数序列是一棵树的度序列当且仅当。 证明：设正整数序列是一棵树T的度序列,则满足,E为T的边数,又有边数和顶点的关系,所以 证明：若e是的边,则。 若e为Kn的一条边,由Kn中的边的对称性以及每棵生成树的边数为n-1,Kn的所有生成树的总边数为：,所以,每条边所对应的生成树的棵数为：,所以,K n - e 对应的生成树的棵数为： Kruskal算法能否用来求： 赋权连通图中的最大权值的树？ 赋权图中的最小权的最大森林？如果可以,怎样实现？ 解：（1）不能,Kruskal算法得到的任何生成树一定是最小生成树。 （2）可以,步骤如下： 步骤一：选择边e1,是的尽可能小； 步骤二：若已选定边,则从选取,使 为无圈图 是满足a的尽可能小的权； 步骤三：当步骤二不能继续执行时停止； 习题三 3.设G是阶大于2的连通图,证明下列命题等价： （1）G是块 （2）G无环且任意一个点和任意一条边都位于同一个圈上； （3）G无环且任意三个不同点都位于同一条路上。 证明：（1）→（2）： QUOTE G是块,任取 QUOTE G的一点 QUOTE u,一边 QUOTE e,在 QUOTE e边插入一点 QUOTE v,使得 QUOTE e成为两条边,由此得到新图,显然 QUOTE 的是阶数大于3的块,由定理, QUOTE G中的u,v位于同一个圈上,于是 QUOTE QUOTE 中u与边 QUOTE e都位于同一个圈上。 →(3): 无环,且任意一点和任意一条边都位于同一个圈上,任取 QUOTE 的点u,边e,若 QUOTE 在 QUOTE 上,则三个不同点位于同一个闭路,即位于同一条路,如 QUOTE 不在 QUOTE 上,由定理, QUOTE 的两点在同一个闭路上,在 QUOTE 边插入一个点v,由此得到新图 QUOTE ,显然 QUOTE 的是阶数大于3的块,则两条边的三个不同点在同一条路上。 (3)→(1): QUOTE 连通,若 QUOTE 不是块,则 QUOTE 中存在着割点 QUOTE ,划分为不同的子集块 QUOTE , QUOTE , QUOTE , QUOTE 无环,,点 QUOTE 在每一条 QUOTE 的路上,则与已知矛盾, QUOTE 是块。 设H是连通图G的子图,举例说明：有可能k(H) k(G). 解：通常 QUOTE . eH整个图为 QUOTE ,割点 QUOTE 左边的图 QUOTE 为 QUOTE 的的子图, QUOTE QUOTE ,则 QUOTE . e H 设T是简单连通图G的生