图的随机生成及欧拉(回)路的确定

欧拉图--欧拉通路离散学过欧拉图的⼀些知识今天遇到⼀个题，挺有趣的。

⾸先，欧拉图，是指能从任意⼀点，不重复经过所有边能回到起点的图便是欧拉图。

这个路也叫欧拉回路。

次之，欧拉通路，任意⼀点，不重复经过所有边，不回到起点。

这个路叫欧拉通路。

记得书上的分析是从出⼊度来分析的，对于⽆向图，⼀点的度即是该点连接的边数。

对于有向图，就分为出度和⼊度。

欧拉回路：⽆向图中，所有点都是偶度点，存在欧拉回路。

有向图中，所有点的出度等于⼊度，存在欧拉回路。

欧拉通路：⽆向图中，满⾜有且仅有0或1对奇度点，即存在欧拉通路（奇度点分别为起点和终点）。

有向图中，满⾜有且仅有0或1对点的出⼊度差值为1，即存在欧拉通路（⾃然，出度多的那个是起点，⼊度多的那个是终点）。

那么，对代码来说，这也很容易实现，但是但是但是！我wa了很多次错误点：1.⼤写字母的ascll码⽐⼩写字母ascll码⼤。

2.这题是欧拉通路，没注意奇度点的先后性，也就是，如果有奇度点，得从奇度点开始遍历，⽽不是直接从⼩到⼤找第⼀个有度的字母，也就是得遍历两次找起点。

3.有重复边的存在，不能简单矩阵存图。

4.这题有重复字母，a->a这种也有，遇到⼀组数据如下6aabbccabbccaaabbcca这组数据顺序遍历输出会编程aabbca，少⼀个c，这是bfs遍历的问题，也即存在最后连不起来的情况。

另外，对于dfs也要注意⼀个地⽅，就是需要结束时去存答案，⽽不是开始遍历前存答案。

但是为什么：这样逆序输出从⼩到⼤dfs搜索的答案能保证最后的答案还是字典序最⼩的？这个问题还不是很明⽩，暂留⼀问吧。

5.连通性问题（虽然这题没出到这种数据，但是也确实是⼀个wa点）最后就贴上上述题的代码吧。

#include<iostream>#include<cstring>#include<cstdlib>#include<vector>#include<queue>#include<cmath>#include<map>#include<algorithm>using namespace std;#define N 202#define mt(x) memset(x,0,sizeof x) typedef long long ll;void cn(ll x){cout<<x<<endl;}void cs(string x){cout<<x<<endl;} vector<int>vc[N];int n;int vis[N][N],c;char ans[N];int edge[N];void add(int x,int y){vc[x].push_back(y);vc[y].push_back(x);vis[x][y]++;vis[y][x]++;edge[x]++;edge[y]++;}void find(int x){for(int i='A';i<='z';++i){if(vis[x][i]){vis[x][i]--;vis[i][x]--;find(i);}}ans[c++]=x;}bool pd(){int cnt=0,t=0;for(int i='A';i<='z';++i)if(edge[i]%2){cnt++;if(!t)t=i;}if(!t){for(int i='A';i<='z';++i)if(edge[i]){t=i;break;}}if(cnt&&cnt!=2)return false;find(t);return true;}void PR(){while(c)cout<<ans[--c];cout<<endl;}void solve(){cin>>n;mt(edge);for(int i=0;i<n;++i){string s;cin>>s;add(s[0],s[1]);}if(!pd()||c!=n+1)cs("No Solution"); else PR();}int main(){ios::sync_with_stdio(false);cin.tie(0);solve();return0;}。

euler ancestral sampling 解析-回复Euler Ancestral Sampling 解析Euler Ancestral Sampling（欧拉祖先采样）是一种应用于概率图模型的采样方法，能够生成符合给定概率分布的样本。

它基于欧拉-马尔可夫链（Euler-Maruyama Chain）的理论，利用马尔可夫链中的状态转移过程来进行采样。

在本文中，我们将逐步解析Euler Ancestral Sampling 方法。

1. 引言概率图模型是一种描述随机变量之间依赖关系的工具，常用于建模和推理。

其中，贝叶斯网络是一种常见的概率图模型，用有向无环图表示变量之间的条件依赖关系。

