欢迎来到天天文库
浏览记录
ID:44789409
大小:12.21 MB
页数:38页
时间:2019-10-29
《离散数学 第15章 欧拉图与哈密顿图》由会员上传分享,免费在线阅读,更多相关内容在学术论文-天天文库。
1、第十五章欧拉图与哈密顿图第一节欧拉图PLAY第二节哈密顿图Hamilton图的一个应用(习题8.2#6)7位客人入席,A只会讲英语,B会讲英,汉语,C会讲英,意大利,俄语,D会讲日,汉语,E会讲德,意大利语,F会讲法,日,俄语,G会讲法,德语.能否安排圆桌席位使每位客人与其左右邻不用翻译便可交谈?BCDEFG建立无向图模型:结点为客人;会共同语言的2结点相邻接.则问题归结为求此图的一条Hamilton回路.不难验证,此图有一条Hamilton回路是:(A,B,D,F,G,E,C,A).按此回路安排席位可满足要求.思考问题:此图有E
2、uler回路或路径吗?若有,能否用来解决此问题?A英英法德俄意日汉第三节最短路问题与货郎担问题第十五章习题课解最短的路为ABCDA,距离为36公里,其余两条各为多少?PLAY
此文档下载收益归作者所有