当前位置：文档之家 › 欧拉回路的判定_设计文档

欧拉回路的判定_设计文档

  • 格式：doc
  • 大小：209.07 KB
  • 文档页数：36

I 软件设计文档 II 文档管理信息表 项目名称 欧拉回路判定 版本 内容 编写代码 关键字 欧拉回路 参考文档 数据结构课本（C语言版） 创建时间 创建人 最新发布日期

文档变更纪录 日期 更改内容 2012.07.06 判断函数中是否存在欧拉回路的函数编写 深度优先搜索、建栈、出栈代码的编写 图的建立和邻接表存储结果的建立的代码的编写 2012.07.09 欧拉回路的判定函数的优化

对已经编写的程序进行相应的注释和修改 主要修改邻接表的创建工作！核心是数据部分

2012.07.10 对邻接表的建立函数做更近一步的修改，便于后面的操作 重新修改文件，利于组内对代码的调试和使用修改深度优先搜索函数 进行了文件的导入部分的函数的修改 2012.07.11 对欧拉回路的判断函数进行修改

对深度优先搜索函数进行修改和完善 对邻接表的建立函数做进一步的修改

2012.07.12 在建立图的函数中加入混合图的建立部分。 对栈的相关程序做了修改，调整了栈的逆置和输出。更正了DFSTraverse函数并成功输出了欧拉回路的路径和权值。 在建立图的函数中加入有向图的建立部分 2012.07.13 对欧拉回路的判定函数进行修改和完善

对深度优先搜索的函数进行修改和完善 对建立图的数据进行修改 2012.07.14 对有向图的欧拉回路进行修改

对深度优先搜索函数和showstack函数做了适当调整。 修改实习文档 2012.07.16 多有向图的欧拉回路进行改进

校对并精简了我们的代码，确认了文件和函数 修改了文档，对代码进行注释 III

文档主要评审意见 产品组 评审人员 日期 意见

QA组 评审人员 日期 意见 IV

目 录 1 开发规划 .......................................................................................................................................... 1 1.1 编写目的与范围 ..................................................................................................................... 1 1.2 开发人员 ................................................................................................................................. 1 1.3 开发计划 ................................................................................................................................. 1 1.4 开发环境和工具 ..................................................................................................................... 1 1.5 开发规范 ............................................................................................... 错误！未定义书签。

2 总体设计 .......................................................................................................................................... 2 2.1 概念术语描述 ......................................................................................................................... 2 2.2 基本设计描述 ......................................................................................................................... 2 2.2.1 系统总体逻辑结构图 ................................................................... 错误！未定义书签。 2.2.2 系统部署结构图 ........................................................................... 错误！未定义书签。 2.3 主要界面流程描述 ............................................................................... 错误！未定义书签。 2.3.1 功能1界面流程 ........................................................................... 错误！未定义书签。 2.3.2 功能2界面流程 ........................................................................... 错误！未定义书签。 2.4 模块列表 ................................................................................................................................. 2

3 数据结构及说明 .............................................................................................................................. 3 3.1 全局常量、变量及数据结构.................................................................................................. 9 3.2 重要局部变量及数据结构 ..................................................................................................... 9

4 接口规范 ........................................................................................................ 错误！未定义书签。 4.1 ......................................................................................................................... 15 4.1.1 Interface1 ...................................................................................... 错误！未定义书签。 4.1.2 Interface2 ...................................................................................... 错误！未定义书签。 4.2 ......................................................................................................................... 15 4.3 ......................................................................................................................... 15

5 模块设计 ........................................................................................................................................ 16 5.1 MODULE1设计 ...................................................................................................................... 16 5.2 MODULE2设计 ...................................................................................... 错误！未定义书签。

6 附录................................................................................................................................................ 32 6.1 参考资料 ............................................................................................................................... 32 6.2 附加文档 ............................................................................................... 错误！未定义书签。

合集下载

欧拉路径——精选推荐

欧拉路径——精选推荐

欧拉路径貌似很多博客都喜欢⽤⼀笔画来引⼊欧拉路径，但像您这样的强者时⽆需那些繁琐的东西，我们直接进⼊正题。

定义：图中经过所有边恰好⼀次的路径叫做欧拉路径。

如果起点和终点⼀样，那它就是欧拉回路。

判定：判定当前图中是否存在欧拉路径其实⽐寻找更⿇烦显然，欧拉回路也是欧拉路径，但为了⽅便区分，下⽂判定中的欧拉路径特指起点和终点不同。

判定⽅法：⾸先，当且仅当这张图将有向边视为⽆向边时联通。

