《图论及其应用1-3章习题答案.docx》由会员分享，可在线阅读，更多相关《图论及其应用1-3章习题答案.docx（4页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
习题一1. （题14）：证明图1-28中的两图是同构的图1-28证明 将图1-28的两图顶点标号为如下的(a)与(b)图作映射f : f(vi)ui (1 i 10)简洁证明，对vivjE(a),有f(vivj)=uiujE(b) (1 i 10, 1j 10 )由图的同构定义知，图1-27的两个图是同构的。2. （题6）设G是具有m条边的n阶简洁图。证明：m =当且仅当G是完全图。证明 必要性 若G为非完全图，则$ vV(G),有d(v) n-1 d(v) n(n-1) 2mn(n-1) m k(G).解：通常.eH整个图为，割点左边的图为的的子图， ，则.15、 设T是简洁连通图G的生成树，称为G的余树，图G的微小边割是指其任何真子集均不是边割的边割。证明：（1） 不含G的微小边割。（2） 包含G的唯一的微小边割，其中e为G的不在中的边。证明：（1）设含有G的微小边割S，则T中不含微小边割S，由于T是简洁连通图G的生成树，则T中必定含有一组微小割边，这与T中不含微小割边相冲突，则中不含G的微小边割。 （2）假设e为中的一条边，依据（1）得+e中仍不含G的微小割边，这与 包含G的唯一的微小边割相冲突，则e为G的不在中的边，得证。第 4 页