精华内容
下载资源
问答
  • 至此的信息提取完成,只需将坐标信息转换成邻接矩阵表示的,再利用以下的递归求解算法便可计算出通路。 递归求解算法如下,核心代码不超过15行: def find_path ( self , optimize = True ) : ...

    一个自动闯关的脚本,不知道你有没有玩过这种一笔从头滑到尾的游戏
    可从头条搜索下载,但是个骗人的app,金币根本无法提现

    自动化脚本总共分为三个部分:
    
    • 提取图片信息,转换为 无向图 的邻接矩阵
    • 根据邻接矩阵利用DFS+回溯,递归求解通路(暴力求解,在这种小规模情况下python程序可以在2秒内求出一条有效通路)
    • 将通路路径转化为坐标点,利用adb操作手机进行模拟点击

    技术难点主要在于提取图片中的信息,如何准确识别出图片中的灰色方块和起点方块,并转化成可处理的数据。信息提取这个过程占据了我开发精力的80%,想了很多办法,最后无意中发现了cv2的一些图片处理的功能才迎刃而解。下面简单介绍一下方块信息提取的思路。

    • 首先需要将无关区域去掉,只保留中间连线区域(如下图),使问题简单化,需要根据手机的屏幕尺寸进行处理(参数我都在config.json文件中进行了说明)
      截取中间部分
    • 随后对区域进行灰度和二值化处理,可以简单理解为先将彩色图片处理为只有灰度的图片,然后寻找一个灰度的阀值将图片转换成只有白色和黑色的图片,处理结果如下
      二值化后的图片
    • 利用OpenCV的求轮廓算法cv2.findContours(),将方块包含坐标点的轮廓数据求出,此步骤可以实现最关键的将图形中的方块位置转化成可处理的数据信息。求轮廓前还需对一些细节进行处理,比如去掉尾巴和胡须,以免对结果产生干扰,比如上图倒数第二个起点方块的尾巴部分就和其他方块连接在了一起,需要提前将连通区域断开,方法也很简单。
      轮廓图
    • 利用boundingRect求出每个轮廓的外接矩形,可确定每个方块中心点的坐标,利用contourArea求出每个轮廓的面积可确定图的起点。

    至此图的信息提取完成,只需将坐标信息转换成邻接矩阵表示的图,再利用以下的递归求解算法便可计算出图的通路。
    在这里插入图片描述

    递归求解算法如下,核心代码不超过15行:

        def find_path(self, optimize=True):
            """
            dfs+回溯 递归求解
            :param optimize: 是否对最终结果进行优化,优化可有效减少滑动次数,但模拟滑动操作可能会不稳定
            :return:
            """
            current = time.time() * 1000
            visited = []
            visited.append( self.blocks[self.begin_index])
            self.find_path_fun(visited, self.blocks[self.begin_index])
            path = []
            for item in visited:
                path.append((item.center[0], item.center[1]))
            print("求解耗时 %d ms" % (time.time()*1000 - current,))
            return path if not optimize else self.optimize_path(path)
    
        def find_path_fun(self, visited, start):
            for item in self.matrix[self.block_map[start]]:
                if item is not None and item not in visited:
                    visited.append(item)
                    if len(visited) == len(self.blocks):
                        return True
                    if self.find_path_fun(visited, item):
                        return True
                    else:
                        visited.pop()
            return False
    
    • 最后就是将路径转化成adb模拟滑动和点击的坐标点即可完成自动化闯关的功能。
    • 其实为了达到100%的自动化闯关,项目中有许多细节上的处理,可具体参考代码GitHub:https://github.com/EnthuDai/lian_xian

      总结:之前看到LeetCode排名榜上的大神写过相似的脚本,当时就觉得这样的东西很有意思,放假在家看到有 连线达人 的广告,生成闯关获得的金币可以提现,遂萌生出写这个项目的念头。这个项目虽然小,但是结合了图片处理、数据结构、算法、安卓adb等相关的知识,十分综合,而且写出来之后看着自动闯关的过程相当享受。
    展开全文
  • 哈密顿图 哈密顿回路 哈密顿通路(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':' ');   
    }

     

    展开全文
  • 首先,说明本次问题:本次问题是,构建一个有向哈密顿图,给出任意两个点,找到他们之间存在的哈密顿通路。哈密顿通路需要保证所有点被遍历到,同时不能有重复点。(由于比较习惯java,所以偷懒直接写java

    之前以自己一渣渣之身参加了一个比赛,果然连门槛都没摸到,虽然略有沮丧不过还是得到了很多思考哒,这里记一下。

    因为之前没有接触过算法,感觉这个可能也只是能够解决问题,效率极低,先记下来以后有兴致慢慢优化好了。

    首先,说明本次问题:

    本次问题是,构建一个有向哈密顿图,给出任意两个点,找到他们之间存在的哈密顿通路。哈密顿通路需要保证所有点被遍历到,同时不能有重复点。

    (由于比较习惯java,所以偷懒直接写java版的吧。还得好好学习c的说!)

    这里我考虑用递归的方式,求出存在的哈密顿通路。

    step1:构建图的方式

    HashMap<Integer,ArrayList<Integer>> myMap 
        = new HashMap<Integer, ArrayList<Integer>>();
        //其中,key值为点的ID值,value为与该点相连接的点的ID值

    step2:找到哈密顿通路

    int size = myMap.size();    //点的个数
    void findHamiltonianPath(int id,Integer[] edge){
            for(int pointID: myMap.get(id)){
                if(edge.length!=size-1 && pointID ==destinationID) continue;
                //提前到达目标点
                if(ifHavePassed(edge,pointID)) continue;
                //曾经经过此点,ifHavePassed函数用于检查路径中是否已含有该点
                Integer[] newEdge = new Integer[edge.length+1];
                System.arraycopy(edge,0,newEdge,0,edge.length);
                newEdge[edge.length] = pointID;
                //得到新的路径数组  
                if(pointID == destinationID){
                    System.out.println(Arrays.asList(newEdge));
                    continue;
                }
                findHamiltonianPath(pointID, newEdge);
            }
        }

    感觉原理还是蛮简单的,但是应该还能优化很多。
    希望明年能摸到比赛的门槛~

    展开全文
  • 欧拉通路哈密顿图

    2019-02-10 22:10:15
    欧拉图和哈密顿图 觉得有用的话,欢迎一起讨论相互学习~Follow Me 通路和回路 给定图G&lt;V,E&gt;中结点和边相继交错出现的序列,其中V表示图中结点集合,E表示图中边的集合 Γ=v0e1v1e2v2...ekvk\Gamma=v_0e...

    欧拉图和哈密顿图

    觉得有用的话,欢迎一起讨论相互学习~

    我的微博我的github我的B站

    通路和回路

    • 给定图G<V,E>中结点和边相继交错出现的序列,其中V表示图中结点集合,E表示图中边的集合
      Γ=v0e1v1e2v2...ekvk\Gamma=v_0e_1v_1e_2v_2...e_kv_k

      1. Γ\Gamma中边eie_i的两个端点是vi1v_{i-1}viv_i (G是有向图时要求vi1vieiv_{i-1}与v_{i}分别是e_{i}的起始点和终点),i=1,2,3,…k,则称Γv0vk\Gamma为结点v_0到结点v_k通路(entry) . v0vkv_0和v_k分别称为此通路的 始点和终点 , 统称为通路的 端点 . 通路中边的数目k称为此通路的 长度(length) .当v0=vkv_0=v_k时,此通路称为 回路(circuit)
      2. 若通路中的所有 边(edges) 互不相同,则称此通路为 简单通路(simple entry) 或一条 迹(trail) ;若回路中的所有 互不相同,则称此回路为 简单回路(simple circuit,simple cycle) 或一条 闭迹
      3. 若通路中所有 结点(vertices) 互不相同,则称此通路为 基本通路(basic entry)初级通路、路径(path) ,若回路中除 v0=vkv_0=v_k 外的所有 结点 互不相同(从而所有边互不相同),则称此回路为 基本回路(basic circuit) 或者 初级回路、圈
    • 说明

      1. 回路是通路的特殊情况 因而如果说某条通路,则它可能是回路,但当说一基本通路时,一般指其不是基本回路的情况。
      2. 基本通路一定是简单通路 , 基本回路一定是简单回路 , 但是反之不然 , 因为没有重复的结点肯定没有重复的边,但没有重复的边不能保证一定没有重复的结点。

    可达(accessible)和距离(distance)

    • 在图G=<V,E>中, vi,vjVv_i,v_j\in V

      1. 如果从viv_ivjv_j存在通路,则称vivjv_i到v_j可达的(accessible) ,否则称 vivjv_i到v_j不可达 。规定:任何结点到自己都是可达的。
      2. 如果vivjv_i到v_j可达,则称长度最短的 通路 为从vivjv_i到v_j短线程(geodesic) ,从 vivjv_i到v_j 的短线程的长度称为vivjv_i到v_j的 距离(distance) ,记为 d(vi,vj)d(v_i,v_j) .如果vivjv_i到v_j不可达,则通常记为d(vi,vj)=d(v_i,v_j)=\infty
    • 对于无向图,若vivjv_i到v_j可达,则vjviv_j到v_i一定可达;也有d(vi,vj)=d(vj,vi)d(v_i,v_j)=d(v_j,v_i)

    • 对于有向图,若vivjv_i到v_j可达,不一定有vjviv_j到v_i一定可达;也不一定有d(vi,vj)=d(vj,vi)d(v_i,v_j)=d(v_j,v_i)

    • 在一个具有n个结点的图中,如果从结点vivj(vivj)v_i到结点v_j(v_i\neq v_j) , 存在一条通路则从结点vjviv_j到结点v_i存在一条长度不大于n-1的基本通路。

    • 在一个具有n个结点的图中,如果存在经过结点viv_i的回路,则存在一条经过结点viv_i的长度不大于n的基本回路。

    图的连通性

    无向图的连通性

    • 若无向图G中的任何两个结点都是可达的,则称G是连通图(connected graph),否则称G是非连通图(unconnected graph)

    有向图的连通性

    • 设G=<V,E>是一个有向图,
      1. 略去G中所有有向边得无向图G’,如果无向图G’是连通图,则称有向图G是连通图或弱连通图(weakly connected graph); 否则称G是非连通图.
      2. 若G中任何一对结点之间至少有一个结点到另一个结点是可达的,则称G是单向连通图(unilaterally connected graph)
      3. 若G中任何一对结点之间都是互相可达的,则称G是强连通图(strongly connected graph)
    • 有向图G是强连通图的充分必要条件是G中存在一条经过所有结点的 回路
    • 有向图G是单向连通图的充分必要条件是G中存在一条经过所有结点的 通路

    欧拉图和欧拉通路/回路

    • 设G是无孤立结点的图,若存在一条通路,经过图中每边一次且仅一次,则称此通路为该图的欧拉通路(eulerian entry)
    • 设G是无孤立结点的图,若存在一条回路,经过图中每边一次且仅一次,则称此回路为该图的欧拉回路(eulerian circuit) ,具有欧拉回路的图称为 欧拉图(eulerian graph)
    • 以上定义既适合无向图也适合有向图
    • 欧拉通路是经过图中所有边的通路中长度最短的通路,即通过图中所有边的简单通路
    • 欧拉回路是经过图中所有边的回路中长度最短的回路,即为通过图中所有边的简单回路

    欧拉图的判定和性质

    • 无向图 G=<V,E>具有一条 欧拉通路 ,当且仅当G是 连通的且仅有零个或两个奇度数结点
    • 无向图 G=<V,E>具有一条 欧拉回路 ,当且仅当G是 连通的, 并且 所有结点的度数均为偶数
    • 有向图 G 具有一条 欧拉通路 ,当且仅当G是连通的,且除了两个结点以外,其余结点的入度等于出度,而这两个例外的结点中,一个节点的入度比出度大1,另一个结点的出度比入度大1.
    • 有向图 G 具有一条 欧拉回路,当且仅当G是连通的,且所有结点的入度等于出度。

    哈密顿图和哈密顿通路/回路

    • 经过图中每个节点一次且仅一次的通路称为哈密顿通路(Hamiltonian entry/path)
    • 经过图中每个节点一次且仅一次的回路称为哈密顿回路(Hamiltonian circuit/cycle)
    • 存在哈密顿回路的图称为哈密顿图(Hamiltonian graph)
    • 哈密顿图既适合无向图也适合有向图
    • 哈密顿通路是经过图中所有结点的通路中长度最短的通路,即通过图中所有结点的基本通路
    • 哈密顿回路是经过图中所有结点的通路中长度最短的回路,即通过图中所有结点的基本回路
    展开全文
  • 无向: 欧拉图:每个点度数偶数 欧拉路径:两个点奇数,其余偶数 参考资料:欧拉图(路径)
  • 哈密顿图

    千次阅读 2017-03-15 19:57:34
    哈密顿图 一、定义概念 1.哈密顿通路  设G=为一图(无向图或有向图).G中经过每个顶点一次且仅一次的通路称作哈密顿通路 2.哈密顿回路  G中经过每个顶点一次且仅一次的回路称作哈密顿回路 3.哈密顿图  若G...
  • Dirac 定理: 设一个无向中有 N 个节点,若所有节点的度数都大于等于 N/2,则汉密尔顿回路一定存在。注意,“N/2” 中的除法不是整除,而是实数除法。如果 N 是偶数,当然没有歧义;如果 N 是奇数,则该条件中的 ...
  • 10.5 欧拉通路哈密顿通路 欧拉通路和欧拉回路 G中的欧拉回路是包含G的每一条边的简单回路。 G中的欧拉通路是包含G的每一条边的简单通路。 啥意思呢?先解释简单,即两个顶点之间不能拥有2条边。再来就是需要...
  • =2)阶竞赛构造哈密顿通路 N阶竞赛:含有N个顶点的有向,且每对顶点之间都有一条边。对于N阶竞赛一定存在哈密顿通路。 证明及原理 然后,又有题目中给出的就是一个竞赛,所以我们可以直接推理哈密顿通路...
  • 题意:  给了一堆木棍..木棍的的两头都有颜色..木棍可以通过颜色相同的连在一起..... 乍一看也是一个求哈密顿通路的问题..同样要进行问题转化..把颜色看成点..把每个木棍看成边..那么问题就变成了求是否存在欧
  • 第15章欧拉图与哈密顿图 15.1 欧拉图 1、通过图中所有边仅一次的通路称作欧拉通路。通过图中所有边仅一次的回路称作欧拉回路。具有欧拉回路的图是欧拉图,仅具有欧拉通路的图是半欧拉图。平凡图(只含一个顶点的图)...
  • 由于题意的特殊性,构建出来的是一个竞赛,竞赛一定存在一个哈密顿通路,包含中所有点一次且仅一次,所以最少次数一定是1,且这一次就能完成所有的N项作业.即给出竞赛,构造哈密顿通路. 注意:  由于这题...
  • 链接:http://www.icpc.moe/onlinejudge/showProblem.do?problemCode=3332 ... 题意:  给你一个N,代表含有N个点的竞赛,接着的N * (N- 1) / 2行两个点u, v,代表存在有向边<u,v>,问是否能构造...
  •   经过图中的每个顶点一次且仅一次的通路称为哈密顿通路,经过图中每个顶点一次且仅一次的回路称为哈密顿回路,具有哈密顿回路的图称为哈密顿图,具有哈密顿通路但不具有哈密顿回路的图称为半哈密顿图哈密顿图是...
  • 离散数学-图论-哈密顿图及其应用

    千次阅读 2019-09-22 07:18:00
    哈密顿图 一、定义概念 1.哈密顿通路 设G=<V,E>为一图(无向图或有向图).G中经过每个顶点一次且仅一次的通路称作哈密顿通路 2.哈密顿回路 G中经过每个顶点一次且仅一次的回路(通路基础上+回到起始点...
  • 题意:  有一串单词...若有一个单词的最后一个字符等于另一个单词的第一个字符..... 这题目的意思求是否存在哈密顿通路(每个单词是一个点..找一条路径恰好经过每个单词一次)...但这么多点..还是个NP难..直接做不
  • 我的机器学习教程「美团」算法工程师带你入门机器学习 以及 「三分钟系列」数据结构与算法 已经开始更新了,欢迎大家订阅~这篇专栏整合了这几年的算法知识,简单易懂,也将是我实体书的BLOG版...1.哈密顿通路 设G=...
  • 2. 哈密顿图的定义(哈密顿通路、哈密顿回路) 3. 哈密顿图的必要条件及其推论及推论的应用 4. 证明不存在哈密顿回路 5. 哈密顿图的充分条件 6. 哈密顿图的其他判定方法 方法1: ...
  • 题意:给n个点n条边,判断是否为哈密顿通路。直接暴力搜//author: CHC //First Edit Time: 2015-08-30 16:12 #include #include #include #include #include #include #include <map>
  • 哈密顿图和欧拉图知识小结

    千次阅读 2017-08-02 20:56:46
    哈密顿图的判定是世界级难题。 设G是n阶无向简单图,若对于G中任意不相邻的顶点u、v,均有d(u)+d(v)>=n-1,则说明G中存在哈密顿通路。 不过,这个条件只是充分条件,而不是必要条件。 也就是说,满足该条件一定存在...
  • 欧拉图和哈密顿图

    2019-02-10 22:12:00
    欧拉图和哈密顿图 觉得有用的话,欢迎一起讨论相互学习~Follow Me 通路和回路 给定图G<V,E>中结点和边相继交错出现的序列,其中V表示图中结点集合,E表示图中边的集合 \[\Gamma=v_0e_1v_1e_2v_2...e_kv_k\] 若\...
  • 那么这句话说明该就是竞赛了,竞赛是一定有哈密顿通路的,存在哈密顿通路,机器就只需重启一次就可以做完所有任务。接下来就是简单的寻找哈密顿通路。 简单说下算法: 竞赛:每对顶点之间都有一...

空空如也

空空如也

1 2 3 4 5 6
收藏数 111
精华内容 44
关键字:

哈密顿图通路