ブラウザよりも高速アクセス！
7 関係: ハミルトン閉路問題、グラフ理論、路、閉路、閉路グラフ、NP完全問題、正則グラフ。
ハミルトン閉路問題
ハミルトン閉路問題（ハミルトンへいろもんだい）とは、与えられたグラフについて、全ての頂点を一度だけ通る閉路が存在するかどうか調べる問題である。名称はこの問題を最初に研究した数学者ウィリアム・ローワン・ハミルトンの名に因む。.
新しい！!: ハミルトン路とハミルトン閉路問題 · 続きを見る »
グラフ理論
ラフ理論（グラフりろん、graph theory）は、ノード（節点・頂点）の集合とエッジ（枝・辺）の集合で構成されるグラフに関する数学の理論である。グラフ (データ構造) などの応用がある。.
新しい！!: ハミルトン路とグラフ理論 · 続きを見る »
路
路（ろ）.
閉路
有向閉路の例。青い頂点を2度通るので単純閉路ではない。 閉路（へいろ、cycle, circuit, closed walk）あるいは閉道（へいどう、closed path）とは、始点と終点が同じ路のこと。すなわち、出発点に戻るような辿り方のことである。グラフ理論や位相幾何学において用いられる。 単純閉路（たんじゅんへいろ、simple cycle）とは、自分自身と交差していない閉路のこと。グラフの単純閉路であればいかなる頂点も一度しか現れない。 閉路ならば同じところを行ったり来たりして辿ってもよく、同じところを繰り返し通らない閉路のことを閉道という。 n個の相異なる頂点vi（i.
閉路グラフ
長さ6の閉路グラフ 閉路グラフ（へいろグラフ、cycle graph）は、グラフ理論において1つの閉路（正確には閉道）から成るグラフをいう。言い換えれば、いくつかの辺が相互に連なって1つの輪を形成しているグラフである。n個の辺による閉路グラフを Cn と表記する。Cn においては、辺と頂点の数は等しく、各頂点の次数は常に2である。つまり、各頂点は常に2つの辺と接合している。.
新しい！!: ハミルトン路と閉路グラフ · 続きを見る »
NP完全問題
NP完全（な）問題（エヌピーかんぜん（な）もんだい、NP-complete problem）とは、(1) クラスNP（Non-deterministic Polynomial）に属する決定問題（言語）で、かつ (2) 任意のクラスNPに属する問題から多項式時間還元（帰着）可能なもののことである。条件 (2) を満たす場合は、問題の定義が条件 (1) を満たさない場合にも、NP困難な問題とよびその計算量的な困難性を特徴づけている。多項式時間還元の推移性から、クラスNPに属する問題で、ある一つのNP完全問題から多項式時間還元可能なものも、またNP完全である。現在発見されているNP完全問題の証明の多くはこの推移性によって充足可能性問題などから導かれている。充足可能性問題がNP完全であることは1971年、スティーブン・クック（Stephen Cook (1971).
新しい！!: ハミルトン路とNP完全問題 · 続きを見る »
正則グラフ
正則グラフ（せいそくグラフ、regular graph）は、グラフ理論において、各頂点の隣接する頂点数が全て同じであるようなグラフである。すなわち、全ての頂点の次数が等しい。頂点の次数が k の正則グラフを 「k-正則グラフ」または「次数 k の正則グラフ」と呼ぶ。 次数2までの正則グラフの分類は容易である。0-正則グラフは連結されていない頂点で構成され、1-正則グラフは連結されていない辺で構成され、2-正則グラフは連結されていない閉路で構成される。 3-正則グラフは立方体グラフとも呼ばれる。 正則グラフのうち、隣接する2つの頂点に共通する隣接点が常に同じ l 個で、隣接しない2つの頂点に共通する隣接点が常に同じ n 個となっているものを強正則グラフという。正則だが強正則でない最小のグラフは、6頂点の閉路グラフかつ循環グラフである。 完全グラフ K_m は任意の m について強正則である。 クリスピン・ナッシュ＝ウィリアムズの定理によれば、2k+1 個の頂点から成る k-正則グラフには必ずハミルトン路がある。 ファイル:0-regulární graf na 6 vrcholech.png|0-正則グラフ File:1-regulární graf na 6 vrcholech.svg|1-正則グラフ File:2-regulární graf na 6 vrcholech.svg|2-正則グラフ File:3-regular graph2.svg|3-正則グラフ.
新しい！!: ハミルトン路と正則グラフ · 続きを見る »