在概率图模型中，我们常常需要从给定的概率分布中进行采样，为了实现这一目标，Euler Ancestral Sampling 方法应运而生。

2. 欧拉-马尔可夫链欧拉-马尔可夫链本质上是一种连续时间马尔可夫链，它是由基于欧拉方法离散化的随机微分方程演化而来。

马尔可夫链是一种状态转移概率满足马尔可夫性质的随机过程。

在欧拉-马尔可夫链中，状态转移过程受到离散化误差的影响，但仍然保持了接近连续时间的性质。

欧拉-马尔可夫链的状态转移方程为：X_{t+1} = X_t + f(X_t) * dt + g(X_t) * √(dt) * Z_t其中，X_t 为马尔可夫链在时间t 的状态，f(.) 和g(.) 是随机微分方程中的漂移项和扩散项函数，dt 是时间步长，Z_t 是满足标准正态分布的随机变量。

3. 欧拉祖先采样欧拉祖先采样是一种基于欧拉-马尔可夫链的采样方法。

给定一个概率图模型，我们希望从其中采样得到一个符合该模型分布的样本。

具体地，对于贝叶斯网络中的一个结点，我们需要根据其父结点的状态和概率分布来生成一个样本值。

对于每个结点，我们利用欧拉-马尔可夫链进行采样。

首先，我们初始化所有结点的状态。

然后，根据状态转移方程逐步更新结点的状态，直到链达到平稳状态。

离散数学欧拉图第7讲基本概念定义7.1◆通过无向图中所有边一次且仅一次行遍所有顶点的迹称为欧拉迹。

◆通过无向图中所有边一次且仅一次行遍所有顶点的闭迹称为欧拉环游。

◆具有欧拉环游的图称为欧拉图。

回忆思考哥尼斯堡七桥问题即下图是否是欧拉图的问题。

CA BD定理7.1设G是非平凡无向图，则G是欧拉图 G是连通图且G中没有奇点。

证明“”连通，显然。

因为所有的边都在欧拉环游上出现一次且仅一次，所以每个顶点的度=该顶点在欧拉环游上出现的次数的2倍。

故每个点都是偶点。

证：证明“”任一个无奇点的无向图，从任一条边开始都能长出一条闭迹。

设P 是G 中最长的闭迹，则P 是G 的欧拉环游。

（想想为什么？）故G 是欧拉图。

证：定理7.1（其中的必要性就足够了）回答了（实际上是否定）哥尼斯堡七桥问题。

CA BD推论设G 是非平凡无向图，则G有欧拉迹 G是连通图且G中至多有2个奇点。

一个图有欧拉迹，在中国古代被称为是“一笔画”的。

比如“日”可一笔画，而“田”不可一笔画。

思考上述定理给出了欧拉图的判定条件,那么如何找出欧拉环游呢?Fleury算法——一种求欧拉环游的方法(1) 任取v0∈V(G)，令P0= v0。

(2) 设P i= v0e1v1e2… e i v i已经选取，按下面方法来从E(G)-{e1,e2… e i}中选取e i+1：(a) e i+1与v i相关联；(b) 除非无别的边可供选择，否则e i+1不为G i=G-{e1,e2… e i}中的桥。

(3) 当(2)不能再进行时，算法停止。

123 456 789谢谢观看。

离散实验——欧拉图的判定和应⽤实验六欧拉图判定和应⽤【实验⽬的】掌握判断欧拉图的⽅法。

【实验内容】编程随机⽣成n个结点的⽆向图（有向图）并能进⾏（半）欧拉图的判定，若是则给出所有欧拉路.【要求】对给定n个结点，随机⽣成邻接矩阵以确定某⽆向简单图（有向图）并进⾏欧拉图和半欧拉图的判定，若符合则给出⾄少⼀条欧拉回路或欧拉路。

【实验原理和⽅法】是根据随机⽣成的图求欧拉（回）路，先要随机⽣成⼀个邻接矩阵，然后判定是否是欧拉回路只要根据奇数度结点的个数。

再⽤⼀个递归函数找出欧拉路。

（1）⽤关系矩阵R=表⽰图。

（2）对⽆向图⽽⾔，若所有结点的度都是偶数，则该图为欧拉图。

