数毒吧 关注:336贴子:2,203
  • 10回复贴,共1

唯一环的路径不唯一性

只看楼主收藏回复

之前有人问我这么一个问题:唯一环的路径是唯一的吗?这一下把我问懵了,我研究了一两天,结果发现这个问题其实并不是特别难。经和楠竹讨论,现在把结果发上来。
至于大家是不是真正知道这个问题,我希望比我们先知道结果的人不要充当**人士。知道结果的话,请你绕行。


IP属地:北京1楼2021-01-10 12:43回复
    现在阐述一下问题:唯一环(UL)的路径是否是唯一的。什么是唯一环的路径呢?就是说,我们需要把唯一环的环状结构按照次序有序连接起来,作为唯一环的先后序列。题目问的就是这个序列是否存在多种不同的连法。举个例子,这个UL的路径是这样的:

    可以从图里看到,这个连法是唯一的。换句话说,你无法找到一个点,在和别的点连起来之后,依然成环。比如我们可以尝试把r4c6和r4c8连起来,但是这样的话,剩余的格子无法保证路径成环。


    IP属地:北京2楼2021-01-10 12:46
    回复
      下面说一下基本概念:出度。我们把一个点可以往外连的所有格子总数称为这个格子的出度。比如r4c6的出度是3,因为它可以往结构的r1c6、r6c4和r4c8三个格子连接线条。
      当出度点均为2的时候,UL的路径唯一,因为我们无法找到别的连接办法,因为它只有两种连接方式。


      IP属地:北京3楼2021-01-10 12:48
      回复
        当出度为3的时候,当这个点作为接收的时候,剩下出度为2,即还可以往外找到两种可能连接的情况。这种情况分析较为复杂。下面我找到了一个极端例子:所有出度都是3的UL,且它至少有4种不同的路径。

        如图所示,所有点的出度都是3,也就是说我们无法找到出度为2的点。


        IP属地:北京4楼2021-01-10 12:51
        回复



          最后一个路径是SE程序给出的默认路径。可以从图里看到,路径是不对称的,所以你可以尝试把路径旋转180度后得到第四种画法。


          IP属地:北京5楼2021-01-10 12:52
          回复
            结论:但是出度3的点会受到出度2的点的制约,所以我们连线先从出度2的连的话,出度3的点就会由于刚才的连锁反应而降到出度2,因为别的点可能被别的地方连走了,所以平时我们遇不到多路径的UL。
            图里给出的恰好是范例,所有点都是出度3,这样你怎么找到一种,就必然有一种对称的画法。
            出度3的点在UL较长的时候出现频率较高,但这样的点依旧可以受到别的出度2的点的制约而改成出度2,进而只有一种连接方式,导致一种巧合。

            如图所示,所有圈起来的点都是出度3的点。
            就这个例子来说,比如我们假设把r1c5的格子挪一下,假如我往下放一个格子的位置,然后为了保证UL合法,我们把r2c7的点往上挪一下。


            图里的这样的结构就有两种画法,所以路径不一定是唯一的。


            IP属地:北京6楼2021-01-10 12:56
            回复
              在UL的递归算法过程中,我们是通过BFS对行、列、宫三个方向进行迭代。由于迭代方式的关系,所以算法不能给出唯一的路径;但我们找到的例子里,大多的题目都是唯一的路径,这使得我们以为路径唯一是一个“定则”。所以在我们平时做题和发现问题的时候,需要反复思考,不能认为巧合是真理就不再思考了。


              IP属地:北京7楼2021-01-10 12:58
              回复
                UL有子环的可能性吗?


                8楼2021-01-13 08:56
                收起回复
                  路径唯一才叫唯一环。路径有分支,但最终构成封闭的环,也算唯一环。
                  只要逻辑上符合强弱交替并形成封闭的环,那结论是一致的。


                  9楼2021-04-20 17:21
                  回复