欢迎来到天天文库
浏览记录
ID：23970922
大小：590.01 KB
页数：7页
时间：2018-11-12
《图论 王树禾 答案.pdf》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、图论第一次作业Bybyh1.1举出两个可以化成图论模型的实际问题略1.2证明
2、E(G)
3、,其中G是单图2证明：（思路）根据单图无环无重边的特点，所以
4、E(G)
5、最大的情形为任意两个顶点间有一条边相连，即极端情况为。2•1.4画出不同构的一切四顶单图•0条边：1条边：•2条边：3条边：•4条边：5条边：•6条边：1.10G≅?当且仅当存在可逆映射?:??→??，使得??∈??⇔????∈??，其中?和?是单图。（证明充分性和必要性）•必要性•若?≅?，由定义可得，存在可逆映射?:??→???:??→?(
6、?)当且仅当???=??时，????=???(?)，所以??∈??⇒????∈??•充分性•定义?:??→?(?)，使得??∈??和????∈?(?)一一对应，于是?可逆，且???=??的充要条件是????=????，得?≅?11.12求证(a)????=??，(b)?是完全二分图，则??≤??2,4•(a)对于???，将顶集分为?和?，使得?∪?=????，?∩?=,,∅，?=?，?=?，对于?中的每一顶点，都和?中所有顶点相连，所以????=??,•(b)设?的顶划分为?,?，?=?,?=?−?，则??≤2?•????-?=?
7、−??≤,4•证明：•(a)第一个序列考虑度数7,第二个序列考虑6,6,1•(b)将顶点v分成两部分v’和v’’•v’={v
8、v=vi,1≤i≤k},•v’’={v
9、v=vi,k10、dH(v)
10、dH(v)
此文档下载收益归作者所有