C语⾔算法：flag=1;for(i=1;i<=n && flag;i++){sum=0;for(j=1;j<=n;j++)if(r[i][j]) sum++;if(sum%2==0) flag=0;}如果 flag 该⽆向图是欧拉图（3）对有向图⽽⾔，若所有结点的⼊度等于出度，则该图为欧拉图。

C语⾔算法：flag=1;for(i=1;i<=n && flag;i++){sum1=0;sum2=0;for(j=1;j<=n;j++)if(r[i][j]) sum1++;for(j=1;j<=n;j++)if(r[j][i]) sum2++;if(sum1%2==0 || sum2%2==0) flag=0;}如果 flag 该有向图是欧拉图（4）求出欧拉路的⽅法：欧拉路经过每条边⼀次且仅⼀次。

可⽤回溯的⽅法求得所有欧拉路。

C语⾔算法：intcount=0,cur=0,r[N][N]; // r[N][N]为图的邻接矩阵，cur为当前结点编号，count为欧拉路的数量。

int sequence[M];// sequence保留访问点的序列，M为图的边数输⼊图信息;void try1(int k) //k表⽰边的序号{int i,pre=cur; //j保留前⼀个点的位置,pre为前⼀结点的编号if (r[cur][i]) //当前第cur点到第i点连通{//删除当前点与第i点的边，记下第k次到达点i，把第i个点设为当前点 r[cur][i]=0;cur=sequence[k]=i;if (k<M) try1(k+1); //试下⼀个点else prt1();//经过了所有边，打印⼀个解//上⾯条件不满⾜，说明当前点的出度为0，回溯，试下⼀位置r[pre][i]=1;cur=pre;}}附上代码：有向图：#include <stdio.h>#include <string.h>#include <stdlib.h>#include <time.h>int n,a[100][100],m=0,visit[100];int cur=0,s[100],vis[100][100];void try1(int k)//取欧拉路{int i;if(cur==m+1){for(i=0;i<cur;i++){if(i==0)printf("%d",s[i]+1);elseprintf("->%d",s[i]+1);}printf("\n");}else{for(i=0;i<n;i++){if(a[k][i]&&!vis[k][i]){vis[k][i]=1;vis[i][k]=1;s[cur++]=i;try1(i);cur--;vis[k][i]=0;vis[i][k]=0;}}}}void dfs(int k){int i;visit[k]=1;for(i=0;i<n;i++){if(a[k][i]&&!visit[i]){dfs(i);}}}int fun()//判断连通性{int i;dfs(0);return0;}return1;}int main(void){int i,j;memset(vis,0,sizeof(vis));memset(visit,0,sizeof(visit));srand(time(NULL));printf("请输⼊节点个数n：");scanf("%d",&n);for(i=0;i<n;i++){for(j=0;j<n;j++){if(i==j)a[i][j]=0;else if(i>j)a[i][j]=a[j][i];elsea[i][j]=rand()%2;m+=a[i][j];}}m/=2;printf("邻接矩阵为：\n ");for(i=0;i<n;i++){printf(" %d",i+1);}printf("\n");for(i=0;i<n;i++){printf("%d",i+1);for(j=0;j<n;j++)printf(" %d",a[i][j]);printf("\n");}if(fun()==0){printf("该图不是连通图！\n");return0;}printf("该图是连通图！\n");int odd=0;for(i=0;i<n;i++){int sum=0;for(j=0;j<n;j++){if(a[i][j])sum++;}if(sum%2)odd++;}if(odd==0){printf("该图没有奇数度节点，具有欧拉回路，是欧拉图。

