一类循环图中的Eulerian定向数

Counting the Eulerian Orientations of One Class of Circulant Graphs

一般的图中Eulerian定向数的计数是#P-完全问题,但对于某些特殊图中的Eulerian定向数给出精确计数是完全有可能的.通过拆分解构的方法可以找到与一类循环图中Eulerian定向数有关的递推关系,从而给出该数的精确计数.前人的工作在于给出了一些近似估计.

Even though counting Eulerian orientations in general graphs is # P-complete problem, it is possible to count Eulerian orientations in some special graphs explicitly. By disassembling and unhooking circulant links we can find the recurrence relation for the number of Eulerian orientations of one class of circulant graphs, so to give the explicit counting. The previous work devoted to give some approximate estimations.