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

    千次阅读 2017-03-15 19:57:34
    哈密顿图 一、定义概念 1.哈密顿通路  设G=为一图(无向图或有向图).G中经过每个顶点一次且仅一次的通路称作哈密顿通路 2.哈密顿回路  G中经过每个顶点一次且仅一次的回路称作哈密顿回路 3.哈密顿图  若G...

    哈密顿图

    一、定义概念

    1.哈密顿通路

             设G=<V,E>为一图(无向图或有向图).G中经过每个顶点一次且仅一次的通路称作哈密顿通路

    2.哈密顿回路

             G中经过每个顶点一次且仅一次的回路称作哈密顿回路

    3.哈密顿图

            若G中存在哈密顿回路,则称它是哈密顿图

    4.定义详解:

           (1)存在哈密顿通路(回路)的图一定是连通图;

           (2)哈密顿通路是初级通路,哈密顿回路是初级回路;

           (3)若G中存在哈密顿回路,则它一定存在哈密顿通路,反之不真

           (4)只有哈密顿通路,无哈密顿回路的图不交哈密顿图;

    二、判定定理

    注意:目前没有找到哈密顿图的简单的充要条件

           (1)设无向图G=<V,E>为哈密顿图,V1是V的任意真子集,则

                                                                    p(G-V1)<=|V1|

           其中,p(G-V1)为G中删除V1后的所得图的联通分支数目,|V1|为V1集合中包含的顶点个数。【哈密顿图存在的必要条件】

           推论有割点的图一定不是哈密顿图

           设v是图中的割点,则p(G-v)>=2,由上述定理知G不是哈密顿图

           (2)设G是n(n>=3)阶无向简单图,若对于G中的每一对不相邻的顶点u,v,均有

            d(u)+d(v)>=n-1

           则G中存在哈密顿通路。又若

            d(u)+d(v)>=n

           则G中存在哈密顿回路,即G为哈密顿图。【哈密顿图存在的充分条件,不是必要条件】

           其中d(u),d(v)分别代表顶点u,v的度数。

           推论:设G是n(n>=3)阶无向简单图,若G的最小度>=n/2,则G是哈密顿图。

           由推论知,对于完全图Kn,当n>=3时,是哈密顿图,完全二部图Kr,s当r==s>=2时是哈密顿图。

           (3)在n(n>=2)阶有向图D=<V,E>中,如果略去所有有向边的方向,所得无向图中含生成子图Kn,则D中存在哈密顿通路。

           推论:n(n>=3)阶有向完全图是哈密顿图。

    1.常用方法判断是哈密顿图:

           (1)若能通过观察找出图G中的一条哈密顿回路,则G当然是哈密顿图。

           (2)若一个无向图G满足上述(2)中的条件,一个有向图D满足上述(3)的推论的条件,则G、D都是哈密顿图。

    2.破坏哈密顿图存在的必要条件,判定不是哈密顿图:

           设n阶图G是哈密顿图,则G应该满足以下诸条件:

           (1)G必须是连通图;

           (2)G中的边数m必须大于等于顶点数n;

           (3)若G中存在2度顶点v,即d(v)=2,则与v关联的两条边ei,ej必须在G中的任何哈密顿回路上;

           (4)若G中存在每条哈密顿回路中出现的边,不能构成边数小于n的初级回路(圈);

    破坏以上诸条件中的一条,都不是哈密顿图。

    展开全文
  • 哈密顿图 哈密顿回路 哈密顿通路(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':' ');   
    }

     

    展开全文
  • 金字塔图的哈密顿图性质研究,宁安琪,宁宣熙,本文仿照埃及金字塔的形状,设计了一类金字塔图,它包括平面金字塔图和立体多面金字塔图,并用一般图中构造哈密顿轨(圈)的自组
  • 扇面蜂巢图及其哈密顿图性质的研究,宁安琪 ,宁宣熙,本文提出了一种扇面蜂巢图,它是由若干个(P 2,P为个数)20角顶的哈密顿图拼接成扇面构成的。文中研究了这种扇面蜂巢图的哈密顿图
  • 知识点 - 哈密顿图

    2019-08-16 21:38:12
    知识点 - 哈密顿图 解决问题类型: 对于顶点个数大于2的图,如果图中任意两点度的和大于或等于顶点总数,那这个图一定是哈密顿图。闭合的哈密顿路径称作哈密顿圈,含有图中所有顶点的路径称作哈密顿路径。 哈密顿图:...

    知识点 - 哈密顿图

    解决问题类型:

    对于顶点个数大于2的图,如果图中任意两点度的和大于或等于顶点总数,那这个图一定是哈密顿图。闭合的哈密顿路径称作哈密顿圈,含有图中所有顶点的路径称作哈密顿路径。

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

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

    概念

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

    竞赛图是通过在无向完整图中为每个边缘分配方向而获得的有向图(有向图)。 也就是说,它是一个完整图形的方向,等价于一个有向图,其中每对不同的顶点通过单个有向边连接,即每对顶点之间都有一条边相连的有向图称为竞赛图。设D为n阶有向简单图,若D中基图为n阶无向完全图,则称D是n阶竞赛图

    img

    判定

    一:Dirac定理(充分条件)

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

    二:基本的必要条件

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

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

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

    过程:

    1:任意找两个相邻的节点SSTT,在其基础上扩展出一条尽量长的没有重复结点的路径.即如果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,S, v1, v2, ..., vk, T.可以证明存在节点vi(i属于[1,k][1, k]),满足vi与T相邻,且vi+1vi+1SS相邻.找到这个节点vi,把原路径变成S&gt;vi&gt;T&gt;vi+1S -&gt; vi -&gt; T -&gt; vi+1 ,即形成了一个回路.

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

    证明:

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

    复杂度:

    O(N2)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;
        }
    }
    

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

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

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

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

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

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

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

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

    证毕.

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

    用图来说明:

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

    img

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

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

    则构造哈密顿路:V5&gt;V1&gt;V2&gt;V3&gt;V4.V5 -&gt; V1 -&gt; V2 -&gt; V3 -&gt; V4.

    img

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

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

    则构造哈密顿路:V1&gt;V2&gt;V3&gt;V4&gt;V5.V1 -&gt; V2 -&gt; V3 -&gt; V4 -&gt; V5.

    img

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

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

    构造哈密顿路: V1&gt;V2&gt;V3&gt;V5&gt;V4V1 -&gt; V2 -&gt; V3 -&gt; V5 -&gt; V4.

    img

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

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

    则构造哈密顿路: V1&gt;V2&gt;V3&gt;V4&gt;V5V1 -&gt; V2 -&gt; V3 -&gt; V4 -&gt; V5.

    img

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

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

    构造哈密顿路: V1&gt;V2&gt;V5&gt;V3&gt;V4V1 -&gt; V2 -&gt; V5 -&gt; V3-&gt; V4.

    img

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

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

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

    img

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

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

    构造哈密顿路:V1&gt;V2&gt;V3&gt;V5&gt;V4V1 -&gt; V2 -&gt; V3 -&gt; V5-&gt; V4.

    img

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

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

    构造哈密顿路: V1&gt;V2&gt;V3&gt;V5&gt;V4V1 -&gt; V2 -&gt; V3 -&gt; V5-&gt; V4.

    img

    (还是举一个吧~~~)

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

    同样最后一位为1,代表存在&lt;Vi,V5&gt;&lt;Vi, V5&gt;且i=4(最后一位)

    则构造哈密顿路:V1&gt;V2&gt;V3&gt;V4&gt;V5V1 -&gt; V2 -&gt; V3 -&gt; V4 -&gt; 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),因为存在弧&lt;V1,V3&gt;&lt;V1, V3&gt;&lt;V3,V2&gt;&lt;V3, V2&gt;.这里需要注意下.

    #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':' ');   
    }
    

    .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’:’ ');
    }

    
    
    展开全文
  • 四正则连环图的哈密顿图性质研究及其判定的多项式算法,宁安琪,宁宣熙,在本文中定义了一般四正则连环图,并讨论了它的哈密顿图性质。研究表明,并非在全部四正则连环图中都存在哈密顿圈。研究了几种存
  • 第15章欧拉图与哈密顿图 15.1 欧拉图 1、通过图中所有边仅一次的通路称作欧拉通路。通过图中所有边仅一次的回路称作欧拉回路。具有欧拉回路的图是欧拉图,仅具有欧拉通路的图是半欧拉图。平凡图(只含一个顶点的图)...

    教材:《离散数学》第2版 屈婉玲 耿素云 张立昂 高等教育出版社
    源文档高清截图在最后

    第15章欧拉图与哈密顿图

    15.1 欧拉图

    1、通过图中所有边仅一次的通路称作欧拉通路。通过图中所有边仅一次的回路称作欧拉回路。具有欧拉回路的图是欧拉图,仅具有欧拉通路的图是半欧拉图。平凡图(只含一个顶点的图)是欧拉图。

    2、无向图G是欧拉图,当且仅当G是连通图且没有奇度顶点。
    证明 若G为平凡图,显然成立。设该图G(V, E)为非平凡图,具有m条边和n个顶点。
    必要性(左推右)。因为G为欧拉图,所以G存在欧拉回路C。对任意vi, vj∈V,vi, vj都在C上。因而vi, vj连通,G为连通图。对任意vi∈V,vi在C上每出现一次就获得两个度(一个入度和一个出度),而所有顶点都会出现在C中至少一次,于是G中无奇度顶点。
    充分性(右推左)。由于G为非平凡的连通图,边数m≥1,下面对m作归纳证明。
    m = 1时,因为G没有奇度顶点,但G又是连通的,所以G只能是一个环。G为欧拉图。
    如果m≤k(k≥1)时结论都成立,那么m = k + 1时结论也要成立。由于G的连通性且无奇度顶点,G的最小度δ(G)≥2。可以证明G中必含圈。设C为G中的一个圈,将删除C中的全部边以后剩下的部分记为G的一个生成子图G’。设G’有s个连通分量G1’、G2’、……、Gs’,其中每个连通分量最多有k条边,且无奇度顶点。设Gi’与C的公共顶点为在这里插入图片描述,i = 1,2,……,s。由归纳假设,G1’、G2’、……、Gs’都是欧拉图,它们都存在欧拉回路。设Ci是Gi’的一条欧拉回路,i = 1,2,……,s。从某个顶点vr开始沿C行走,遇到在这里插入图片描述就行遍Ci,回到在这里插入图片描述继续沿C行走,最后回到vr。于是,走过的这条回路借由G的生成子图G的每个连通分量与G的一条回路C的全部公共顶点,经过了生成子图G’和C的全部边仅一次(因为在连通分量中走的都是欧拉回路),可见走过的这条回路就是G中的欧拉回路,G为欧拉图。
    上述充分性证明是构造性证明,提供了一种求欧拉回路的算法:逐步插入回路法。
    在这里插入图片描述

    3、哥尼斯堡七桥问题的内容是:一个人如何不重复地走完7座给定的桥(如下图),回到出发地点。显然,要对该问题求解就是要求解该图中的一个欧拉回路。但是这个图有4个奇度顶点,所以无解。
    在这里插入图片描述

    4、无向图G是半欧拉图,当且仅当G是连通的且恰有2个奇度顶点。
    证明 必要性(左推右)。设该图G(V, E)是m条边的n阶无向图。因为G为半欧拉图,所以G存在欧拉通路但不存在欧拉回路。设该欧拉通路为Γ = vi0ej1vi1ej2…ejmvim,且vi0≠vim。根据欧拉图的定义,G是连通的。对任意v∈V,如果v不是Γ的端点,设其出现k次,那么就有v的度d(v) = 2k。如果v是Γ的端点,由于两个端点不同且不相邻,v作为端点就只能出现1次,获得1度。当v是端点时,它还可能作为非端点继续出现若干次,每次获得2度。所以d(v)是奇数。
    充分性(右推左)。设G的两个奇度顶点u、v,对G加新边(u, v),得G’ = G∪(u, v)。则G连通且无奇度顶点。于是G为欧拉图,存在欧拉回路C’。C = C’ – (u, v)就是G中的欧拉通路,G为欧拉图。

    5、对有向图,可类似证明定理:
    【1】有向图D是欧拉图,当且仅当D是强连通的,且每个顶点的入度等于出度。
    【2】有向图D是半欧拉图,当且仅当D是单向连通的,且恰有两个奇度顶点:其中一个顶点的入度比出度大1,另一个的出度比入度大1,其余顶点的入度等于出度。

    6、G是非平凡的欧拉图,当且仅当G是连通的,且是若干个边不重的圈的并图。
    可用归纳法证明。

    7、设G是非平凡的欧拉图,则G的边连通度λ(G)≥2。
    证明 只需证明G不是1边-连通图。即证G的任意一条边e都不是桥(割边,去掉该边后图不再连通)。设C是一条欧拉回路,那么e在C上,且G – e的连通分支(连通分量)数p(G – e) = p(G),故e不是桥。

    8、Fleury算法
    用途:求欧拉回路。
    基本思想:能不走桥就不走桥。
    输入:欧拉图G(V, E)。
    1、任取v0∈V,记P0 = v0,i = 0。
    2、设Pi = v0e1v1e2…eivi,如果E – {e1,e2,……,ei}没有与vi关联的边,计算停止。否则,按下述条件从E – {e1,e2,……,ei}中任取边ei+1:
    (a) ei+1与vi关联;
    (b)除非没有别的边可以选择,否则不应该为Gi = G – {e1,e2,……,ei}中的桥。
    3、i = i + 1,返回到第2步。
    算法停止时,得到的简单回路Pm = v0e1v1e2…emvm为G的一条欧拉回路。

    15.2 哈密顿图

    1、经过图的所有顶点仅一次的通路称为哈密顿通路,经过图中所有顶点仅一次的回路称作哈密顿回路。具有哈密顿回路的图称作哈密顿图,具有哈密顿通路但不具有哈密顿回路的图称作半哈密顿图。
    (从起点出发和到达终点不算经过)
    平凡图是哈密顿图。目前人们还没有找到便于判断哈密顿图的充分必要条件。

    2、设无向图G(V, E)是哈密顿图,则对任意的非空集在这里插入图片描述,均有p(G – V1)≤|V1|。
    证明 设C为G中的一条哈密顿回路。易知,当V1中的点在C上均不相邻(虽然V1的点都在C上,但两两不由一条边直连)时,p(C – V1)达到最大值|V1|(连通分量最大,即分成了尽可能多的互不连通的子图。删掉V1及其关联的边后,最多可以构造出|V1|个互不连通的子图。一种构造方法是:从起点开始依次给点编号(0或1开始均可),V1是全部编号为奇数的点)。而当V1的点在C上存在相邻情况时,总有p(C – V1) < |V1|。所以p(C – V1)≤|V1|。C是G的生成子图,所以p(G – V1)≤p(C – V1)≤|V1|。
    本定理给出的是判定一个图是哈密顿图的必要条件,而不是充分条件。Peterson图满足该条件,但它不是哈密顿图。
    推论 设无向图G(V, E)是半哈密顿图,则则对任意的非空集在这里插入图片描述,均有p(G – V1)≤|V1| + 1。
    证明 设P是G中从u到v的哈密顿通路,G’为在u,v之间加新边e得到的图,易知添加该边以后哈密顿通路变成哈密顿回路,G’为哈密顿图。于是p(G’ – V1)≤|V1|。而p(G – V1) = p(G’ – V1 – e)≤p(G’ – V1) + 1≤|V1| + 1。(提示:G – V1和G’ – V1 – e是完全相同的图,G’ – V1去掉e后可能会因为e是割边(桥)从而连通分量数 + 1)

    3、设G是n阶无向简单图,若对G中任意不相邻顶点u,v,均有d(u) + d(v)≥n – 1,则G中存在哈密顿通路。
    证明 (我也没搞懂,日后再更)一个图是哈密顿图首先要是连通图。设G不连通,则G至少有2个连通分量G1、G2。设u、v分别是G1、G2的一个顶点,因为G是简单图,所以在这里插入图片描述(一个点的度最大的情况是该点与图中其它点都有边直连),矛盾,所以G是连通图。
    下面证明G中存在哈密顿通路。设Γ = v1v2…vl为G中的一条极大路径,即Γ的起点与终点都不与Γ外的顶点相邻,l≤n。
    (1)若l = n,则Γ就是G中的哈密顿通路,定理成立。
    (2)若l < n,则G存在Γ外的顶点,要证明G中存在过Γ上所有顶点的圈:
    【a】若v1与vl相邻,则Γ∪(v1, vl)就是这个圈。
    【b】若v1与vl不相邻,设v1与Γ上的vi1 = v2,vi2,……,vik相邻(k≥2,否则d(v1) + d(vl)≤1 + l – 2≤l – 1 < n – 1,与已知条件d(u) + d(v)≥n – 1不符。因为l < n,所以d(vl)≤l – 2,因为vl至少与1个点不相邻)。vl至少与vi2,vi3,……,vik相邻的顶点在这里插入图片描述之一相邻(否则d(v1) + d(vl)≤k + l – 2 – (k – 1) = l – 1 < n – 1,与已知条件d(u) + d(v)≥n – 1不符)。设vl与在这里插入图片描述相邻(2≤r≤k),于是回路在这里插入图片描述经过Γ上的所有顶点。
    【c】下面证明存在比Γ更长的路径。因为l < n,所以C外还有顶点。由G是连通的,得存在vi+1∈V(G) – V©与C上的某个顶点vt相邻,当t < ir – 1时,删除边(vt-1, vt)得路径在这里插入图片描述比Γ的长度大1。当t≥ir – 1时,可类似构造出比Γ的长度大1的路径Γ’。重复【a】到【c】,在有限步内一定可以得到G的一条哈密顿通路。
    在这里插入图片描述
    推论 设G为不少于3阶的无向简单图,若对于G中任意两个不相邻顶点u,v均有d(u) + d(v)≥n,则G中存在哈密顿回路。
    证明 由上述定理,G中存在一条哈密顿通路Γ = v1v2…vn。若v1与vn相邻,就将这条边e添加到Γ中,就得到G的一条哈密顿回路Γ∪e。若不相邻,可以仿照上述的证明方法证明存在过Γ上各个顶点的圈,此圈就是哈密顿回路。

    4、设u、v为n阶无向简单图G的两个不相邻顶点,且d(u) + d(v)≥n,则G为哈密顿图,当且仅当G∪(u, v)是哈密顿图,其中(u, v)是添加的新边。

    5、不低于2阶的竞赛图都有哈密顿通路。
    回忆:若有向图D的基图(有向边全部改成无向边后的图)为n阶无向完全图,就称D为n阶竞赛图。
    证明 设D为n阶竞赛图,对n归纳证明。
    当n = 2时,D的基图是二阶完全图K2,结论成立。
    设n = k时结论成立,那么n = k + 1时结论也要成立。设V(D) = {v1, v2, …, vk, vk+1},记D1 = D – vk+1,易知D1为k阶竞赛图。由归纳假设,D1存在哈密顿通路Γ1 = v1’v2’…vk’。下面,需要证明vk+1可以加入Γ 1中。若存在vr’(1≤r≤k)使(vi’, vk+1)、(vk+1, vr’)∈E(D),i = 1,2,……,r – 1。则可以得到哈密顿通路Γ = v1’v2’…vr-1’vk+1vr’…vk’。若不存在,则任意i = 1,2,……,k,均有(vi’, vk+1)∈E(D),则可以得到哈密顿通路Γ = v1’v2’…vk’vk+1。
    在这里插入图片描述在这里插入图片描述在这里插入图片描述在这里插入图片描述在这里插入图片描述在这里插入图片描述在这里插入图片描述

    展开全文
  • 欧拉图与哈密顿图

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

    2019-02-19 01:08:45
    存在性判定 欧拉回路:从图中某一顶点出发,所有边仅经过一次,最后回到该...哈密顿图:哈密顿路经过图的所有顶点一次且仅仅一次。 存在哈密顿回路的图称为哈密顿图。 在n阶简单图中,若任一对不相邻顶点(u, v)有d...
  • 目录石墨笔记 PPT版1 二部图 偶图 双图 二分图 Ks,t G(V1,V2,E)2 欧拉图3 哈密顿图4 平面图欧拉公式推论: n-m+r = k+1m <=3n-6是平面图的必要条件m <= ((k-2)/k )*(n-2)是平面图的必要条件库拉图斯基定理: ...
  • 6.3 哈密顿图 注意: 平凡图是哈密顿图 每个结点都过,每个结点只过一次。(有的边可以不过) 不像欧拉图,哈密顿图我们至今未找到判断的充分必要条件。下面我们来列举一些充分条件和必要条件。 必要条件: 例题...
  • 哈密顿图判断 输入一个具有n个顶点的无向图G,判断G是否有哈密尔顿回路。(哈密顿回路问题,建议使用递归解决)
  • 哈密顿圈自组织算法的实证研究结果及其在哈密顿图判定上的应用,宁宣熙,宁安琪,本文首先介绍了SOA算法在大约12000个规模不同(n=10-4000,m=20-8000)的一般任意图中构造哈密顿圈的实证研究结果,验证了SOA算法的...
  • 证明连通简单图是哈密顿图

    千次阅读 2018-07-16 21:44:33
    定理 对于v阶无向简单图,如果对于图中任意两点的度数之和都大于等于顶点数,那么该图就是哈密顿图
  • 哈密顿图 数学建模

    2011-07-11 21:46:40
    哈密顿图 数学建模```````````````````
  • 欧拉图,哈密顿图

    2016-01-28 11:46:01
    欧拉图: 半欧拉图: ...哈密顿图: 半哈密顿图: 一笔画问题:http://acm.nyist.net/JudgeOnline/problem.php?pid=42 AC代码: #include//c++ #include//数学公式 #include//malloc #include #i
  • 哈密顿图与半哈密顿图前言一、半/哈密顿图定义二、半/哈密顿图的必要条件三、判别二部图是否为哈密顿图四、判断哈密顿路的充分条件五、图的闭包、竞赛图六、哈密顿图的充要条件七、旅行商问题 前言 提示:本文主要...
  • 竞赛图 哈密顿图

    2020-02-27 16:07:59
    竞赛 竞赛是通过在无向完整中为每个边缘分配方向而获得的...与哈密顿路径的关系 任何有限数量n个顶点的竞赛都包含一个哈密尔顿路径,即所有n个顶点上的直线路径。假设该语句适用于n,并考虑n + 1个顶点上的...
  • 图论(四)欧拉图与哈密顿图

    千次阅读 2019-01-04 16:21:48
    文章目录欧拉图哈密顿图应用中国邮递员问题旅行售货员问题 欧拉图 欧拉图:遍历每一条边恰好再回到出发点 多重图:图是没有多重边的多重图 图G是欧拉图当且仅当G是联通的且每个结点的度为偶数 连通图G是...
  • 哈密顿图 poj 1776

    2017-05-04 17:00:49
    哈密顿图解析:http://blog.csdn.net/pi9nc/article/details/9219971 #include #include using namespace std; #define maxn 1010 bool graph[maxn][maxn]; int next[maxn]; int head, n; char str[maxn ]; int...
  • 哈密顿图的判断需求分析详细设计程序流程图测试数据 需求分析   经过图中的每个顶点一次且仅一次的通路称为哈密顿通路,经过图中每个顶点一次且仅一次的回路称为哈密顿回路,具有哈密顿回路的图称为哈密顿图,具有...
  • 2. 哈密顿图的定义(哈密顿通路、哈密顿回路) 3. 哈密顿图的必要条件及其推论及推论的应用 4. 证明不存在哈密顿回路 5. 哈密顿图的充分条件 6. 哈密顿图的其他判定方法 方法1: ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 893
精华内容 357
关键字:

哈密顿图