一、欧拉回路所谓欧拉回路与哥尼斯堡7桥问题相联系的．在哥尼斯堡7桥问题中，欧拉证明了不存在这样的回路，使它经过图中每条边且只经过一次又回到起始点．与此相反，设G （V ，E ）为一个图，若存在一条回路，使它经过图中每条边且只经过一次又回到起始点，就称这种回路为欧拉回路，并称图G 为欧拉图．在一个图中，连接一个节点的边数称为该节点的度数．对欧拉图，我们有下列结果： 定理1 对连通图G （V ，E ），下列条件是相互等价的： （1）G 是一个欧拉图；（2）G 的每一个节点的度数都是偶数；（3）G 的边集合E 可以分解为若干个回路的并．证明 ：()()12⇒ 已知G 为欧拉图，则必存在一个欧拉回路．回路中的节点都是偶度数．()()23⇒ 设G 中每一个节点的度数均为偶数．若能找到一个回路C 1使G=C 1，则结论成立．否则，令G 1=G\C 1，由C 1上每个节点的度数均为偶数，则G 1中的每个节点的度数亦均为偶数．于是在G 1必存在另一个回路C 2．令G 2=G 1\C 2，···．由于G 为有限图，上述过程经过有限步，最后必得一个回路C r 使 G r =G r-1\C r 上各节点的度数均为零，即C r =G r-1．这样就得到Ｇ的一个分解 G C C C r =⋅⋅⋅12 ．()()31⇒ 设G C C C r =⋅⋅⋅12 ，其中i C （I=1,2,…,r ）均为回路．由于G 为连通图，对任意回路i C ,必存在另一个回路j C 与之相连，即i C 与j C 存在共同的节点．现在我们从图G 的任意节点出发，沿着所在的回路走，每走到一个共同的节点处，就转向另一个回路，···，这样一直走下去就可走遍G 的每条边且只走过一次,最后回到原出发节点，即G 为一个欧拉图．利用定理1去判断一个连通图是否为欧拉图比较容易，但要找出欧拉回路，当连通图比较复杂时就不太容易了．下面介绍一种求欧拉回路的算法．二、弗罗莱算法算法步骤如下：（1）任取起始点v v R 00,;→（2）设路)},({,),,({),,({1211201rr i i r i i i v v e v v e v v e R -⋅⋅⋅=已选出，则从E\},,,{21r e e e ⋅⋅⋅中选出边1+r e ，使1+r e 与ri v 相连，除非没有其它选择，G e r r \{}+1仍应为连通的．（3）重复步骤（2），直至不能进行下去为止．定理2 连通的有向图存在欧拉回路的充分必要条件是对任意节点，进入该节点边数（进数）与离开该点的边数（出数）相等．三、中国邮递员问题一名邮递员带着要分发的邮件从邮局出发，经过要分发的每个街道，送完邮件后又返回邮局．如果他必须至少一次走过他管辖范围内的每一条街道，如何选择投递路线，使邮递员走尽可能少的路程．这个问题是由我国数学家管梅谷先生（山东师范大学数学系教授）在1962年首次提出的，因此在国际上称之为中国邮递员问题．用图论的述语，在一个连通的赋权图G （V ，E ）中，要寻找一条回路，使该回路包含G 中的每条边至少一次，且该回路的权数最小．也就是说要从包含G 的每条边的回路中找一条权数最小的回路．如果G 是欧拉图，则很容易由弗罗莱算法求出一个欧拉回路，但是若G 不是欧拉图，即存在奇度数的节点，则中国由递员问题的解决要困难得多．本节的主要目标是给出在有奇度数节点的连通图中寻找最小权数的回路的方法．首先注意到，若图G 有奇数度节点，则G 的奇数度节点必是偶数个．把奇数度节点分为若干对，每对节点之间在G 中有相应的最短路，将这些最短路画在一起构成一个附加的边子集E '．令G / =G+E /，即把附加边子集E / 叠加在原图G 上形成一个多重图G /，这时G /中连接两个节点之间的边不止一条．显然G /是一个欧拉图，因而可以求出G /的欧拉回路．该欧拉回路不仅通过原图G 中每条边，同时还通过E / 中的每条边，且均仅一次．邮递员问题的难点在于当G 的奇数度节点较多时，可能有很多种配对方法，应怎样选择配对，能使相应的附加边子集E / 的权数ω(E / )为最小？为此有下列定理．定理 3 设G （V ，E ）为一个连通的赋权图，则使附加边子集E / 的权数ω(E / )为最小的充分必要条件是G+E / 中任意边至多重复一次，且G+E / 中的任意回路中重复边的权数之和不大于该回路总权数的一半．证明： 必要性．用反证法．设存在一种奇节点集的配对，使其附加边子集E / 权数 ω(E / )为最小．若 G+E / 中有一条边重复n n ()≥2次，由于G+E /为欧拉图，所以删去相应的二次重复边后仍为欧拉图．这样，相应的附加边子集的权数将减小，这与 ω(E /)为最小的假设矛盾．这说明E /中的边均互不相同．其次，若G+E / 中存在一个回路，使它的重复边的权数之和大于该回路总权数的一半，则在E / 中删去这些重复边（注意：这些边均在E /中），而代之以该回路的其余部分的边再重复一次．经过这种替代后所得到的边子集E //仍为附加子集，且ω(E //)<ω(E /)，又产生矛盾． 充分性．设有两个附加边子集E /和E //，均使G+E /和G+E //中每条边至多重复一次，且每个回路中的重复边的权数和不大该回路权数的一半，我们来证明ω(E /)=ω(E //)．首先注意到，由E /和E //不相同的部分组成的图（记为]\[//////）（E E EE G ）是由一个或若干个欧拉子图所组成的．这是因为E /＋E //中每个节点的度数均为偶数，而E /和E //的公共边数也是偶数，故]\[//////）（E E EE G 中每个节点的度数仍为偶数，所以它若为连通图时是一个欧拉图；若为非连通图时则由若干个欧拉子图组成．]\[//////）（E E EE G 的任何回路都由E /和E //中的边组成，而E /和E //在回路中的权数分别不大于该回路权数的一半，因而任何回路中属于E /中的权数之和与属于E //中的边数之和必定相等，所以ω(E /)=ω(E //)．它就是最优附加边子集的权数，即E /和E //均为使附加边子集的权数达到最小的最优附加边子集．由定理3可得一个寻找邮递员问题最优解的方法．现举例如下：例1 已知邮递员要投递的街道如图11-20所示，试求最优邮路．解 先找出奇节点：A 1，A 2，A 3，A 4，B 1，B 2，B 3，B 4．奇节点进行配对，不妨把A 1与B 1，A 2与B 2，A 3与B 3，A 4与B 4配对，求其最短路．显然它不是最优解．下面我们根据定理3来进行调解．第一次调整：删去多于一条的重复边，即A 3与B 3，A 4与B 4中的（A 4，B 3）．调整后，实际上成为A 1与B 1，A 2与B 2，A 3与A 4，B 3与B 4的配对，它们的最短路如图11-21所示． 第二次调整：发现在回路{A 1，A 2，B 2，A 4，B 3，B 4，B 1，A 1}中重复边的权数和为11，大于该回路权数20的一半．因而调整时，把该回路的重复边删去，代之以重复其余部分，得图11-22．可以看出，实际上是调整为A 1与A 2，B 1与B 4，A 3与A 4，B 2与B 3配对．第三次调整：在图11-22中发现回路{ A 3，A 4，B 2，A 3}中重复边的权数和为7，大于该回路权数10的一半，因而删去原重复边（A 3，V 2，A 4）和（A 4，B 2），而添加（B 2，A 3），得到图11-23．进行检查发现，既没有多于一条的重复边，也没有任何回路使其重复边的权数之和大于该回路的一半，因此图11-23就是最优的附加边子集E /，而G+E /为欧拉图，可由弗罗莱算法找出最优邮路．在现实生活中，很多问题都可以转化为中国邮递员问题，例如道路清扫时如何使开空车的总时间最少的问题等等．上面例1题所用的求最优邮路的方法叫“奇偶点图上作业法”．因为此方法要验证每个回路，很不方便，Edmods 和Johnson 在1973年提出一种比较有效的方法，有兴趣的读者可参考有关资料．习 题 11-31．证明，若图G 为欧拉图，则G 的边数不少于节点数．2．一名邮递员的投邮区，如下图11-24所示，每条边（街道）都有邮件需投递，各边旁所注的数字为该街道的长度，试求该邮区的最短投递路径及其长度． 3．求下列图11-25（a ）(b)所示的投邮区的最佳邮路及其长度．【算法】欧拉图，欧拉回路，Eular Circuit ，随机生成欧拉图，搜索欧拉回路背景：图论起源于18世纪，1736年瑞士数学家欧拉（Eular ）发表了图论的第一篇论文“哥尼斯堡七桥问题”。