论文标题
Kirchhoff的电路法律应用程序在搜索问题中简化图形
Kirchhoff's Circuit Law Applications to Graph Simplification in Search Problems
论文作者
论文摘要
本文提出了使用电势概念对图的新分析，还提出了基于此分析的图形简化方法。假设加权图中的每个节点具有各自的电势值。此外，假设图中的开始和终端节点分别具有最大和零电位。当我们让每个节点的级别定义为从开始节点到节点的最小边/跳数时，可以根据几何比例关系估算每个级别的适当电位。基于每个级别的估计电位，我们可以重新设计图形找到问题问题的图形，因此可以针对Kirchhoff的电路定律，可用于简化图形以解决路径问题的问题。
This paper proposes a new analysis of graph using the concept of electric potential, and also proposes a graph simplification method based on this analysis. Suppose that each node in the weighted-graph has its respective potential value. Furthermore, suppose that the start and terminal nodes in graphs have maximum and zero potentials, respectively. When we let the level of each node be defined as the minimum number of edges/hops from the start node to the node, the proper potential of each level can be estimated based on geometric proportionality relationship. Based on the estimated potential for each level, we can re-design the graph for path-finding problems to be the electrical circuits, thus Kirchhoff's Circuit Law can be directed applicable for simplifying the graph for path-finding problems.
