在图算法的研究中，隐式图是仅给出初始结点、目标结点以及生成子结点的约束条件（题意隐含给出），要求按扩展规则应用于扩展结点的过程，其顶点或边在计算机存储器中不表示为显式对象，而是由一些更简洁的输入在算法上确定的。
隐式图的概念在用图描述的各种搜索算法中很常见。在此上下文中，隐式图可以被定义为一组规则，用于定义任意指定顶点的所有相邻顶点。[1]这种类型的隐式图表示类似于邻接表，因为它可以方便地访问每个顶点的相邻顶点。例如，在搜索诸如Rubik's Cube (魔方)之类的智力游戏的解时，可以定义一个隐式图，其中每个顶点代表魔方的可能状态之一，每个边代表从一种状态到另一种状态的移动。通过尝试智力游戏中所有可能的移动并确定每个移动达到的状态，可以直接生成任何顶点的相邻顶点；然而，隐式表示是必要的，因为魔方的状态空间太大，不允许算法列出它的所有状态。[2]
在计算复杂性理论中，已经结合隐式图定义了几个复杂性类，如上所述，通过列出顶点的相邻顶点的规则或算法来定义。例如，PPA是这样一类问题，其中一个问题被作为输入给出一个无向隐式图(其中顶点是n位二进制串，有一个多项式时间算法来列出图中任意顶点的相邻顶点)和一个奇数度的顶点，并且必须找到第二个奇数度的顶点。通过握手引理，这样一个顶点存在；找到一个顶点是一个NP问题，但是以这种方式定义的问题不一定是NP完全的，因为不知道PPA = NP是否成立。PPAD是定义在隐式有向图上的类似类，它在算法博弈论中引起了关注，因为它包含了计算纳什均衡的问题。[3]]测试隐式图中一个顶点到另一个顶点的可达性的问题也可以用来表征空间有界的非确定复杂性类，该类包括NL(在顶点是O(log n)位的位串的隐式有向图中可以表征可达性的问题类)、SL(无向图的类似类)和PSPACE(在具有多项式长度位串的隐式图中可以表征可达性的问题类)。在这种复杂性理论的背景下，隐式图的顶点可以表示非确定图灵机的状态，边可以表示可能的状态转换，但是隐式图也可以用于表示许多其他类型的组合结构。[4]PLS，另一种复杂性类，它捕获了在隐式图中寻找局部最优解的复杂性。[5]
隐式图模型也被用作相对化的一种形式，以证明复杂性类之间的分离比非相对化模型的已知分离更强。例如，Childs(查尔兹)等人使用隐式图的邻域表示来定义一个图遍历问题，这个问题可以在量子计算机上用多项式时间解决，但在任何经典计算机上需要指数时间来解决。[6]
在图的有效表示的背景下，J. H. Muller (穆勒)为给定F族图中的图G定义了局部结构或邻接标记方案，作为图G每个顶点O(log n)位标识符的分配，以及一种算法(它可能依赖于F，但独立于单独的图G)，该算法将两个顶点标识符作为输入，并确定它们是否是图G中边的端点。也就是说，这种类型的隐式表示类似于邻接矩阵:检查两个顶点是否相邻很简单，但是找到任何顶点的相邻顶点可能涉及循环遍历所有顶点并测试哪些顶点是相邻顶点。[7]
具有邻接标记方案的图族包括:
并非所有图族都有局部结构。对于一些族，一个简单的计数参数证明邻接标记方案不存在:只有O(n log n)位可以用来表示整个图，所以这种类型的表示只能在给定族F中n个顶点图的数量最多为 时存在。具有比这更多的图的图族，例如二部图或无三角形图，没有邻接标记方案。[8][10] 然而，即使图族中图的数量很少的图族也可能没有邻接标记方案；例如，边少于顶点的图族具有2O(n log n) n顶点图，但没有邻接标记方案，因为可以通过为每个边添加一个新的孤立顶点，而不改变其可标记性，将该族中的任何给定图转换成更大的图。[7][10] Kannan(坎南)等人问，具有禁用子图特征和最多具有2O(n log n) n顶点图是否足够一起保证邻接标记方案的存在；这个问题，Spinrad (斯宾格勒)重申为一个猜想，仍然没有定论。[8][10] 在满足猜想条件且没有已知邻接标记方案的图族中，有圆盘图族和线段相交图族。
如果图族F具有邻接标记方案，那么F中的n-顶点图可以表示为多项式大小的公共诱导通用图的诱导子图，该图由所有可能的顶点标识符组成。相反，如果可以构造这种类型的诱导通用图，那么它的顶点的标识可以用作邻接标记方案中的标记。[8]对于隐式图表示的这种应用，标签使用尽可能少的位是很重要的，因为标签中的位数直接转换成诱导通用图中的顶点数。Alstrup和Rauhe证明了任何树都有每个标签有 log2 n + O(log* n)位的邻接标记方案，由此可以得出，任何树度为k的图都有每个标签有k log2 n+ O(log* n)的方案和有顶点的通用图。特别的，平面图最多有三个荫度，所以它们有顶点数接近立方的通用图。[14]这一界限由Gavoille (伽沃勒)和Labourel(劳雷尔)改进，他们的研究表明平面图和次闭图族具有每标签2 log2 n + O(log log n) 位的标记方案，而有界树宽的图具有每个标签为log2 n + O(log log n) 位的标记方案。[15]
Aanderaa-Karp-Rosenberg(安德拉-卡普-罗森博格)猜想涉及了作为一组标记顶点给出的隐式图，其具有用于确定任何两个顶点是否相邻的黑盒规则。该定义与邻接标记方案的不同之处在于，该规则可能适用于特定的图，而不是适用于族中所有图的通用规则。由于这种差异，每个图都有一个隐式表示。例如，规则可以是在不同的邻接矩阵中查找这对顶点。然而，作为输入给出这种类型的隐式图的算法必须仅通过隐式邻接测试对其进行操作，而与测试是如何实现的无关。
图属性是一个图是否属于给定图族的问题；在顶点的任何重新标记下，答案都必须保持不变。在这种情况下，要确定的问题是，在最坏的情况下，在对给定的隐式图确定感兴趣的属性是真还是假之前，必须测试多少对顶点的邻接性。Rivest和Vuillemin证明了任何非平凡图属性的确定性算法都必须测试二次数量的顶点对。[16] 完整的Aanderaa-Karp-Rosenberg(安德拉-卡普-罗森博格)猜想是，单调图属性的任何确定性算法(如果有更多的边被添加到具有该属性的图中，该算法仍然成立)在某些情况下必须测试每一对可能的顶点。这个猜想的几个例子已经被证明是正确的[16]——例如，对于顶点数为质数的图来说，它是正确的——但是整个猜想仍然是开放的。还研究了随机算法和量子算法问题的变体。
Bender(本德)和Ron(罗恩)已经表明，在用于规避猜想的同一模型中，仅在恒定时间才有可能区分有向无环图和远非无环图。相比之下，在基于邻域的隐式图模型中，这样快的时间是不可能的。[17]
^Korf, Richard E. (2008), "Linear-time disk-based implicit graph search", Journal of the ACM, 55 (6), Article 26, 40pp, doi:10.1145/1455248.1455250, MR 2477486..
^Korf, Richard E. (2008), "Minimizing disk I/O in two-bit breadth-first search", Proc. 23rd AAAI Conf. on Artificial Intelligence (PDF), pp. 317–324, The standard 3×3×3 Rubik’s Cube contains 4.3252 × 1019 states, and is too large to search exhaustively..
^Papadimitriou, Christos (1994), "On the complexity of the parity argument and other inefficient proofs of existence" (PDF), Journal of Computer and System Sciences, 48 (3): 498–532, doi:10.1016/S0022-0000(05)80063-7.
^Immerman, Neil (1999), "Exercise 3.7 (Everything is a Graph)", Descriptive Complexity, Graduate Texts in Computer Science, Springer-Verlag, p. 48, ISBN 978-0-387-98600-5..
^Yannakakis, Mihalis (2009), "Equilibria, fixed points, and complexity classes", Computer Science Review, 3 (2): 71–85, arXiv:0802.2831, doi:10.1016/j.cosrev.2009.03.004..
^Childs, Andrew M.; Cleve, Richard; Deotto, Enrico; Farhi, Edward; Gutmann, Sam; Spielman, Daniel A. (2003), "Exponential algorithmic speedup by a quantum walk", Proceedings of the Thirty-Fifth Annual ACM Symposium on Theory of Computing, New York: ACM, pp. 59–68, arXiv:quant-ph/0209131, doi:10.1145/780542.780552, MR 2121062..
^Muller, John Harold (1988), Local structure in graph classes, Ph.D. thesis, Georgia Institute of Technology..
^Kannan, Sampath; Naor, Moni; Rudich, Steven (1992), "Implicit representation of graphs", SIAM Journal on Discrete Mathematics, 5 (4): 596–603, doi:10.1137/0405049, MR 1186827..
^Chrobak, Marek; Eppstein, David (1991), "Planar orientations with low out-degree and compaction of adjacency matrices" (PDF), Theoretical Computer Science, 86 (2): 243–266, doi:10.1016/0304-3975(91)90020-3..
^Spinrad, Jeremy P. (2003), "2. Implicit graph representation", Efficient Graph Representations, pp. 17–30, ISBN 0-8218-2815-0..
^Kang, Ross J.; Müller, Tobias (2011), Sphere and dot product representations of graphs (PDF)..
^Ma, Tze Heng; Spinrad, Jeremy P. (1991), "Cycle-free partial orders and chordal comparability graphs", Order, 8 (1): 49–61, doi:10.1007/BF00385814, MR 1129614..
^Curtis, Andrew R.; Izurieta, Clemente; Joeris, Benson; Lundberg, Scott; McConnell, Ross M. (2010), "An implicit representation of chordal comparability graphs in linear time", Discrete Applied Mathematics, 158 (8): 869–875, doi:10.1016/j.dam.2010.01.005, MR 2602811..
^Alstrup, Stephen; Rauhe, Theis (2002), "Small induced-universal graphs and compact implicit graph representations" (PDF), Proceedings of the 43rd Annual IEEE Symposium on Foundations of Computer Science: 53–62, doi:10.1109/SFCS.2002.1181882..
^Arnaud, Labourel; Gavoille, Cyril (2007), "Shorter Implicit Representation for Planar Graphs and Bounded Treewidth Graphs" (PDF), Proceedings of the 15th annual European Symposium on Algorithms: 582–593, doi:10.1007/978-3-540-75520-3_52..
^Kahn, Jeff; Saks, Michael; Sturtevant, Dean (1983), "A topological approach to evasiveness", Symposium on Foundations of Computer Science, Los Alamitos, CA, USA: IEEE Computer Society, pp. 31–33, doi:10.1109/SFCS.1983.4..
^Bender, Michael A.; Ron, Dana (2000), "Testing acyclicity of directed graphs in sublinear time", Automata, languages and programming (Geneva, 2000), Lecture Notes in Comput. Sci., 1853, Berlin: Springer, pp. 809–820, doi:10.1007/3-540-45022-X_68, MR 1795937..
暂无