1. 有向图欧拉路径：图中恰好存在⼀个点（起点）出度⽐⼊度多1，恰好⼀个点（终点）⼊度⽐出度多1，剩下所有点⼊度等于出度。

2. 有向图欧拉回路：图中所有点⼊度等于出度（任⼀点都可以做起点和终点）。

3. ⽆向图欧拉路径：图中恰好有两个点的度数为奇数（起点和终点），其他所有点的度数为偶数。

4. ⽆向图欧拉回路：图中所有点的度数都为偶数（任⼀点都可以做起点和终点）。

寻找：算法⼀：Fluery 算法。

时间复杂度O(m2)，不常⽤。

算法⼆：Hierholzer 算法。

时间复杂度O(m)，常⽤。

只写 Hierholzer 算法，做法⾮常简单。

1. 从起点开始dfs，标记选了的边不能重复选，这⾥⽤类似Dinic的当前弧优化。

2. 当前点不存在出边时回退，并将当前点⼊栈P。

3. 当dfs结束时倒序输出栈P中的节点即可。

算法导论上似乎有该算法证明。

例题：题⽬保证联通，所以直接判断⼊度和出度即可。

要求字典序最⼩，那么每次都要选能到达的最⼩的点。

可以将边离线下来按v从⼤到⼩排序，然后依次插⼊到链式前向星⾥，这样可以保证每次选到的都是最⼩的。

当前弧优化不加复杂度就假了。

code:#include<bits/stdc++.h>using namespace std;#define int long long#define in read()inline int read(){int p=0,f=1;char c=getchar();while(c>'9'||c<'0'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9'){p=p*10+c-'0';c=getchar();}return p*f;}const int N=1e5+5;const int M=2e5+5;int n,m;struct edge{int v,nxt;}e[M];inline void insert(int u,int v){e[++en].v=v;e[en].nxt=head[u];head[u]=en;}struct QWQ{int u,v;}E[M];inline bool cmp(QWQ a,QWQ b){return a.v>b.v;}int p[M],pn;void dfs(int u){for(int i=head[u];i;i=head[u]){int v=e[i].v;head[u]=e[i].nxt;dfs(v);}p[++pn]=u;}int flagin,flagout,flag;int ind[N],outd[N];int S=1;signed main(){n=in,m=in;for(int i=1;i<=m;i++)E[i].u=in,E[i].v=in,outd[E[i].u]++,ind[E[i].v]++;sort(E+1,E+1+m,cmp);for(int i=1;i<=m;i++)insert(E[i].u,E[i].v);for(int i=1;i<=n;i++){if(ind[i]!=outd[i])flag++;if(ind[i]==outd[i]+1)flagout++;if(ind[i]+1==outd[i])flagin++,S=i;}if(flag==0||(flag==2&&flagout==1&&flagin==1)){dfs(S);for(int i=pn;i>=1;i--)cout<<p[i]<<' ';}else cout<<"No";return 0;}练习：将每个字母视为点，单词视为边，就和上⾯差不多了，注意欧拉路径的起始点。

7-4 欧拉图与汉密尔顿图

7-4 欧拉图与汉密尔顿图


定理7-4.1的证明 的证明 定理
由于G是连通的，故必可到达另一个奇数度结点停止， 由于 是连通的，故必可到达另一个奇数度结点停止， 是连通的 得到一条迹L1： v0e1v1e2v2…eiviei+1…ekvk。若G中没 得到一条迹 中没 有奇数度结点，则从任意结点v 出发， 有奇数度结点，则从任意结点 0出发，用上述方法 必可回到v 得到一条闭迹L 必可回到 0，得到一条闭迹 1。 (2) 若L1经过 的所有边，则L1就是欧拉路。 经过G的所有边 的所有边， 就是欧拉路。 (3) 否则，在G中删掉 1中的边，得到G’，则G’中每个 否则， 中删掉L 中的边，得到 ， 中每个 中删掉 结点的度必为偶数。这是因为： 结点的度必为偶数。这是因为： 如果L 是不封闭的，则对每个非端点v 如果 1是不封闭的，则对每个非端点 i ， L1包含了 关联的所有边中的偶数条， 与vi关联的所有边中的偶数条，即deg’(vi )=deg(vi)中与v 关联的边数，因为deg(vi)为偶数，所以 为偶数， L1中与 i关联的边数，因为 为偶数 deg’(vi )为偶数，而deg’(v0)=deg(v0)-1为偶数， 为偶数， 为偶数， 为偶数 为偶数
定理7-4.1的推论 的推论 定理
无向图G具有一条欧拉回路 当且仅当G是连通 具有一条欧拉回路， 推论 无向图 具有一条欧拉回路，当且仅当 是连通 并且所有结点度数全为偶数。 的，并且所有结点度数全为偶数。 思考题： 思考题： 无向连通图含G有m个奇数度结点，问 个奇数度结点， 无向连通图含 有 个奇数度结点 变为欧拉图？ （1）至少加入多少条边才能使图 变为欧拉图？ ）至少加入多少条边才能使图G变为欧拉图 变为半欧拉图？ （2）至少加入多少条边才能使图 变为半欧拉图？ ）至少加入多少条边才能使图G变为半欧拉图
20-欧拉图

