著者

菊地 洋右

雑誌

研究報告アルゴリズム(AL)

巻号頁・発行日

vol.2010-AL-131, no.7, pp.1-4, 2010-09-15

---

単純グラフ G のすべての辺を含む路をオイラー路、オイラー路が閉路となっているものをオイラー回路という。オイラー路をもつグラフを semi-eulerian とよび、オイラー回路をもつグラフをオイラーグラフとよぶ。オイラーグラフの特徴付けはグラフ理論の教科書に必ず載っていると言っていいほどよく知られている。オイラーグラフが与えられたときに、オイラー回路の数え上げは #P-完全であることが知られている。本研究は、単純グラフ G がオイラー路をもつとき、重複も抜けもなく、そのオイラー路を列挙するアルゴリズムを提案する。本研究のアルゴリズムではまず Fleury’s Algorithm を用いて単純グラフ G のオイラー路を求める。このオイラー路から順次、オイラー路を求めていくことで列挙を行う。提案するアルゴリズムは、Fleury’s Algorithm を適用した後に、すべてのグラフ的列を 1 つあたり O(m) 時間で列挙する。

著者

菊地 洋右

出版者

National Institute of Technology, Tsuyama College

雑誌

津山工業高等専門学校紀要 = Bulletin of National Institute of Technology, Tsuyama College (ISSN:02877066)

巻号頁・発行日

vol.61, pp.17-24, 2020-03-30

---

We propose a mathematical model of criminal action. This paper deals with mathematical modeling of action of murder cases. Our model seems to be reasonable since our verification, and needs to improve for some murder cases.

著者

菊地 洋右

出版者

情報処理学会

雑誌

研究報告アルゴリズム(AL) (ISSN:09196072)

巻号頁・発行日

vol.2010, no.7, pp.1-4, 2010-09-15

参考文献数

2

---

単純グラフ G のすべての辺を含む路をオイラー路、オイラー路が閉路となっているものをオイラー回路という。オイラー路をもつグラフを semi-eulerian とよび、オイラー回路をもつグラフをオイラーグラフとよぶ。オイラーグラフの特徴付けはグラフ理論の教科書に必ず載っていると言っていいほどよく知られている。オイラーグラフが与えられたときに、オイラー回路の数え上げは #P-完全であることが知られている。本研究は、単純グラフ G がオイラー路をもつとき、重複も抜けもなく、そのオイラー路を列挙するアルゴリズムを提案する。本研究のアルゴリズムではまず Fleury's Algorithm を用いて単純グラフ G のオイラー路を求める。このオイラー路から順次、オイラー路を求めていくことで列挙を行う。提案するアルゴリズムは、Fleury's Algorithm を適用した後に、すべてのグラフ的列を 1 つあたり O(m) 時間で列挙する。For simple graph G, eulerian trail is a trail that has all edges in G. If eulerian trail is close circuit, it is called eulerian circuit. If G has a eulerian trail, G is called semi-eulerian and if G has a eulerian circuit, then G is eulerian graph. A characterization of eulerian graph is well-known and may appear in any graph theory. Given eulerian graph, counting eulerian circuits is #P¡complete. This paper will propose an algorithm to generate all eulerian trail for simple graph G, if such trail exists. At first, we obtain the minimum eulerian trail of G, applying Fleury's algorithm. Next, we generate all eulerian trails. Our algorithm generates all eulerian trails in O(m2) for each, after applying Fleury's algorithm, where m is the number of edge in G.

著者

Boris Aronov 浅野哲夫 菊地洋右 SubhasC.Nandy 笹原 慎司 宇野 毅明

出版者

一般社団法人情報処理学会

雑誌

情報処理学会研究報告アルゴリズム(AL) (ISSN:09196072)

巻号頁・発行日

vol.2005, no.26, pp.63-69, 2005-03-17

参考文献数

2

---

n×nの行列に整数0 ... n2-1を配置し、どの行和、列和も等しいものをsemimagic squareとよばれる。ここでは列和、行和のかわりにk×kの部分行列に含まれる要素の和を考え、この和が等しいn×n行列をzero k×k-discrepancy matrixとよぶ。そしてこのような行列はkとnがともに偶数であるとき存在し、kとnが互いに素であるとき存在しないことを示す。さらに、k m●2を整数としたときn=k*であるならばzerok×k-discrepancy matrix の存在がいえる。このzero k×k discrepancy matrixの恒星にはconstant-gap matricesを用いる。また、constant-gap matricesの特徴づけを行なう。A semimagic square of order n is an n×n matrix containning the integers 0,...,n2-1arranged in such a way that each row and column add up to the same value.We generalize this notion to that of a zero k×k-discrepancy matrix by replacing the requiremento tha the sum of each row and each column be the same by that of requiring that the sum of the entries in each k×k square contiguous sub matrix be the same.We show that such matrices exist if k and n are both even,and do not if kand n are are relatively prime.Further,the existence is also guaranteed whenever n=k ●,for some integers k,m●2. A class of matirices,called constant-gap matrices plays an important role.We give a characterization of such matrices.

著者

山中 克久 川野 晋一郎 菊地 洋右 中野 眞一

雑誌

情報処理学会研究報告アルゴリズム(AL)

巻号頁・発行日

vol.2006, no.7(2006-AL-104), pp.27-34, 2006-01-20

---

本文では 正の整数 n の整数分割を列挙するアルゴリズムを与える.この問題は 組み合わせ論において基本的な問題の1つであり 長い間 広く研究されてきた.これまで 整数分割1つ当たり平均定数時間で列挙する方法しか知られていなかった.我々は 与えられた整数の整数分割を 最悪でも1つ当たり定数時間で重複なく列挙するアルゴリズムを与える. また 条件付きの整数分割を定数時間で列挙するアルゴリズムをいくつか与える.