关于二维反问题/中值图

The following construction plays an important role in studying the graphs properly embedded into surfaces. One considers an embedded into a surface (2D manifold) finite graph w/vertices each w/four neighbors. The union of edges of such graph is equal to a union of closed curves on the surface, called geodesics. The faces of the graph can be two-colored.

The corresponding graph G and its dual G^* can be obtained by putting vertices in all faces of the same color and connecting two vertices by an edge if the corresponding faces of the medial graph M(G) have a common corner. Note that M(G)=M(G^*). The construction can be modified accordingly for the case of an embedded graph w/boundary by allowing vertices of the medial graph to have one neighbor.

中值图M(G)的测地线的以下变换类似于纽结理论的Reidemeister 移动。它们对应于图G和G^*的Y-Δ变换。

The three moves of geodesics curves — 测地线曲线的三个移动

以下矩阵包含中值图下方边界面的距离（跨越测地线的最小跳跃次数或M^*(G)中的边距离）。

{\begin{pmatrix}0&1&2&3&2&3&2&1\\1&0&1&2&3&4&3&2\\2&1&0&1&2&3&4&3\\3&2&1&0&1&2&3&4\\2&3&2&1&0&1&2&3\\3&4&3&2&1&0&1&2\\2&3&4&3&2&1&0&1\\1&2&3&4&3&2&1&0\end{pmatrix}}

Two examples of boundary isometric medial graphs with 4 and 5 geodesics — 具有 4 条和 5 条测地线的边界等距中值图的两个示例

Exercise (*). Prove that the distances between boundary faces of an embedded medial graph are invariant under the geodesics moves.

如果中值图的测地线形成伪直线的排列，则

它们中没有一个与自身相交
它们中没有一个是封闭的
它们中没有两个相交超过一次

Exercise (***). Prove that (a) one can recover a planar medial graph M(G), up to the moves, from the distances between its boundary faces, (b) every planar medial graph M(G) can be moved into an arrangement of pseudo-lines without changing the distance matrix.

(提示)。寻找模式

{\begin{pmatrix}k+1&k\\k&k+1\end{pmatrix}}

在边界距离矩阵中。参见 [PU] 获取边界距离刚度结果的连续模拟。

以下最小割最大流结果是在华盛顿大学反问题暑期学校学生 Derek Jerina 的帮助下制定的。

Exercise (**). Prove that the ranks of submatrices of the matrix of the Dirichlet-to-Neumann operator of a planar graph w/natural boundary determine the shortest distances between the boundary faces of its medial graph, and therefore determine the planar graph up to a finite sequence of Y-Δ transformations. (Hint.) It follows from the determinant identity in the section  Special matrices that the ranks of the submatrices count the numbers of disjoint paths connecting boundary nodes of the planar graph.

在 [DeV1]、[DeV2] 和 [CIM] 中证明，如果具有自然边界的平面网络的中值图是伪直线的排列，则其边的电导率由其狄利克雷-诺伊曼算子唯一确定，并且可以通过分层剥离算法找到。