欧拉图和哈密尔顿图.ppt

该【欧拉图和哈密尔顿图 】是由【fanluqian】上传分享，文档一共【16】页，该文档可以免费在线阅读，需要了解更多关于【欧拉图和哈密尔顿图 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。第二节 图的连通性
单击此处添加副标题
通路和回路
无向图的连通性
有向图的连通性
欧拉图
哈密顿图
通路和回路
回路：在点边序列v0e1v1e2…envn中，当v0=vn时称此通路为回路。
通路： G中前后相互关联的点边交替序列w=v0e1v1e2…envn称为连接v0到vn的通路。 W中边的数目K称为通路W的长。
可达的：在图G中，结点u和结点v之间存在一条路，则称结点u到结点v是可达的。
无向图的连通性
连通：在无向图G中，结点u和结点v之间存在一条路，则称结点u与结点v是连通的。约定：任一结点与自身总是连通的。
连通图：若图G中，任意两个结点均连通，则称G是连通图，否则称非连通图。对非连通图可分成几个无公共结点的连通分支。无向图中结点间的连通关系是等价关系。
图是连通的判定法则：从图中任意一结点出发，通过某些边一定能到达其它任意一结点，则称图是连通的。
练习1：连通图的判定
01
(1)
02
(2)
03
(3)
04
(4)
指出下列各图是否连通
欧拉图
欧拉回路：在图G中存在一条回路，经过图G中每条边一次且仅一次。（能一笔画）
欧拉图：具有欧拉回路的图。
设G=<V，E>是连通无向图
欧拉通路：在图G中存在一条通路，经过图G中每条边一次且仅一次。
欧拉图的判定定理
定理7-4 无向图G=<V，E>具有欧拉回路，即是欧拉图的充分必要条件是这个图是连通的，并且图G中所有结点的度数都是偶数，即都与偶数条边相连。
定理7-5 无向图G=<V，E>具有欧拉通路的充分必要条件是图G是连通的，并且图G中恰有两个度数是奇数的结点或者没有度数是奇数的结点。
1
2
指出下列各图哪些是欧拉回路？哪些是欧拉通路？
（2）
（1）
(3)
(4)
(5)
(6)
(7)
练习3：欧拉回路的判定
。
b
d
a
c
。
。
。
。
。
。
。
。
。
e
d
c
b
a
。
。
。
。
。
f
d
e
。
c
b
a
a、b、c、d
都为奇结点，无欧拉通路与欧拉回路
a、c为奇结点，
无欧拉回路
有欧拉通路
全部结点为偶结点，
有欧拉回路
有欧拉通路
。
。
。
。
。
。
a
b
c
d
e
f
a、b、c、e
都为奇结点，
无欧拉通路
与欧拉回路
。
。
。
。
。
a
b
c
d
e
f
全部结点为
偶结点，
有欧拉回路
有欧拉通路
例7-7
l
k
j
i
h
g
f
e
d
c
b
a
全部结点为偶结点，故有欧拉回路，即所求投递线路，
例如(abcgebdfhdeihkiglkjfa)
此投递线路即一笔画线路。
例7-8 如图街道，是否存在一条投递线路使邮递员从邮局a出发通过所有街到一次在回到邮局a?
一笔画问题：就是判断一个图形能否一笔画成,实质上就是判断图形是否存在欧拉通路和欧拉回路的问题。
一笔画的判定定理：⑴ 如果图中的每个结点都与偶数条边相连，则可以任取一点做始点，一笔画完，回到始点；⑵ 如果图中只有两个顶点与奇数条边相连，则选择这两个顶点中的一个做始点，一笔画完，终点为另一个与奇数条边相连的结点。