講演抄録/キーワード |
講演名 |
2012-03-16 15:40
オイラー回帰長の上界についての予想 ○神保秀司(岡山大) COMP2011-54 |
抄録 |
(和) |
オイラーグラフに対して,そのオイラー回路の最短部分閉路長の最大値をそのグラフのオイラー回帰長と呼ぶ.$n$ は正の奇数とし,$n$ 個の点からなる完全グラフ $K_n$ のオイラー回帰長を $e(n)$ で表す.本報告では,未解決になっている「任意の奇数 $n\geqq 7$ に対して $e(n) < n-2$ が成り立つ」という予想を解決に導くことを目的とする新しい予想を提案し,さらに,予想の検証のための計算機実験のアルゴリズムの改良について述べる.改良されたアルゴリズムにより $e(21) < 19$ が成り立つことが検証されている. |
(英) |
The maximum of the shortest subcycle length of Eulerian circuits
of an Eulerian graph is called the Eulerian recurrent length of
the graph. Let $n$ be a positive odd integer, and let $e(n)$ denote
the Eulerian recurrent length of the complete graph $K_n$ that consists of $n$ vertices. In this report, a new conjecture expected to lead to the solution of the following unsolved conjecture is proposed: for any odd integer $n \geqq 7$, $e(n) < n - 2$ holds. Furthermore, improvement of the algorithm for computer experiments to verify the conjectures is shown. By computer experiments with the improved algorithm, it has been verified that $e(21) < 19$ holds. |
キーワード |
(和) |
オイラーグラフ / 完全グラフ / オイラー回路 / 計算機実験 / / / / |
(英) |
Eulerian graph / complete graph / Eulerian circuit / computer experiment / / / / |
文献情報 |
信学技報, vol. 111, no. 494, COMP2011-54, pp. 53-58, 2012年3月. |
資料番号 |
COMP2011-54 |
発行日 |
2012-03-09 (COMP) |
ISSN |
Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
COMP2011-54 |