《离散数学》特殊图-1研究报告.ppt

第8章 一些特殊的图 ;8.1 二部图 ;二部图 ;二部图的判别法 ;匹配 ;匹配 (续);二部图中的匹配;二部图中的匹配 ;一个应用实例 ;上图是二部图，满足t条件（t＝2），存在V1到V2的完备匹配;8.2 欧拉图－－一笔画问题;哥尼斯堡七桥问题;欧拉图 ;一笔画问题;A;欧拉图(续);欧拉图的判别法 ;实例;中国邮路问题：;8.3 哈密顿图－点不重复 ;哈密顿周游世界问题;哈密顿图的定义;实例;无向哈密顿图的一个必要条件 ;理解：满足上述条件的土不一定是哈密顿图 如彼得森图，去掉一个点，连通分支数不发生变化，仍然为1，满足条件，但不是哈密顿图；;实例;无向哈密顿图的一个充分条件 ;哈密顿通路(回路)的存在性(续);由定理, 当n?3时, Kn均为哈密顿图. 判断某图是否为哈密顿图至今还是一个难题 定理8.8：设有向图D=V,E,|V|=n?2 如果所有的有向边均用无向边代替,所得无向图中含有生成子图kn ，则该有向图中存???哈密尔顿通路。 推论:|V|?3的有向(无向)完全图为哈密尔顿图。 ;哈密顿图与欧拉图;判断是否是哈密顿图的可行方法;判断是否是哈 密顿图的可行方法(续);应用实例;应用－货郎担问题：