グラフへの整数配置問題
2
0
0
全文
(2) 情報処理学会第 76 回全国大会. {f (a1 ), f (a2 ), · · · , f (an )} も定和配置可能であり、変換. びその最大・最小値、定和配置の解が存在しない条件を. 後の定和 S は式 (5) となる。. 導き、正4面体、6面体、8面体での具体的な構成例を. ′. S ′ = αS + β(m + 2). 述べた。今後は指定の定和値での構成問題、正12面. (5). 体、20面体の具体的な配置を検討する。. 従って配置する数字列が an = αn + β と表されるとき. 参考文献. は 1, 2, · · · , n の配置問題に帰着されることになる。特. [1] 坂田, 杉山, Internet Shiritori using Java, 情報処理学 会, 5N-10 (1999-09).. にアフィン変換 f (x) = n + 1 − x (α = −1, β = n + 1) を用いると最小配置と最大配置を互いに変換できる。例. [2] 赤塚, 杉山, 仮名の出現頻度の偏りを用いた「いろは歌」 の生成, 情報処理学会, 1Q-6 (2001-03).. えば図 1 に示した最小配置を用いて f (x) = 17 − x で 最大配置に変換できることになる。最大配置・最小配置. [3] 杉山 雅英, ことば遊び「doublet」とグラフ探索問題に ついて, 情報処理学会 東北支部第 4 回研究会, 02-4-B9 (2003-03).. の定和の値は式 (5) から関係式 (6) を満す。. Smax + Smin = (n + 1)(m + 2). (6). [4] 大森清美, 魔方陣の世界, 日本評論社.. さらに式 (4), (6) を用いて最大配置・最小配置の定和を 式 (7) のように計算できる。 ( Smax = 12 {(n + 1)(m + 2) + m(2E − V )}. Smin = 21 {(n + 1)(m + 2) − m(2E − V )}. [5] 内田伏一, 魔方陣にみる数のしくみ, 日本評論社. [6] ペレマリン, 藤川健治訳, 遊びの数学, 社会思想社.. (7). 6. 3. 正多角形・正多面体への定和配置 式 (7) で. 22. 3 13. 28 15. 与えられる定和 S が整数値になることは定和配置でき ることの必要条件である。従って S が整数にならない. 19. 26 1. 29. 17. 24. 8. 場合には定和配置できないことになる。正多面体にお. 10. 31. いて V, E ≡ 0(mod. 2) であるので n = mE + V ≡. 32. 9. 0(mod. 2) である。式 (7) の分子は m ≡ 1(mod. 2) の. 11. 時、(n + 1)(m + 2) + m(2E − V ) ≡ 1(mod. 2) であ. 7. 18. 16. 14. なり、即ち、最小・最大配置問題の解は存在しないこと. 27. 4 ✏. 30. 2. 25. る。分子が奇数となるので S は整数にならないことに になる。 ✓ 正多面体の最小・最大配置問題. 23. 12. 20. 5. 21. 図 2: 正6面体の最小配置の例 (m = 2, n = 32). 正多面体の辺に奇数個の数字をおく最小・最大配. 2. 置解は存在しない。 ✒. 同様に正多角形において V = E であるので m ≡. ✑. 1(mod. 2) の時、分子 ≡ 1(mod. 2) となるので最小・最 大配置問題の解は存在しないことになる。 ✓ 正多角形の最小・最大配置問題. 21. 25. 16. 14 27. 3. 9. 5. 18 ✏. 正多角形 の辺の数 E が偶数の時、辺に奇数個の. 28 22. 11. 17. 24. 数字をおく最小・最大配置解は存在しない。 ✒ ✑ 正6面体および正8面体への配置の例を図 2, 3 に示 す。図 2 では m = 2, Smin = 50, n = 32、図 3 では. m = 2, Smin = 44, n = 30 である。最大配置は最小配置. 12. 10 1 13. 20 6. 23 26. 15. 19. 4 8. 7 30. 29 2. から変換 f (x) = n + 1 − x で構成できる。. 4. むすび 多角形、正多面体を含む次数一定のグラ. 図 3: 正8面体の最小配置の例 (m = 2, n = 30). フへの整数定和配置問題について述べ定和の計算法及. 2-4. Copyright 2014 Information Processing Society of Japan. All Rights Reserved..
(3)
関連したドキュメント
断するだけではなく︑遺言者の真意を探求すべきものであ
いてもらう権利﹂に関するものである︒また︑多数意見は本件の争点を歪曲した︒というのは︑第一に︑多数意見は
前掲 11‑1 表に候補者への言及行数の全言及行数に対する割合 ( 1 0 0 分 率)が掲載されている。
LUNA 上に図、表、数式などを含んだ問題と回答を LUNA の画面上に同一で表示する機能の必要性 などについての意見があった。そのため、 LUNA
2014年夏にあったイスラエルによるガザへの軍事侵
奥付の記載が西暦の場合にも、一貫性を考えて、 []付きで元号を付した。また、奥付等の数
彩度(P.100) 色の鮮やかさを 0 から 14 程度までの数値で表したもの。色味の
LF/HF の変化である。本研究で はキャンプの日数が経過するほど 快眠度指数が上昇し、1日目と4 日目を比較すると 9.3 点の差があ った。