《图论 王树禾 答案》由会员分享，可在线阅读，更多相关《图论 王树禾 答案（7页珍藏版）》请在金锄头文库上搜索。
1、图论第一次作业 By byh |E(G)|, 2 |E(G)| 2 G 1.1 举出两个可以化成图论模型的实际问题 略 1.2 证明其中 是单图 证明：（思路）根据单图无环无重边的特点，所以 最大的情形为任意两个顶点间有一条边相连，即极 端情况为。 1.4 画出不同构的一切四顶单图 0条边：1条边： 2条边：3条边： 4条边：5条边： 6条边： 1.10G 当且仅当存在可逆映射: ，使得 ，其中和是单图。（证明充分性和必要性） 必要性 若 ，由定义可得，存在可逆映射: : () 当且仅当 = 时， = ()，所以 充分性 定义: ()，使得 和 ()一一对应，于 是可逆，且 = 的充要条件是
2、= ，得 1.12求证(a) , = ，(b)是完全二分图，则 1 4 2 (a)对于, ，将顶集分为和，使得 = , ， = ， = ， = ，对于中的每一顶点，都和中所有顶点 相连，所以 , = (b)设的顶划分为,， = , = ，则 , - = 2 4 证明： (a)第一个序列考虑度数7,第二个序列考虑6,6,1 (b)将顶点v分成两部分v和v v = v|v = vi, 1 i k, v = v|v = vi, k i n 以v点为顶的原图的导出子图度数之和小于 然后考虑剩下的点贡献给这k个点的度数之和最大可能为 1.37：证明无环图含二分生成子图，使得 1 2 对每 个 ()成立。 证明： 任取X, Y满足X UY = V(G)， X Y = ，且令X,Y中的顶两两不相邻，所得的 图是H且是二分子图，令H是G边数最多的二分生成子图，若存在v V(G)， 使得dH(v) dG(v)，不妨设v X，则将v所连的边取消，换成dG(v) - dH(v) 条边，且将v加入Y中，于是H的边数增加了dG(v) - 2dH(v)条，与H边数最多 矛盾，故原命题成立。 2 1
