资源描述：
《图的矩阵表示、欧拉图与哈密顿图》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、离散数学·习题课DiscreteMathematics第十二次：图论基础(2)、欧拉图与哈密顿图南京大学计算机科学与技术系2010年6月1日前情提要有向图的连通性：弱连通图：基图是连通图的有向图；强连通图：对有向图?=?,?,∀??,??∈?⇒??↔??。单向连通图：对有向图?=?,?,∀??,??∈?⇒??→??∨??→??。课程内容回顾2前情提要有向图的连通性（续）：强连通图判定定理：对有向图?=?,?,?=?1,?2,⋯,??，?是强连通图⇔?中存在经过每个顶点至少一次的回路。单向连通图判定定理：对?阶有向图，?是单向连通图⇔?中存在
2、经过每个顶点至少一次的通路。扩大路径证明法。课程内容回顾3前情提要二部图：无向图?=?,?，若能将?分为不交的?1和?2，使得?中每条边的两个端点均分属?1和?2，则称?为二部图（bipartitegraph），记为?1,?2,?。完全二部图：?为简单二部图，?1中每个顶点均与?2中所有顶点相邻，记为??1,
3、?2
4、。课程内容回顾4前情提要二部图的判定定理：无向图?=?,?是二部图⇔?中不存在奇数长度回路。欧拉图含有欧拉回路（经过图中所有边一次且仅一次而行遍所有顶点的回路）的图，平凡图是欧拉图；半欧拉图：含有欧拉通路但不含欧拉回路的图。
5、课程内容回顾5前情提要欧拉图的判定定理：无向图是欧拉图当且仅当其为连通图且不含奇度顶点；无向图是半欧拉图当且仅当其为连通图且恰含2个奇度顶点；有向图是欧拉图当且仅当其为强连通图且每个顶点的入度与出度相等；课程内容回顾6前情提要欧拉图的判定定理（续）：有向图是半欧拉图当且仅当其为单向连通图且恰含2个奇度顶点，其中一个入度比出度大1，另一个出度比入度大1，其余每个顶点的入度与出度相等；?是非平凡欧拉图当且仅当?为连通的且为若干不重的圈的并图。求欧拉回路的Fleury算法。课程内容回顾7前情提要哈密顿图含有哈密顿回路（经过图中所有顶点一次且
6、仅一次的回路）的图，平凡图是哈密顿图；半哈密顿图：含哈密顿通路但不含欧拉回路的图。课程内容回顾8前情提要哈密顿图的性质或判定定理（充分或必要条件）哈密顿图成立的简单充分必要条件尚未找到。无向图?=?,?是哈密顿图，则：∀?1(?1⊂?∧?1≠∅)⇒?(?−?1)≤
7、?1
8、。无向图?=?,?是半哈密顿图，则：∀?1(?1⊂?∧?1≠∅)⇒?(?−?1)≤
9、?1
10、+1。课程内容回顾9前情提要哈密顿图的性质或判定定理（续）若无向图中含有割点或桥，则其非哈密顿图。?是?(?≥3)阶无向简单图，若对于?中任意不相邻顶点??,??均有???+???≥
11、?，则?是哈密顿图。?是?阶无向简单图，若对于?中任意不相邻顶点??,??均有???+???≥?−1，则?中存在哈密顿通路。课程内容回顾10前情提要哈密顿图的性质或判定定理（续）?是?阶无向简单图，?,?是其中两个不相邻顶点，且??+??≥?，则?为哈密顿图当且仅当?∪(?,?)为哈密顿图（(?,?)是新加的边）。二阶及以上竞赛图具有哈密顿通路。货郎担问题（TSP）：求带权图中最短的哈密顿回路。TSP问题是一个典型的NP-Hard问题，动态规划求解的时间复杂度约为??22?。课程内容回顾11图论基本概念课堂练习1、证明：?阶简单二部图?的边数
12、不超过?2/4。（6分钟）证明：设?的边集为?，则?=*?1,?2+，故必有?1+?2=?。由于?是简单二部图，故对于?的任意无向边*?1,?2+，?1∈?1,?2∈?2（反之亦可）；故边数不超过?1×?2。由于顶点数2?1+?22均为正整数，故有：?≤?1×?2≤=?/4。由于2边的数目是整数，故命题得证。□图论基本概念课堂练习12图论基本概念课堂练习2、哥尼斯堡七桥问题中，至少再架几座桥有人就可以从陆地某点出发经过每一座桥一次且仅一次，最后返回到出发地点？（1分钟）答：至少再架2座桥即可。图论基本概念课堂练习13图论基本概念课堂练习3、证明：若?
13、为欧拉图，则?中无桥。（4分钟）证明：反设?中有桥，且?=(?,?)为桥，则?−?中必含2个连通分支?1和?2；因为?是欧拉图，故??(?)和??(?)皆为偶数，故去掉一边后??1(?)和??2(?)皆为奇数；注意到此时两连通分支中其它顶点度数皆为偶数，这与握手定理的推论矛盾。因此假设错误，?中没有桥。□图论基本概念课堂练习14图论基本概念课堂练习4、课本第304页第13题。（5分钟）证明：令?=?,?是2?阶简单无向图，其中?=??为去完成任务的人，?=*(?,?)
14、?,?∈?,?≠?且?和?有共同熟悉的任务+。根据题设，∀?,?∈?(??+??=2
15、?)，故??+??≥2?−1，根据哈密顿通路的存在条件，?中存在哈密顿通路。设?
