|
===================================== 〔語彙分解〕的な部分一致の検索結果は以下の通りです。 ・ 誘導 ： [ゆうどう] 1. (n,vs) guidance 2. leading 3. induction 4. introduction 5. incitement 6. inducement
無向グラフ''G''中の誘導パスは， ''G''の誘導グラフかつ道であるグラフのことである． つまり，誘導パスは そのパス上で隣接している任意の頂点対は''G''中で隣接しており， かつ， 隣接していない任意の頂点対は''G''中で隣接していないような，''G''中の頂点の列である． 誘導パスは，スネークとも呼ばれ， 超立方体上の最長誘導パスを発見する問題は， en:Snake-in-the-box問題として知られている． また， 誘導サイクルは， en:閉路をなす''G''の誘導グラフのことである． また，誘導サイクルは， コードレスサイクルや，その長さが4以上のとき，ホールとも呼ばれる． アンチホールは， ''G''の補グラフにおけるホールである． グラフ中の最長誘導パスの長さは， そのグラフのう回路数と呼ばれる．〔.〕 任意のen:疎グラフに対して， う回路数が固定された時は，:w:tree-depthが固定されている時と等価である． 〔, Proposition 6.4, p. 122.〕 グラフ''G''の誘導パス数とは， グラフを分割するのに必要な最小の誘導パスの数である． 〔.〕 また， ''G''のパス被覆は，''G''のすべての頂点を覆うために必要な誘導パスの最小数である． 〔.〕 グラフ''G''の内周は， ''G''中の最小のサイクルの長さであるが， そのサイクルは，誘導サイクルである． 同様に，奇内周は， グラフにおける奇数長の最短な誘導サイクルの長さのことである． == 例 == 図は， 8個の頂点と12本の辺からなるグラフと， このグラフにおける長さ4の誘導パスの例である． 図の超立方体は， これより長い誘導パスを持たないが， 長さ6の誘導サイクルを持つ． 超立方体上の最長誘導パスまたは，最長誘導サイクルを求める問題は， en:Snake-in-the-box問題として知られており， 符号理論や工学分野で広く研究されている． 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「誘導パス」の詳細全文を読む スポンサード リンク
|