隐式图

在图算法的研究中，隐式图表示（或更简单地说是隐式图）是一种图，其顶点或边缘在计算机内存中不表示为显式对象，而是从其他输入中通过算法确定，例如一个可计算的函数。

隐式图的概念在各种搜索算法中很常见，这些算法是用图来描述的。在这种情况下，隐式图可以被定义为一组规则来定义任何指定顶点的所有邻居。这种类型的隐式图表示类似于邻接列表，因为它提供了对每个顶点的邻居的简单访问。例如，在寻找诸如Rubik'sCube等谜题的解决方案时，我们可以定义一个隐式图，其中每个顶点代表立方体的一个可能状态，每条边代表从一个状态到另一个状态的移动。通过尝试谜题中所有可能的移动并确定这些移动所达到的状态，可以直接生成任何顶点的邻居；然而，隐式表示是必要的，因为魔方的状态空间太大，不允许一个算法列出其所有的状态。在计算复杂性理论中，已经定义了几个与隐式图有关的复杂性类别，如上所述，由一个规则或算法来列出一个顶点的邻居。例如，PPA是这样一类问题：给定一个无向隐式图（其中顶点是n位二进制字符串，有一个列出任何顶点邻居的多项式时间算法）和图中一个奇数程度的顶点作为输入，并且必须找到第二个奇数程度的顶点。根据握手定理，这样的顶点是存在的；找到一个顶点是NP中的一个问题，但是以这种方式定义的问题不一定是NP-完全的，因为PPA=NP是未知的。PPAD是一个定义在隐式有向图上的类似类，在算法博弈论中引起了关注，因为它包含了计算纳什均衡的问题。测试隐式图中一个顶点对另一个顶点的可达性问题也可以用来描述空间约束的非确定性复杂性类，包括NL（隐式有向图中顶点为O(logn)比特串的可达性问题类）、SL（无向图的类似类）和PSPACE（隐式图中具有多项式长度的比特串的可达性问题类）。

在这个复杂性理论背景下，隐式图的顶点可以代表非确定性图灵机的状态，而边可以代表可能的状态转换，但隐式图也可以用来代表许多其他类型的组合结构。PLS是另一个复杂性类别，它捕捉了在隐式图中寻找局部最优的复杂性。隐式图模型也被用作相对化的一种形式，以证明复杂度类别之间的分离，这种分离比非相对化模型的已知分离更强。例如，Childs等人使用隐式图的邻域表示来定义图的遍历问题，该问题在量子计算机上可以在多项式时间内解决，但在任何经典计算机上需要指数级时间来解决。

在图的有效表示方面，J.H.Muller将给定的图族F中的图G的局部结构或邻接标记方案定义为给G的每个顶点分配一个O(logn)位标识符，以及一个算法（可能取决于F，但独立于单个图G），该算法将两个顶点标识符作为输入并确定它们是否是G中一条边的端点。也就是说，这种类型的隐式表示类似于邻接矩阵：检查两个顶点是否相邻是直截了当的，但寻找任何顶点的邻居可能需要在所有顶点中循环，测试哪些是邻居。具有邻接标记方案的图族包括。

如果G中的每个顶点最多有d个邻居，可以将G的顶点从1到n编号，并让顶点的标识符为其自身编号和邻居编号的（d+1）元组。当两个顶点的标识符中的xxx个数字出现在另一个顶点的标识符之后，这两个顶点就是相邻的。更普遍的是，同样的方法可以用来为具有有界空心性或有界退化性的图提供隐式表示，包括平面图和任何小闭合图族中的图。交叉图区间图是实线中一组线段的交集图。