精华内容
下载资源
问答
  • 哈密顿回路

    2016-07-09 12:20:36
    哈密顿回路:通过图的每个节点一次。 存在哈密顿回路的图就是哈密顿图。 判定条件:图中任意两个不同的节点的度数之和大于等于n。 代码:求hamilton回路 void Hamilton(int ans[maxn], bool map[maxn][maxn], int n)...

    哈密顿回路:通过图的每个节点一次。

    存在哈密顿回路的图就是哈密顿图。

    判定条件:图中任意两个不同的节点的度数之和大于等于n。

    代码:求hamilton回路

    void Hamilton(int ans[maxn], bool map[maxn][maxn], int n) {
        int s=1, t;
        int i, j;
        int ansk = 2;
        int w;
        int temp;
        bool vis[maxn];
        memset(vis, false, sizeof(vis));
        for (i=1; i<=n; i++) 
            if (map[s][i])
                break;
        t = i;
        ans[0] = s;
        ans[1] = t;   //任找两个相邻的节点
        while (1) {
            while (1) {     //从t开始拓展,拓展到一个点,就从该点在拓展
                for (i=1; i<=n; i++) {
                    if (map[t][i] && !vis[i]) {  
                        vis[i] = true;
                        ans[ansk++] = i;
                        t = i;
                        break;
                    }
                }
                if (i > n)
                    break;
            }
            reverse(ans, 0, ansk-1);    //翻转
            temp = s;
            s = t;
            t = temp;
            while (1) {   //从刚开始的s再拓展
                for (i=1; i<=n; i++) {
                    if (map[t][i] && !vis[i]) {
                        vis[i] = true;
                        ans[ansk++] = i;
                        t = i;
                        break;
                    }
                }
                if (i > n) break;
            }
            if (!map[s][t]) {   //若没有形成环,就构造一个环。
                for (i=1; i<ans-2; i++) 
                    if (map[ans[i][t]] && map[ans[i+1][s]])
                        break;
                w = ansk-1;
                i++;
                t = ans[i];
                reverse(ans, i, w);
            }
            if (ansk == n)   //完成停止
                return ;
            for (j=1; j<=n; j++) {   //加环以外的边。
                 if (!vis[j]) {
                    for (i=1; i<ansk-1; i++) 
                        if (map[ans[i]][j])
                            break;
                    if (map[ans[i]][j])
                        break;
                }
            }
            s = ans[i-1];
            t = j;
            reverse(ans, 0, i-1);   //始终形成环
            reverse(ans, i, ansk-1);
            ans[ansk++] = j;
            vis[j] = true;
        }
    }


    展开全文
  • 哈密顿图 哈密顿回路 哈密顿通路(Hamilton)

    万次阅读 多人点赞 2018-07-30 10:33:19
     哈密顿图:图G的一个回路,若它通过图的每一个节点一次,且仅一次,就是哈密顿回路.存在哈密顿回路的图就是哈密顿图.哈密顿图就是从一点出发,经过所有的必须且只能一次,最终回到起点的路径.图中有的边可以不经过,但是...

    概念:

      哈密顿图:图G的一个回路,若它通过图的每一个节点一次,且仅一次,就是哈密顿回路.存在哈密顿回路的图就是哈密顿图.哈密顿图就是从一点出发,经过所有的必须且只能一次,最终回到起点的路径.图中有的边可以不经过,但是不会有边被经过两次.

      与欧拉图的区别:欧拉图讨论的实际上是图上关于边的可行便利问题,而哈密顿图的要求与点有关.

    判定:

    一:Dirac定理(充分条件)

      设一个无向图中有N个顶点,若所有顶点的度数大于等于N/2,则哈密顿回路一定存在.(N/2指的是⌈N/2⌉,向上取整)

    二:基本的必要条件

      设图G=<V, E>是哈密顿图,则对于v的任意一个非空子集S,若以|S|表示S中元素的数目,G-S表示G中删除了S中的点以及这些点所关联的边后得到的子图,则W(G-S)<=|S|成立.其中W(G-S)是G-S中联通分支数.

    三:竞赛图(哈密顿通路)

      N(N>=2)阶竞赛图一点存在哈密顿通路.

    算法:

    一:在Dirac定理的前提下构造哈密顿回路

    过程:

      1:任意找两个相邻的节点S和T,在其基础上扩展出一条尽量长的没有重复结点的路径.即如果S与结点v相邻,而且v不在路径S -> T上,则可以把该路径变成v -> S -> T,然后v成为新的S.从S和T分别向两头扩展,直到无法继续扩展为止,即所有与S或T相邻的节点都在路径S -> T上.

      2:若S与T相邻,则路径S -> T形成了一个回路.

      3:若S与T不相邻,可以构造出来一个回路.设路径S -> T上有k+2个节点,依次为S, v1, v2, ..., vk, T.可以证明存在节点vi(i属于[1, k]),满足vi与T相邻,且vi+1与S相邻.找到这个节点vi,把原路径变成S -> vi -> T -> vi+1 ,即形成了一个回路.

      4:到此为止,已经构造出来了一个没有重复节点的的回路,如果其长度为N,则哈密顿回路就找到了.如果回路的长度小于N,由于整个图是连通的,所以在该回路上,一定存在一点与回路之外的点相邻.那么从该点处把回路断开,就变回了一条路径,同时还可以将与之相邻的点加入路径.再按照步骤1的方法尽量扩展路径,则一定有新的节点被加进来.接着回到路径2.

    证明:

      跟据鸽巢定理,既然与S和T相邻的点都在路径上,它们分布的范围只有v1,v2---,vk这k个点,k<=N-2,跟据哈密顿回路的第一个判断条件,d(S)+d(T)>=N,那么v1,v2,---vk这k个点中一定有至少2个点同时与S和T相连,根据鸽巢定理,肯定存在一个与S相邻的点vi和一个与T相邻的点vj,满足j=i+1

    伪代码:

      设s为哈密顿回路的起始点,t为哈密顿回路中终点s之前的点.ans[]为最终的哈密顿回路.倒置的意思指的是将数组对应的区间中数字的排列顺序反向.

      1:初始化,令s = 1,t为s的任意一个邻接点.

      2:如果ans[]中元素的个数小于n,则从t开始向外扩展,如果有可扩展点v,放入ans[]的尾部,并且t=v,并继续扩展,如无法扩展进入步骤3.

      3:将当前得到的ans[]倒置,s和t互换,从t开始向外扩展,如果有可扩展点v,放入ans[]尾部,并且t=v,并继续扩展.如无法扩展进入步骤4.

      4:如果当前s和t相邻,进入步骤5.否则,遍历ans[],寻找点ans[i],使得ans[i]与t相连并且ans[i +1]与s相连,将从ans[i + 1]到t部分的ans[]倒置,t=ans[i +1],进如步骤5.

      5:如果当前ans[]中元素的个数等于n,算法结束,ans[]中保存了哈密顿回路(可看情况是否加入点s).否则,如果s与t连通,但是ans[]中的元素的个数小于n,则遍历ans[],寻找点ans[i],使得ans[i]与ans[]外的一点(j)相连,则令s=ans[i - 1],t = j,将ans[]中s到ans[i - 1]部分的ans[]倒置,将ans[]中的ans[i]到t的部分倒置,将点j加入到ans[]的尾部,转步骤2.

    时间复杂度:

      如果说每次到步骤5算一轮的话,那么由于每一轮当中至少有一个节点被加入到路径S -> T中,所以总的轮数肯定不超过n轮,所以时间复杂度为O(n^2).空间上由于边数非常多,所以采用邻接矩阵来存储比较适合.

    附上模板:

    
    const int maxN = 100;
    
    inline void reverse(int arv[maxN + 7], int s, int t){//将数组anv从下标s到t的部分的顺序反向
        int temp;
        while(s  < t){
            temp = arv[s];
            arv[s] = arv[t];
            arv[t] = temp;
            s++;
            t--;
        }
    }
    
    void Hamilton(int ans[maxN + 7], bool map[maxN + 7][maxN + 7], int n){
        int s = 1, t;//初始化取s为1号点
        int ansi = 2;
        int i, j;
        int w;
        int temp;
        bool visit[maxN + 7] = {false};
        for(i = 1; i <= n; i++) if(map[s][i]) break;
        t = i;//取任意邻接与s的点为t
        visit[s] = visit[t] = true;
        ans[0] = s;
        ans[1] = t;
        while(true){
            while(true){//从t向外扩展
                for(i = 1; i <= n; i++){
                    if(map[t][i] && !visit[i]){
                        ans[ansi++] = i;
                        visit[i] = true;
                        t = i;
                        break;
                    }
                }
                if(i > n) break;
            }
            w = ansi - 1;//将当前得到的序列倒置,s和t互换,从t继续扩展,相当于在原来的序列上从s向外扩展
            i = 0;
            reverse(ans, i, w);
            temp = s;
            s = t;
            t = temp;
            while(true){//从新的t继续向外扩展,相当于在原来的序列上从s向外扩展
                for(i = 1; i <= n; i++){
                    if(map[t][i] && !visit[i]){
                        ans[ansi++] = i;
                        visit[i] = true;
                        t = i;
                        break;
                    }
                }
                if(i > n) break;    
            }
            if(!map[s][t]){//如果s和t不相邻,进行调整
                for(i = 1; i < ansi - 2; i++)//取序列中的一点i,使得ans[i]与t相连,并且ans[i+1]与s相连
                    if(map[ans[i]][t] && map[s][ans[i + 1]])break;
                w = ansi - 1;
                i++;
                t = ans[i];
                reverse(ans, i, w);//将从ans[i +1]到t部分的ans[]倒置
            }//此时s和t相连
            if(ansi == n) return;//如果当前序列包含n个元素,算法结束
            for(j = 1; j <= n; j++){//当前序列中元素的个数小于n,寻找点ans[i],使得ans[i]与ans[]外的一个点相连
                if(visit[j]) continue;
                for(i = 1; i < ansi - 2; i++)if(map[ans[i]][j])break;
                    if(map[ans[i]][j]) break;
            }
            s = ans[i - 1];
            t = j;//将新找到的点j赋给t
            reverse(ans, 0, i - 1);//将ans[]中s到ans[i-1]的部分倒置
            reverse(ans, i, ansi - 1);//将ans[]中ans[i]到t的部分倒置
            ans[ansi++] = j;//将点j加入到ans[]尾部
            visit[j] = true;
        }
    }

    在整个构造过程中,如果说每次到步骤5算做一轮的话,那么每一轮当中至少有一个节点被加入到路径S->T中,所以总的轮数肯定不超过n轮,实际上,不难看出该算法的复杂度是O(n^2),因此总共拓展了n轮路径,每步拓展最多枚举所有的节点。

    二:N(N>=2)阶竞赛图构造哈密顿通路

    N阶竞赛图:含有N个顶点的有向图,且每对顶点之间都有一条边.对于N阶竞赛图一定存在哈密顿通路.

    数学归纳法证明竞赛图在n >= 2时必存在哈密顿路:

    (1)n = 2时结论显然成立;

    (2)假设n = k时,结论也成立,哈密顿路为V1, V2, V3, ..., Vk;

      设当n = k+1时,第k + 1个节点为V(k+1),考虑到V(k+1)与Vi(1<=i<=k)的连通情况,可以分为以下两种情况.

        1:Vk与V(k+1)两点之间的弧为<Vk, V(k+1)>,则可构造哈密顿路径V1, V2,…, Vk, V(k+1).

        2:Vk与V(k+1)两点之间的弧为<V(k+1),Vk>,则从后往前寻找第一个出现的Vi(i=k-1,i>=1,--i),满足Vi与V(k+1)之间的弧为<Vi,V(k+1)>,则构造哈密顿路径V1, V2, …, Vi, V(k+1), V(i+1), …, V(k).若没找到满足条件的Vi,则说明对于所有的Vi(1<=i<=k)到V(k+1)的弧为<V(k+1),V(i)>,则构造哈密顿路径V(k+1), V1, V2, …, Vk.

    证毕.

    竞赛图构造哈密顿路时的算法同以上证明过程.

     

    用图来说明:

    假设此时已经存在路径V1 -> V2 -> V3 -> V4,这四个点与V5的连通情况有16种,给定由0/1组成的四个数,第i个数为0代表存在弧<V5,Vi>,反之为1,表示存在弧<Vi,V5>

     

     

     

    sign[]={0, 0, 0, 0}.

    很显然属于第二种情况,从后往前寻找不到1,即且不存在弧<Vi, V5>.

    则构造哈密顿路:V5 -> V1 -> V2 -> V3 -> V4.

     

     

    sign[]={0, 0, 0, 1}.

    属于第一种情况,最后一个数字为1,即代表存在弧<Vi, V5>且i=4(最后一个点)

    则构造哈密顿路: V1 -> V2 -> V3 -> V4 -> V5.

     

     

     

    sign[]={0, 0, 1, 0}.

    属于第二种情况,从后往前找到1出现的第一个位置为3.

    构造哈密顿路: V1 -> V2 -> V3 -> V5 -> V4.

     

     

     

    sign[]={0, 0, 1, 1}.

    属于第一种情况,最后一个数字为1,即代表存在弧<Vi, V5>且i=4(最后一个点)

    则构造哈密顿路: V1 -> V2 -> V3 -> V4 -> V5.

     

     

     

    sign[]={0, 1, 0, 0}.

    属于第二种情况,从后往前找到1出现的第一个位置为2.

    构造哈密顿路: V1 -> V2 -> V5 -> V3-> V4.

     

     

     

    sign[]={0, 1, 0, 1}.

    属于第一种情况,最后一个数字为1,即代表存在弧<Vi, V5>且i=4(最后一个点)

    则构造哈密顿路:V1 -> V2 -> V3 -> V4 -> V5.(就不举末尾为1的栗子了~~)

     

     

     

    sign[]={1, 0, 1, 0}.

    属于第二种情况,从后往前找到1出现的第一个位置为3.

    构造哈密顿路: V1 -> V2 -> V3 -> V5-> V4.

     

     

     

    sign[]={1, 1, 1, 0}.

    属于第二种情况,从后往前找到1出现的第一个位置为3.

    构造哈密顿路: V1 -> V2 -> V3 -> V5-> V4.

     

     

     

    (还是举一个吧~~~)

    sign[]={1, 1, 1, 1}.

    同样最后一位为1,代表存在<Vi, V5>且i=4(最后一位)

    则构造哈密顿路:V1 -> V2 -> V3 -> V4 -> V5.以上是当N=4时(N+1=5),用图来阐述算法的过程.

    注意从后往前找不是找这个点编号之前的点,即不是按照编号来的,而是按照当前哈密顿序列从后往前找的.举个栗子:

    4

    2 1

    1 3

    3 2

    4 1

    4 2

    4 3

    第一步ans={1}

    第二步ans={2,1}

    第三步sign={0, 1}(map[3][2] = 0,map[3][1] = 1,当前序列为2,1) ,而不是{1, 0}(1,2),因为存在弧<V1, V3>和<V3, V2>.这里需要注意下.

    代码:

    #include <iostream>
    #include <cmath>
    #include <cstdio>
    #include <cstring>
    #include <cstdlib>
    #include <algorithm>
    #include <queue>
    #include <stack>
    #include <vector>
    
    using namespace std;
    typedef long long LL;
    const int maxN = 200;
    
    //The arv[] length is len, insert key befor arv[index] 
    inline void Insert(int arv[], int &len, int index, int key){ 
        if(index > len) index = len;
        len++;
        for(int i = len - 1; i >= 0; --i){
            if(i != index && i)arv[i] = arv[i - 1];
            else{arv[i] = key; return;}
        }
    }
    
    void Hamilton(int ans[maxN + 7], int map[maxN + 7][maxN + 7], int n){
        int ansi = 1;
        ans[ansi++] = 1;
        for(int i = 2; i <= n; i++){//第一种情况,直接把当前点添加到序列末尾
            if(map[i][ans[ansi - 1]] == 1)
                ans[ansi++] = i;
            else{
                int flag = 0;
                for(int j = ansi - 2; j > 0; --j){//在当前序列中,从后往前找到第一个满足条件的点j,使得存在<Vj,Vi>且<Vi, Vj+1>.
                    if(map[i][ans[j]] == 1){//找到后把该点插入到序列的第j + 1个点前.
                        flag = 1;
                        Insert(ans, ansi, j + 1, i);
                        break;
                    }
                }
                if(!flag)Insert(ans, ansi, 1, i);//否则说明所有点都邻接自点i,则把该点直接插入到序列首端.
            }
        }
    }
    
    int main()
    {
        //freopen("input.txt", "r", stdin);
        int t;
        scanf("%d", &t);
        while(t--){
            int N;
            scanf("%d", &N);
            int M = N * (N - 1) / 2;
            int map[maxN + 7][maxN + 7] = {0};
            for(int i = 0; i < M; i++){
                int u, v;
                scanf("%d%d", &u, &v);
                //map[i][j]为1说明j < i,且存在弧<Vi, Vj>,因为插入时只考虑该点之前的所有点的位置,与之后的点没有关系.所以只注重该点与其之前的点的连通情况.
                if(u < v)map[v][u] = 1;
            }
            int ans[maxN + 7] = {0};
            Hamilton(ans, map, N);
            for(int i = 1; i <= N; i++)
                printf(i == 1 ? "%d":" %d", ans[i]);
            printf("\n");
        }
        return 0;
    }
    void Hamilton(int ans[maxN + 7], int map[maxN + 7][maxN + 7], int n){
        int nxt[maxN + 7];
        memset(nxt, -1, sizeof(nxt));
        int head = 1;
        for(int i = 2; i <= n; i++){
            if(map[i][head]){
                nxt[i] = head;
                head = i;
            }else{
                int pre = head, pos = nxt[head];
                while(pos != -1 && !map[i][pos]){
                    pre = pos;
                    pos = nxt[pre];
                }
                nxt[pre] = i;
                nxt[i] = pos;
            }
        }
        int cnt = 0;
        for(int i = head; i != -1; i = nxt[i])
            ans[++cnt] = i;
    }
    void Hamitton(bool reach[N + 7][N + 7], int n)  
    {    
        vector <int> ans; 
        ans.push_back(1);  
        for(int i=2;i <= n;i++)  
        {  
            bool cont = false;  
            for(int j=0;j<(int)ans.size()-1;j++)  
                if(reach[ ans[j] ][i] && reach[i][ ans[j+1] ])  
                {  
                    ans.insert(ans.begin()+j+1,i);  
                    cont = true;  
                    break;  
                }  
            if(cont)  
                continue;  
            if(reach[ ans.back() ][i])  
                ans.push_back(i);  
            else  
                ans.insert(ans.begin(),i);  
        } 
        for(int i=0;i<n;i++)  
                       printf("%d%c",ans[i],i==n-1?'\n':' ');   
    }

     

    展开全文
  • 欧拉回路及哈密顿回路

    千次阅读 2013-10-04 21:38:37
    欧拉图: 在图为连通图的前提下,欧拉通路:当前...相关判定条件(图联通) (1)无向图存在欧拉回路的条件是:图中不存在奇度结点,有向图存在欧拉回路的条件是:每个结点出度均等于入度。 (2)无向图存在欧拉通

    转载自:http://blog.csdn.net/zhang360896270/article/details/8746783

    欧拉图:

    在图为连通图的前提下,欧拉通路:当前图中经过每条边一次且仅一次,若最终回到出发点则称为欧拉回路。

    相关判定条件(图联通)

    (1)无向图存在欧拉回路的条件是:图中不存在奇度结点,有向图存在欧拉回路的条件是:每个结点出度均等于入度

    (2)无向图存在欧拉通路的条件是:图中仅存在两个奇度结点(起点和终点),有向图存在欧拉通路的条件是:存在两个结点入度不等于出度,分别为起点(出度-入度==1)和终点(入度-出度==1)

    除此之外个人认为无向图只要存在欧拉回路则从任意一点出发均可遍历全部边回到该点(哈密顿图同理)。

    判定欧拉图只是基础,更重要的是找出具体的欧拉路径(回路)

    算法:

    使用链式前向星存储图(便于找边),可先通过并查集(或者广搜)判断当前图是否连通,然后还能记录出入度根据之前定理判定。然后通过深搜并且标记每一条走过的边确定是否有欧拉路径(回路),算法整体思路较简单,关键是能否想到利用欧拉路径(回路)建立模型。

    哈密顿图:

    在图为无向连通图的前提下,哈密顿通路:经过每个顶点一次且仅一次,若最终回到出发点则称为哈密顿图,哈密顿图为NP完全问题,暂不存在多项式时间内的解法

    相关判定条件(图无向且连通)

    (1)若图有n个结点的无向图且任意两个不同的结点度数之和均大于n,则此图为哈密顿图(存在哈密顿回路),此为判断是否是哈密顿图的充分条件,也就是说满足这个条件一定是哈密顿图,但哈密顿图不一定必满足这个条件。

    算法:(前提是图有n个结点的无向图且任意两个不同的结点度数之和均大于n)

    选取任意结点作为S,与其相邻一结点为T,然后逐步向两边扩展至无法扩展为止,若此时S与T连通,则判断是否S->T中包含全部点,若不连通则查找S->T中结点v[i]与T相邻且v[i+1]与S相邻的点,即S->v[i]->v[i+1]->T,而此时S ->V[i+1],T->V[i],将V[i+1]及其后部分翻转可构成S->v[i]->T->v[i+1]的哈密顿回路,判断此时是否路径包含全部结点,若不包含,查找不属于回路中但与其中结点相邻的结点,然后可将此回路缩为一点(因为已经求得当前回路为哈密顿回路)再修改S、T重复上述过程。

    欧拉路径(回路)相关题目:UVA10054、POJ2230、HDU1116

    哈密顿(回路)相关题目:POJ2438

    UVA10054(每一个珠子首尾连接构成无向图)

    展开全文
  • 相关判定条件(图联通)  (1)无向图存在欧拉回路的条件是:图中不存在奇度结点,有向图存在欧拉回路的条件是:每个结点出度均等于入度。  (2)无向图存在欧拉通路的条件是:图中仅存在两个奇度结点(起点...

     欧拉图:

    在图为连通图的前提下,欧拉通路:当前图中经过每条边一次且仅一次,若最终回到出发点则称为欧拉回路。

    相关判定条件(图联通)

             (1)无向图存在欧拉回路的条件是:图中不存在奇度结点,有向图存在欧拉回路的条件是:每个结点出度均等于入度

             (2)无向图存在欧拉通路的条件是:图中仅存在两个奇度结点(起点和终点),有向图存在欧拉通路的条件是:存在两个结点入度不等于出度,分别为起点(出度-入度==1)和终点(入度-出度==1)

    除此之外个人认为无向图只要存在欧拉回路则从任意一点出发均可遍历全部边回到该点(哈密顿图同理)。

    判定欧拉图只是基础,更重要的是找出具体的欧拉路径(回路)

    算法:

             使用链式前向星存储图(便于找边),可先通过并查集(或者广搜)判断当前图是否连通,然后还能记录出入度根据之前定理判定。然后通过深搜并且标记每一条走过的边确定是否有欧拉路径(回路),算法整体思路较简单,关键是能否想到利用欧拉路径(回路)建立模型。

     

    哈密顿图:

    在图为无向连通图的前提下,哈密顿通路:经过每个顶点一次且仅一次,若最终回到出发点则称为哈密顿图,哈密顿图为NP完全问题,暂不存在多项式时间内的解法

    相关判定条件(图无向且连通)

            (1)若图有n个结点的无向图且任意两个不同的结点度数之和均大于n,则此图为哈密顿图(存在哈密顿回路),此为判断是否是哈密顿图的充分条件,也就是说满足这个条件一定是哈密顿图,但哈密顿图不一定必满足这个条件。

    算法:(前提是图有n个结点的无向图且任意两个不同的结点度数之和均大于n)

             选取任意结点作为S,与其相邻一结点为T,然后逐步向两边扩展至无法扩展为止,若此时S与T连通,则判断是否S->T中包含全部点,若不连通则查找S->T中结点v[i]与T相邻且v[i+1]与S相邻的点,即S->v[i]->v[i+1]->T,而此时S ->V[i+1],T->V[i],将V[i+1]及其后部分翻转可构成S->v[i]->T->v[i+1]的哈密顿回路,判断此时是否路径包含全部结点,若不包含,查找不属于回路中但与其中结点相邻的结点,然后可将此回路缩为一点(因为已经求得当前回路为哈密顿回路)再修改S、T重复上述过程。

    欧拉路径(回路)相关题目:UVA10054、POJ2230、HDU1116

    哈密顿(回路)相关题目:POJ2438

    UVA10054(每一个珠子首尾连接构成无向图)

    展开全文
  • 欧拉回路 定义 欧拉回路:图G中每条边且只通过一次,并且经过每一顶点的回路 欧拉通路:(欧拉路径):图G中每条边且只通过一次,并且...判定一个图是否是(半)欧拉图 无向图: 定理1:无向图G为欧拉图,当且仅当...
  • 相关判定条件(图联通)  (1)无向图存在欧拉回路的条件是:图中不存在奇度结点,有向图存在欧拉回路的条件是:每个结点出度均等于入度。  (2)无向图存在欧拉通路的条件是:图中仅存在两个奇度结点(起点和...
  • 文章目录道路与回路概念简单有向道路(回路)和初级有向道路(回路)连通图道路与回路-小结道路与回路的判定邻接矩阵法搜索法道路回路的判定--小结欧拉道路与回路哈密顿道路与回路哈密顿回路判定证明回顾闭合图...
  • 哈密顿

    千次阅读 2016-03-22 12:12:48
    有一个判定条件是设图G具有n个定点的无向联通图,如果图G任意两个定点度数之和大于n,则G具有哈密顿回路,满足这个条件则一定是哈密顿图,但是哈密顿图不一定满足这个条件,最简单的例子就是一个n阶圈图 目前判断...
  • 各种图回路性质及判定

    千次阅读 2017-02-28 22:44:24
    一、哈密顿回路  1.哈密顿回路必须是封闭的环 2.是一个连通图,任意两点都可到达,经过图中所有的点一次且仅一次的回路. 二、欧拉回路(图的一笔画问题) 1.欧拉通路:存在这样一条路径,使其经过图G中所有的边一次 若...
  • 2. 哈密顿图的定义(哈密顿通路、哈密顿回路) 3. 哈密顿图的必要条件及其推论及推论的应用 4. 证明不存在哈密顿回路 5. 哈密顿图的充分条件 6. 哈密顿图的其他判定方法 方法1: ...
  • 哈密顿图与半哈密顿图前言一、半/哈密顿图定义二、半/哈密顿图的必要条件三、...2.哈密顿回路:给定无向图G中,通过图中每个结点一次而且仅一次的回路。 3.哈密顿图:具有哈密顿回路的图。 4.半哈密顿图:有哈密顿路
  • 欧拉图与哈密顿

    2019-03-13 16:47:42
    存在性判定 欧拉回路:从图中某一顶点出发,所有边仅经过一次,最后回到该顶点。 无向图:所有顶点度数为偶数 ... 存在哈密顿回路的图称为哈密顿图。 在n阶简单图中,若任一对不相邻顶点(u, v)有d...
  • 欧拉图和哈密顿

    2019-02-19 01:08:45
    存在性判定 欧拉回路:从图中某一顶点出发,所有边仅经过一次,最后回到该顶点。 无向图:所有顶点度数为偶数 ... 存在哈密顿回路的图称为哈密顿图。 在n阶简单图中,若任一对不相邻顶点(u, v)有d...
  • 哈密顿图和欧拉图知识小结

    千次阅读 2017-08-02 20:56:46
    哈密顿图的判定是世界级难题。 设G是n阶无向简单图,若对于G中任意不相邻的顶点u、v,均有d(u)+d(v)>=n-1,则说明G中存在哈密顿通路。...所以要判断哈密顿回路和哈密顿路径一般通过深搜回溯去判定,代码: #in
  • 哈密顿问题 基本概念 哈密尔顿通路:经过图中每个结点且仅经过一次的通路。 哈密尔顿回路:经过图中每个结点且仅经过一次的回路。 哈密尔顿图:存在哈密尔顿回路的图。 竞赛图:每对顶点之间都有一条边相连的有向图...
  • 看到哈密顿回路就被吓傻了……结果没有好好考虑性质…… 首先,平面图有个性质:边数小于等于$3n-6$(我也不知道为啥),边数大于这个的直接pass 然后考虑原图,先把哈密顿回路单独摘出来,就是一个环。对于每一条...
  • 但是题目中有一个条件——这张图存在一条哈密顿回路。 我们把哈密顿回路在平面上画成一个圆。仔细观察一下。  每条边如果画在圆内都是一条弦,那如果弦在圆内相交怎么办?把另一条弦翻出去。...
  • 【基本概念】 哈密尔顿通路:经过图中每个结点且仅... 与欧拉回路的对比:欧拉回路是指不重复地走过所有路径的回路;哈密尔顿回路是指不重复地走过所有点并且最后回到起点的回路。 【判定】 1.哈密尔顿通路的判定...
  • 题目大意: 给出一张包含一个哈密顿回路的图,问这个图是不是平面图(即可以画在同一个平面上且边不相交)。 题解 由于存在一个哈密顿回路(下面称作圆),所以每条边有三种连法:连在圆的内部,顺时针连在圆的外部...
  • 算法:图遍历问题

    2019-05-31 19:29:43
    欧拉回路判定:仅有两个奇数度点,或没有奇数度点。 找欧拉回路: DFS搜索,POJ1780,相同位作为边,不用位作为点,稠密图,DFS容易得到结果 Fleury算法,在每个dfs状态中,能不走桥就不走桥,即可。 哈密顿回路...
  • 1.欧拉图定义欧拉通路/回路:通过每条边有且仅有一次的通路/回路欧拉图:具有欧拉回路的图半欧拉图:有欧拉通路,无欧拉回路判定定理无向欧拉图判别法:G是无向欧拉图 G是连通图且G无奇度顶点无向半欧拉图判别法:G...
  • 1.欧拉图定义欧拉通路/回路:通过每条边有且仅有一次的通路/回路欧拉图:具有欧拉回路的图半欧拉图:有欧拉通路,无欧拉回路判定定理无向欧拉图判别法:G是无向欧拉图 G是连通图且G无奇度顶点无向半欧拉图判别法:G...
  • 题意:给定一个图和一个哈密顿回路判定是否是平台图。 解法: 用平面图m 若两条边在圆内相交,则他们在圆外也是相交的,即若a,b不能同时取,a’,b’也不能同时取 按2-sat建模缩点后判断合法性 ///BZOJ...
  • HNOI2010 平面图判定

    2018-10-28 11:53:00
    我们发现他给了我们一个很好的性质:那就是这个平面图上存在着一个哈密顿回路(n元环)。 那么我们就可以很简单的判定两条边 如果划在同一侧是否会相交。 如果相交,那么我们就得把他们放在两侧,否则不需要。 ...
  • [HNOI2010]平面图判定

    2019-03-04 13:12:00
    现在假设你要判定的是一类特殊的图,图中存在一个包含所有顶点的环,即存在哈密顿回路。输入输出格式输入格式: 输入文件的第一行是一个正整数 \(T\),表示数据组数 (每组数据描述一个需要判定的图)。接下来从输入文...

空空如也

空空如也

1 2 3 4
收藏数 69
精华内容 27
关键字:

哈密顿回路判定