20-欧拉图

7
(1)m＝1时，由G的连通性及无奇度顶点可知，G只能是一个环， 由于G连通及无奇度顶点，所以δ(G)≥2. 无论G是否为简单图，
无向欧拉图的判别法
推论 无向图G是欧拉图当且仅当G连通且G是若干个边不重复 的圈之并. 例11.5 将下面欧拉图拆分为若干个边不重复的圈.
8
无向欧拉图的判别法
例11.6 将下面欧拉图拆分为若干个边不重复的圈.
20
Fleury算法（构造欧拉回路）
算法： （能不走桥不走桥） (1) 任取v0V(G)，令P0=v0. (2) 设Pi = v0e1v1e2…eivi 已经行遍，按下面方法从 E(G){e1,e2,…,ei }中选取ei+1：
(a) ei+1与vi 相关联；
(b) 除非无别的边可供行遍，否则ei+1不应该为 Gi = G{e1,e2,…,ei }中的桥.
用Fleury算法走出下图的一条欧拉回路.
19
有向欧拉图的判别法
定理11.5 有向图D是欧拉图当且仅当D是强连通的且每个顶 点的入度都等于出度. 本定理的证明类似于定理15.1. 定理11.6 有向图D是半欧拉图当且仅当D是单向连通的，且 D中恰有两个奇度顶点，其中一个出度比入度大1(始点)，另 一个入度比出度大1(终点)，而其余顶点入度与出度都相等. 本定理的证明类似于定理15.1.
9
构造欧拉路径实例
10
欧拉图的应用
七桥问题 A
B
D
C d(B)=5，d(A)= d (C)= d(D)=3， 七桥问题无解.
11
半欧拉图的判别法
定理11.4 无向图G是半欧拉图当且仅当G 连通且恰有两个奇度
顶点.
证 必要性显然. 充分性 设u,v为G 中的两个奇度顶点，令
论欧拉图_哈密顿图的判定及应用

论欧拉图_哈密顿图的判定及应用


所有顶点中，选一个与 ｘ 最邻近的点，把连接 ｘ 与此点的边加到这条
路 上 。 重 复 这 一 步 ，直 到 完 全 图 中 所 有 顶 点 都 包 含 在 路 中 。
步骤 ２ 把起始点和最后加入的顶点间的边放入，得到回路。
［３］
参考文献
例 ２ 在下图中以点 ａ 为起点，根据最邻近算法逐点构造出一条哈密 ［１ ］马叔良、顾豫；离散数学；电子工业出版社；１９９７
点以及这些点所关联的 边 后 得 到 的 子 图 ，则 ｗ（Ｇ－ Ｓ）≤ ∣ Ｓ｜ 成 立 。 其
中 ｗ（Ｇ－ Ｓ）是 Ｇ－ Ｓ 中 连 通 分 支 数 。 ［１］
定理 ４ 是哈密顿图的必要条件。用它可以证明某些图不是哈密
顿图。
图１
图２
２ 、用 定 理 来 判 定
定理 １ 一个无向连通图是欧拉图的充分必要条件是图中各点
用图形可描述现实世界中许多状态变化。图形表达事物是现
２ 、用 定 理 来 判 定
代 科 学 技 术 中 的 一 种 重 要 手 段 。 图 形 不 仅 形 象 直 观 ，而 且 可 以 结 合
定理 ３ 设图 Ｇ 是具有 ｎ 个顶点的无向连通图，如果 Ｇ 中任意
数据，可以数形结合便于计算。因此图论内容是相当现实和必需的， 两个不同顶点的度数之和大 于 等 于 ｎ，则 Ｇ 具 有 哈 密 顿 回 路 ，即 Ｇ
邮 件 时 ，每 次 要 走 遍 负 责 投 递 范 围 内 的 各 条 街 道 ，然 后 再 回 到 邮 局 ，
他 应 该 按 什 么 样 的 路 线 走 ，使 所 走 的 路 程 最 短 ？ 这 就 是 中 国 邮 路 问
题 。 如 果 将 投 递 地 点 用 点 来 表 示 ，邮 递 员 可 供 选 择 的 路 线 用 边 来 表