關於二維反問題/中值圖

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] 中證明，如果具有自然邊界的平面網路的中值圖是偽直線的排列，則其邊的電導率由其狄利克雷-諾伊曼運算元唯一確定，並且可以透過分層剝離演算法找到。