特殊图(10.5).ppt

11.2 欧拉图 11.2.1 欧拉图的引入与定义 例11.2.1判断下面的6个图中，是否是欧拉图？是否存在欧拉通路？ 11.2.2-4 欧拉图的判定及应用 定理11.2.1 （含推论11.2.1） （1）无向图G = V, E是欧拉图，当且仅当G是连通的，且仅有零个奇度数结点。 （2）无向图G = V, E有欧拉通路但不是欧拉图，当且仅当G是连通的，并且恰有两个奇度数结点。（两个奇度数结点必是G中每条欧拉通路的端点） 定理11.2.2 有向图G具有一条欧拉通路，当且仅当G是连通的，且除了两个结点以外，其余结点的入度等于出度，而这两个例外的结点中，一个结点的入度比出度大1，另一个结点的出度比入度大1。 推论11.2.2 有向图G具有一条欧拉回路，当且仅当G是连通的，且所有结点的入度等于出度。 定义11.2.2 设G = V, E，e∈E，如果 p(G-e)＞p(G) 称e为G的桥(Bridge)或割边(Cut edge)。 显然，所有的悬挂边都是桥。 例 例11.2.3 图中的三个图能否一笔画？为什么？ 例11.2.4 蚂蚁比赛问题 甲、乙两只蚂蚁分别位于图的结点A、B处，并设图中的边长度相等。甲、乙进行比赛：从它们所在的结点出发，走过图中所有边最后到达结点C处。如果它们的速度相同，问谁先到达目的地？ 11.3 哈密顿图 11.2.1 哈密顿图的引入与定义 例：对下面的图 11.3.2 哈密顿图的判定 定理11.3.1 设无向图G = V, E是哈密顿图，V1是V的任意非空子集，则 p(G-V1) ≤ |V1| 其中p(G-V1)是从G中删除V1后所得到图的连通分支数。 推论11.3.1设无向图G = V, E中存在哈密顿通路，则对V的任意非空子集V1，都有 p(G-V1) ≤ |V1| + 1 例11.3.2 证明图中不存在哈密顿回路。 例 设G = V, E是具有n个结点的简单无向图。如果对任意两个不相邻的结点u, v∈V，均有 deg(u)+deg(v)≥n-1 则G是连通的。 证明 用反证法：假设G有两个或更多连通分支。设一个连通分支有n1个结点，另一个连通分支有n2个结点。这二个连通分支中分别有两个结点v1、v2。显然，deg(v1)≤n1-1，deg(v2)≤n2-1。从而 deg(v1)+deg(v2)≤n1+n2-2 ≤n-2 与已知矛盾，故G是连通的。 定理11.3.2 设G = V, E是具有n个结点的简单无向图。如果对任意两个不相邻的结点u, v∈V，均有 deg(u)+deg(v)≥n-1 则G中存在哈密顿通路。 推论11.3.2 设G = V, E是具有n个结点的简单无向图。如果对任意两个不相邻的结点u, v∈V，均有 deg(u)+deg(v)≥n 则G中存在哈密顿回路。 例11.3.3 某地有5个风景点，若每个风景点均有2条道路与其他点相通。问游人可否经过每个风景点恰好一次而游完这5处？ 解 将5个风景点看成是有5个结点的无向图，两风景点间的道路看成是无向图的边，因为每处均有两条道路与其他结点相通，故每个结点的度数均为2，从而任意两个不相邻的结点的度数之和等于4，正好为总结点数减1。故此图中存在一条哈密顿通路，因此游人可以经过每个风景点恰好一次而游完这5处。 例11.3.4 判断下图是否存在哈密顿回路。 例11.3.5 证明下图没有哈密顿通路。 定理11.3.3 设G = V, E是有n(n≥2)个结点的一些简单有向图。如果忽略G中边的方向所得的无向图中含生成子图Kn，则有向图G中存在哈密顿通路。 11.3.4 哈密顿图的应用 1、巡回售货员问题简介 例11.3.6 2、中国邮路问题 一个邮递员送信，要走完他负责投递的全部街道，完成任务后回到邮局，应按怎样的路线走，他所走的路程才会最短呢？ 如果将这个问题抽象成图论的语言，就是给定一个连通图，连通图的每条边的权值为对应的街道的长度(距离)，要在图中求一回路，使得回路的总权值最小。 中国邮路问题 若图为欧拉图，只要求出图中的一条欧拉回路即可。否则，邮递员要完成任务就得在某些街道上重复走若干次。 如果重复走一次，就加一条平行边，于是原来对应的图就变成了多重图。只是要求加进的平行边的总权值最小就行了。 问题就转化为：在一个有奇度数结点的赋权连通图中，增加一些平行边，使得新图不含奇度数结点，并且增加的边的总权值最小。 解决问题的步骤 要解决上述问题，应分下面两个大步骤。 首先，增加一些边，使得新图无奇度数结点，我们称这一步为可行方案(Feasibl