精华内容
下载资源
问答
  • 哈密顿图判断 输入一个具有n个顶点的无向图G,判断G是否有哈密尔顿回路。(哈密顿回路问题,建议使用递归解决)
  • 哈密顿图

    2019-08-23 21:23:25
  • 哈密顿图的判定问题是一个NP完全问题,是图论理论中尚未解决的主要问题之一。1968年,Grinberg证明了一个必要条件,提高了判定非哈密顿可平面图的效率,由此产生了很多3-正则3-连通非哈密顿可平面图的研究成果。根据...
  • 四正则连环图的哈密顿图性质研究及其判定的多项式算法,宁安琪,宁宣熙,在本文中定义了一般四正则连环图,并讨论了它的哈密顿图性质。研究表明,并非在全部四正则连环图中都存在哈密顿圈。研究了几种存
  •  哈密顿图:图G的一个回路,若它通过图的每一个节点一次,且仅一次,(那么,问题来了,既然要回到起始点,是不是应该说除了起点以外的点通过一次且仅一次,而起点这个点,作为哈密顿回路的时候需要两次到达)就是...

    概念:

      哈密顿图:图G的一个回路,若它通过图的每一个节点一次,且仅一次,(那么,问题来了,既然要回到起始点,是不是应该说除了起点以外的点通过一次且仅一次,而起点这个点,作为哈密顿回路的时候需要两次到达)就是哈密顿回路.存在哈密顿回路的图就是哈密顿图.哈密顿图就是从一点出发,经过所有的必须且只能一次,最终回到起点的路径.图中有的边可以不经过,但是不会有边被经过两次.

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

    判定:

    一:Dirac定理(充分条件)

      设一个无向图中有N个顶点,若所有顶点的度数大于等于N/2,则哈密顿回路一定存在.(N/2指的是⌈N/2⌉,向上取整),用\frac{N + 1}{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 -> S,即形成了一个回路.

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

    证明:

      可利用鸽巢原理(抽屉原理)证明.

    抽屉原理

    原理1: 把多于n+1个的物体放到n个抽屉里,则至少有一个抽屉里的东西不少于两件。

    证明(反证法):如果每个抽屉至多只能放进一个物体,那么物体的总数至多是n×1,而不是题设的n+k(k≥1),故不可能。

    原理2:把多于mn(m乘n)+1(n不为0)个的物体放到n个抽屉里,则至少有一个抽屉里有不少于(m+1)的物体。

    证明(反证法):若每个抽屉至多放进m个物体,那么n个抽屉至多放进mn个物体,与题设不符,故不可能。

    原理3:把无数还多件物体放入n个抽屉,则至少有一个抽屉里有无数个物体。

    原理1 、2 、3都是第一抽屉原理的表述 [2]  。

    第二抽屉原理

    把(mn-1)个物体放入n个抽屉中,其中必有一个抽屉中至多有(m—1)个物体(例如,将3×5-1=14个物体放入5个抽屉中,则必定有一个抽屉中的物体数少于等于3-1=2)。

    伪代码:

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

     

    哈密顿通路

    二: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 <cstdio>
    #include <cmath>
    #include <string>
    #include <cstring>
    #include <algorithm>
    #include <limits>
    #include <vector>
    #include <stack>
    #include <queue>
    #include <set>
    #include <map>
    #include <bitset>
    #include <unordered_map>
    #include <unordered_set>
    #define lowbit(x) ( x&(-x) )
    #define pi 3.141592653589793
    #define e 2.718281828459045
    #define INF 0x3f3f3f3f
    #define HalF (l + r)>>1
    #define lsn rt<<1
    #define rsn rt<<1|1
    #define Lson lsn, l, mid
    #define Rson rsn, mid+1, r
    #define QL Lson, ql, qr
    #define QR Rson, ql, qr
    #define myself rt, l, r
    using namespace std;
    typedef unsigned long long ull;
    typedef unsigned int uit;
    typedef long long ll;
    const int maxN = 1e2 + 7;
    int ans[maxN], mp[maxN][maxN], N;
    inline void Insert(int &len, int l, int r)    //The ans[] length is len, insert key befor arv[index]
    {
        len++;
        for(int i=r; i>=l; i--)
        {
            ans[i + 1] = ans[i];
        }
        ans[l] = len;
    }
    void Hamilton()
    {
        int have_node = 0;
        ans[++have_node] = 1;
        for(int i = 2; i <= N; i++) //插入点i
        {
            if(mp[ans[have_node]][i]) ans[++have_node] = i; //第一种情况,直接把当前点添加到序列末尾
            else
            {
                bool flag = false;
                for(int j = have_node - 1; j; j--)   //在当前序列中,从后往前找到第一个满足条件的点j,使得存在<Vj,Vi>且<Vi, Vj+1>.
                {
                    if(mp[ans[j]][i])  //找到后把该点插入到序列的第j + 1个点前.
                    {
                        flag = true;
                        Insert(have_node, j + 1, have_node);
                        break;
                    }
                }
                if(!flag) Insert(have_node, 1, have_node);    //否则说明所有点都邻接自点i,则把该点直接插入到序列首端.
            }
        }
    }
    
    int main()
    {
        int t; scanf("%d", &t);
        while(t--)
        {
            scanf("%d", &N);
            memset(mp, 0, sizeof(mp));
            int M = N * (N - 1) / 2;
            for(int i = 0; i < M; i++)
            {
                int u, v;
                scanf("%d%d", &u, &v);
                mp[u][v] = 1;
            }
            Hamilton();
            for(int i = 1; i <= N; i++) printf(i == 1 ? "%d":" %d", ans[i]);
            printf("\n");
        }
        return 0;
    }
    

     

    展开全文
  • 竞赛图 哈密顿图

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

    竞赛图

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

    • 总的概括就是一个有向完全图

    与哈密顿路径的关系

    任何有限数量n个顶点的竞赛图都包含一个哈密尔顿路径,即所有n个顶点上的直线路径。假设该语句适用于n,并考虑n + 1个顶点上的任何竞赛图T。 选择T的顶点v0,并考虑 的一个有向路径 。现在让 是最大的,所以对于每个 都有一个从 到 的有向边。

    哈密顿图

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

    • 哈密顿回路:G中经过每个顶点一次且仅一次的回路(通路基础上+回到起始点)称作哈密顿回路

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

    定义

    (1)存在哈密顿通路(回路)的图一定是连通图;
    (2)哈密顿通路是初级通路,哈密顿回路是初级回路;
    (3)若G中存在哈密顿回路,则它一定存在哈密顿通路,反之不真(看课本的话,是必要条件,而不是充分条件,故不可反推!)
    (4)只有哈密顿通路,无哈密顿回路的图不叫哈密顿图;即,哈密顿图是回路

    判定
    (1)设无向图 G = < V , E > G=<V,E> G=<V,E> 为哈密顿图, V 1 V1 V1 V V V的任意真子集,则 p ( G − V 1 ) < = ∣ V 1 ∣ p(G-V1)<=|V1| p(GV1)<=V1

    其中, p ( G − V 1 ) p(G-V1) p(GV1) G G G 中删除 V 1 V1 V1 后的所得图的联通分支数目, ∣ V 1 ∣ |V1| V1 V 1 V1 V1 集合中包含的顶点个数。

    【哈密顿图存在的必要条件】推论:有割点的图一定不是哈密顿图。

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

    好理解的吧,就是过去就过不来了,毕竟两块之间只有一条桥嘛。

    (2)设 G G G n ( n > = 3 ) n(n>=3) n(n>=3) 阶无向简单图,若对于 G G G 中的每一对不相邻的顶点 u , v u,v u,v ,均有 d ( u ) + d ( v ) > = n − 1 d(u)+d(v)>=n-1 d(u)+d(v)>=n1 G G G 中存在哈密顿通路。又若 d ( u ) + d ( v ) > = n d(u)+d(v)>=n d(u)+d(v)>=n G G G 中存在哈密顿回路,即 G G G 为哈密顿图。

    【哈密顿图存在的充分条件,不是必要条件】其中d(u),d(v)分别代表顶点u,v的度数。

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

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

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

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

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

    • 若能通过观察找出图G中的一条哈密顿回路,则G当然是哈密顿图。
    • 若一个无向图G满足上述(2)中的条件,一个有向图D满足上述(3)的推论的条件,则G、D都是哈密顿图。

    一道找哈密顿路径的例题

    链接 https://nanti.jisuanke.com/t/43394

    题意

    给出一个 n ( n ≤ 500 ) n(n ≤ 500) n(n500) 个点的有向图,任意两个点之间有且仅一条有向边。
    求一条不重复经过一个点的最长的简单路径。

    做法

    任意两个点之间有且仅一条有向边,这是一个竞赛图。
    竞赛图一定存在哈密顿路径,所以𝑛个点的竞赛图的不重复经过一个点的最长的简单路径的长度为𝑛。

    我们可以根据如下方法构造一条哈密顿路径:

    维护一个 list,整个 list 相当于当前维护的路径。

    • 每次加入一个点𝑢, 若𝑢连向 list 中的所有点,则把𝑢加入 list 的头部。
    • 若 list 中的所有点连向𝑢,则把𝑢加入 list 的尾部。
    • 否则,list 维护的路径中一定存在一条边< 𝑣, 𝑤 >,且存在边< 𝑣, 𝑢 >, < 𝑢, 𝑤 >,于是把𝑢插入至𝑣和𝑤之间。

    时间复杂度 O ( N 2 ) O(N^2) O(N2)

    #include<bits/stdc++.h>
    #define rep(i,a,b) for(int i = (int)a;i<=(int)b;i++)
    #define pb push_back
    using namespace std;
    const int maxn=505;
    typedef long long ll;
    typedef pair<int,int> pii;
    
    list<int> L;
    int mp[maxn][maxn];
    int n;
    
    int main(){
        int T; scanf("%d",&T);
        while(T--){
            scanf("%d",&n);
            rep(i,1,n)rep(j,1,n) scanf("%d",&mp[i][j]);
            L.clear();
            L.push_front(1);
            rep(i,2,n){
                int Ci=0,Co=0;
                for(auto x:L){
                    if(mp[x][i]) Co++;
                    if(mp[i][x]) Ci++;
                }
                if(Co==i-1) L.push_back(i);
                else if(Ci==i-1) L.push_front(i);
                else {
                    auto pre=L.begin();
                    for(;pre!=L.end();pre++){
                        auto lat=pre; lat++;
                        if(lat==L.end()) break;
                        int p=*pre,l=*lat;
                        if(mp[p][i]&&mp[i][l]) break;
                    }
                    L.insert(++pre,i);
                }
            }
            int f=0;
            for(auto x: L){
                if(f) printf(" ");
                f=1;
                printf("%d",x);
            }
            printf("\n");
        }
        return 0;
    }
    
    展开全文
  • 哈密顿图与半哈密顿图前言一、半/哈密顿图定义二、半/哈密顿图的必要条件三、判别二部图是否为哈密顿图四、判断哈密顿路的充分条件五、图的闭包、竞赛图六、哈密顿图的充要条件七、旅行商问题 前言 提示:本文主要...

    前言

    提示:本文主要介绍哈密顿图和半哈密顿图的定义以及判定条件,文中的图片来源于杨映雪老师的ppt。


    一、半/哈密顿图定义

    1.哈密顿路:给定无向图G中,通过图中每个结点一次而且仅一次的路径
    2.哈密顿回路:给定无向图G中,通过图中每个结点一次而且仅一次的回路
    3.哈密顿图:具有哈密顿回路的图。
    4.半哈密顿图:有哈密顿路径而没有哈密顿回路的图。哈密尔顿图和半哈密尔顿图是连通图。
    哈密顿图和欧拉图联系:两者都是遍历问题,但是欧拉图考虑的是边,而哈密顿考虑的是结点。同时判定欧拉图具有充要条件。但是哈密顿图没有简单的充要条件,只有必要条件和充分条件。

    二、半/哈密顿图的必要条件

    必要条件用于判定一个图不是半/哈密顿图。(p59)

    定理1.设无向图G=<V,E>是哈密顿图,S是V的任意的非空真子集, ==w(G-S)≤|S| ==其中,w(G-S)为从G中删除S(删除S中各顶点及关联的边)后所得到的图的连通分支数。

    证明:设C是G的一条哈密顿回路,C是G的子图,在回路C中每删去S的一个结点,最多增加一个连通分支,且删去S中的第一结点时分支数不变,所以有w(C-S)≤|S|。又因为C是G的生成子图,所有C-S是G-S的生成子图,且w(G-S)≤w(C-S),因此w(G-S)≤|S|

    推论:设无向图G=<V,E>是半哈密顿图,则对于结点集V的任意非空真子集S均有w(G-S)≤|S| +1

    证明:设P是G中起始于u终止于v的哈密顿图,令G’=G∪(u,v) (在G的结点u,v之间添加新边),易知G’为哈密顿图。所以有 w(G-S)≤|S| ,则:
    w(G-S) = w(G’ - S - (u,v) ) ≤ w(G’-S) + 1 ≤ |S| +1

    三、判别二部图是否为哈密顿图

    一般情况下,设二部图G(V1,V2,E),|V1|≤|V2|,且|V1|≥2,|V2|≥2,由上述定理以及推论有:
    1.若G是哈密顿图,则|V1| = |V2|;
    2.图G是半哈密顿图,则|V2| = |V1| +1
    3.若|V2| ≥ |V1| +2,则图G既不是哈密顿图,也不是半哈密顿图。

    四、判断哈密顿路的充分条件

    定理2:无向简单图G中任意两个不相邻的 结点度数之和 ≥ n-1,则图G中存在一条哈密顿路。图G是半哈密顿图。

    例题2

    定理3:图G具有n个结点的无向简单图,如果图G中任意一对不相邻结点的度数之和 ≥ n,则G是哈密顿图

    证明:由上述定理2知,图G一定是半哈密顿图,即存在一条哈密顿路F = V1V2V3…Vn。如果V1和Vn相邻,则F是哈密顿回路。如果不相邻,由定理2可知图G一定存在一条包含V1V2V3…Vn的回路,这个回路是哈密顿回路。所有图G是哈密顿图。

    例题

    五、图的闭包、竞赛图

    闭包:

    竞赛图

    竞赛图中每对不同的顶点通过单个有向边连接,即每对顶点间都有一条有向边。设 D 为 n 阶有向简单图,若 D 的基图为 n 阶无向完全图,则 D 为 n 阶竞赛图。简单来说,竞赛图就是将完全无向图的无向边给定了方向

    六、哈密顿图的充要条件




    七、旅行商问题

    展开全文
  • 欧拉图&哈密顿图详解

    千次阅读 多人点赞 2019-07-26 18:00:29
    存在欧拉回路的无向被称为欧拉图。 有欧拉通路,但无欧拉回路的被称为半欧拉图。 欧拉回路:若存在一条从起点S出发的路径,每条边恰好只走一次,最终回到起点S。 欧拉路径:若存在一条从起点S出发的路径,经过...
  • 知识点 - 哈密顿图

    千次阅读 2019-08-16 21:38:12
    知识点 - 哈密顿图 解决问题类型: 对于顶点个数大于2的图,如果图中任意两点度的和大于或等于顶点总数,那这个图一定是哈密顿图。闭合的哈密顿路径称作哈密顿圈,含有图中所有顶点的路径称作哈密顿路径。 哈密顿图:...
  • 哈密顿图的判断需求分析详细设计程序流程图测试数据 需求分析   经过图中的每个顶点一次且仅一次的通路称为哈密顿通路,经过图中每个顶点一次且仅一次的回路称为哈密顿回路,具有哈密顿回路的图称为哈密顿图,具有...
  • 目录石墨笔记 PPT版1 二部图 偶图 双图 二分图 Ks,t G(V1,V2,E)2 欧拉图3 哈密顿图4 平面图欧拉公式推论: n-m+r = k+1m <=3n-6是平面图的必要条件m <= ((k-2)/k )*(n-2)是平面图的必要条件库拉图斯基定理: ...
  • 欧拉图和哈密顿图

    2019-09-04 00:06:27
    哈密顿图 Dirac定理: 无向图,有 N 个节点,若所有节点的度数都大于等于 N/2,则哈密顿回路一定存在。注意,“N/2” 中的除法不是整除,而是实数除法。如果 N 是偶数,当然没有歧义;如果 N 是奇数,则该条件中...
  • 哈密顿图 哈密顿图 是一个无向图,由天文学家哈密顿提出。 由指定的起点前往指定的终点,途中经过所有其他节点且只经过一次。 在图论中是指含有哈密顿回路的图。 哈密顿路径 G=(V,E)是一个图,若G中一条路径通过...
  • 欧拉图与哈密顿图

    2021-03-17 15:25:36
    如果G中的一条通路经过中的每一条边且不重复,则该通路称为欧拉通路 若欧拉通路为回路,则称为欧拉回路 具有欧拉回路的称为欧拉图 定理1:无向G具有欧拉通路,当且仅当G连通且无奇度顶点,或只有两个点度...
  • 题目:哈密顿通路是指,在一个无向图中,存在一条经过图中每一个点,且仅经过一次的通路,若这条通路形成了闭合回路,则称这条回路为哈密顿回路,存在哈密顿回路的图称为哈密顿图。现给出无向图G的边,要求判断无向...
  • &nbsp; &nbsp;&nbsp;相关定义:设G=&lt;V,E&gt;为一图(无向的或有向的).G中经过...若G中存在哈密顿回路,则称G为哈密顿图。 &nbsp; &nbsp;(只是根据自己的体会总结的,因为是初学者,有...
  • 证明连通简单图是哈密顿图

    千次阅读 2018-07-16 21:44:33
    定理 对于v阶无向简单图,如果对于图中任意两点的度数之和都大于等于顶点数,那么该图就是哈密顿图
  • 6.3 哈密顿图 注意: 平凡图是哈密顿图 每个结点都过,每个结点只过一次。(有的边可以不过) 不像欧拉图,哈密顿图我们至今未找到判断的充分必要条件。下面我们来列举一些充分条件和必要条件。 必要条件: 例题...
  • 第15章欧拉图与哈密顿图 15.1 欧拉图 1、通过图中所有边仅一次的通路称作欧拉通路。通过图中所有边仅一次的回路称作欧拉回路。具有欧拉回路的图是欧拉图,仅具有欧拉通路的图是半欧拉图。平凡图(只含一个顶点的图)...
  • 离散数学-图论-哈密顿图及其应用

    千次阅读 2019-09-22 07:18:00
    哈密顿图 一、定义概念 1.哈密顿通路 设G=<V,E>为一图(无向图或有向图).G中经过每个顶点一次且仅一次的通路称作哈密顿通路 2.哈密顿回路 G中经过每个顶点一次且仅一次的回路(通路基础上+回到起始点...
  • 我的机器学习教程「美团」算法工程师带你入门机器学习 以及 「三分钟系列」数据结构与算法 已经开始更新了,欢迎大家订阅~这篇专栏整合了这几年的算法知识,简单易懂,也将是我实体书的BLOG版...1.哈密顿通路 设G=...
  • 哈密顿图和欧拉图知识小结

    千次阅读 2017-08-02 20:56:46
    哈密顿图的判定是世界级难题。 设G是n阶无向简单图,若对于G中任意不相邻的顶点u、v,均有d(u)+d(v)>=n-1,则说明G中存在哈密顿通路。 不过,这个条件只是充分条件,而不是必要条件。 也就是说,满足该条件一定存在...
  • 哈密顿圈自组织算法的实证研究结果及其在哈密顿图判定上的应用,宁宣熙,宁安琪,本文首先介绍了SOA算法在大约12000个规模不同(n=10-4000,m=20-8000)的一般任意图中构造哈密顿圈的实证研究结果,验证了SOA算法的...
  • 回溯搜索方法和路径扩展方法是判定无向哈密顿图的两种重要途径,其缺点是要么进行路径选择的回溯,从而造成指数阶时间开销,要么由于剪枝技术而遗漏正确答案。任何一个无向哈密顿圈总是可以分解成若干个原子圈,这些原子...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 7,170
精华内容 2,868
关键字:

哈密顿图