论文标题
Eulerian电路的简单性：独特性和安全性
Simplicity in Eulerian Circuits: Uniqueness and Safety
论文作者
论文摘要
有向图中的欧拉电路是最基本的图理论概念之一。 Detecting if a graph $G$ has a unique Eulerian circuit can be done in polynomial time via the BEST theorem by de Bruijn, van Aardenne-Ehrenfest, Smith and Tutte, 1941-1951 (involving counting arborescences), or via a tailored characterization by Pevzner, 1989 (involving computing the intersection graph of simple cycles of $G$), both of which thus rely on对于简单的独特问题，过于复杂的概念。 在本文中，我们给出了具有独特的欧拉电路的有向图的新的线性检查表征。这是基于一个简单的条件，即何时必须在所有欧拉电路中连续出现两个边缘，这是基于$ g $的基础无向图的切割节点。作为副产品，我们还可以在线性时间中计算所有最大$ \ textit {safe} $步行，所有欧拉（Eulerian）电路中出现的步道，nagarajan和pop在2009年在2009年提出了基于pevzner表征的多项式算法。
An Eulerian circuit in a directed graph is one of the most fundamental Graph Theory notions. Detecting if a graph $G$ has a unique Eulerian circuit can be done in polynomial time via the BEST theorem by de Bruijn, van Aardenne-Ehrenfest, Smith and Tutte, 1941-1951 (involving counting arborescences), or via a tailored characterization by Pevzner, 1989 (involving computing the intersection graph of simple cycles of $G$), both of which thus rely on overly complex notions for the simpler uniqueness problem. In this paper we give a new linear-time checkable characterization of directed graphs with a unique Eulerian circuit. This is based on a simple condition of when two edges must appear consecutively in all Eulerian circuits, in terms of cut nodes of the underlying undirected graph of $G$. As a by-product, we can also compute in linear-time all maximal $\textit{safe}$ walks appearing in all Eulerian circuits, for which Nagarajan and Pop proposed in 2009 a polynomial-time algorithm based on Pevzner characterization.
