ブラウザよりも高速アクセス！
14 関係: 同値、完全グラフ、巡回行列、ハミルトン路、グラフ理論、固有値、立方体グラフ、隣接代数、隣接行列、閉路、閉路グラフ、連結グラフ、次数 (グラフ理論)、2部グラフ。
同値
同値（どうち）または等価（とうか）とは、2つの命題が共に真または共に偽のときに真となる論理演算である。 英語ではequivalence (EQ)。「if and only if」を略して、iff ともいう。否定排他的論理和 (XNOR) に等しい。 演算子記号は ⇔、↔、≡、.
完全グラフ
記載なし。
新しい！!: 正則グラフと完全グラフ · 続きを見る »
巡回行列
巡回行列（じゅんかいぎょうれつ）または循環行列（じゅんかんぎょうれつ、Circulant matrix）は、テプリッツ行列の特殊なものであり、各行ベクトルが1つ前の行ベクトルの要素を1つずらして配置した形になっているものである。数値解析において、巡回行列は離散フーリエ変換によって対角化されるため、それを含む線型方程式系は高速フーリエ変換で高速に解くことができる。.
新しい！!: 正則グラフと巡回行列 · 続きを見る »
ハミルトン路
ハミルトン路とは、グラフ上の全ての頂点を 1 度ずつ通る路のこと。特に、グラフ上の全ての頂点を 1 度ずつ通る閉路はハミルトン閉路という。また、ハミルトン閉路を含むグラフのことをハミルトングラフといい、ハミルトン路は含むがハミルトン閉路は含まないようなグラフのことを準ハミルトングラフという。 与えられたグラフがハミルトン路を含むかどうか判定する問題は、NP完全。与えられたグラフがハミルトングラフかどうか判定する問題については、ハミルトン閉路問題を参照のこと。.
新しい！!: 正則グラフとハミルトン路 · 続きを見る »
グラフ理論
ラフ理論（グラフりろん、graph theory）は、ノード（節点・頂点）の集合とエッジ（枝・辺）の集合で構成されるグラフに関する数学の理論である。グラフ (データ構造) などの応用がある。.
新しい！!: 正則グラフとグラフ理論 · 続きを見る »
固有値
線型代数学において、線型変換の特徴を表す指標として固有値 (eigenvalue) や固有ベクトル (eigenvector) がある。この2つの用語を合わせて、固有対 (eigenpair) という。与えられた線型変換の固有値および固有ベクトルを求める問題のことを固有値問題 (eigenvalue problem) という。ヒルベルト空間論において線型作用素 あるいは線型演算子と呼ばれるものは線型変換であり、やはりその固有値や固有ベクトルを考えることができる。固有値という言葉は無限次元ヒルベルト空間論や作用素代数におけるスペクトルの意味でもしばしば使われる。.
立方体グラフ
数学のグラフ理論の分野における立方体グラフ（りっぽうたいグラフ、）とは、すべての頂点の次数が 3 であるようなグラフのことを言う。言い換えると、立方体グラフとは 3-正則グラフである。立方体グラフは 3価グラフとも呼ばれる。2部立方体グラフ（bicubic graph）とは、立方体グラフかつ2部グラフであるようなグラフのことを言う。.
新しい！!: 正則グラフと立方体グラフ · 続きを見る »
隣接代数
隣接代数.
新しい！!: 正則グラフと隣接代数 · 続きを見る »
隣接行列
隣接行列（りんせつぎょうれつ、adjacency matrix）とは、における基本的な概念で、グラフの頂点と頂点の隣接関係を表わす正方行列である。 頂点集合を とする有限無向グラフ に対して、その隣接行列 とは（頂点集合によって添字づけられた） 次正方行列であって、その 成分 は頂点 と頂点 を結ぶ枝の数で定義される。これによりグラフ の固有多項式やスペクトルがそれぞれ隣接行列 の固有多項式やスペクトルとして定義される。これらはグラフの不変量である（隣接行列そのものは頂点集合上の置換を除いてしか定まらない）。 有向グラフの場合、 から に向かう枝があるときのみ 成分を 1 に、そうでないとき 成分を 0 にする。また、枝に重みがついているグラフの場合は、 成分を重みとする。.
新しい！!: 正則グラフと隣接行列 · 続きを見る »
閉路
有向閉路の例。青い頂点を2度通るので単純閉路ではない。 閉路（へいろ、cycle, circuit, closed walk）あるいは閉道（へいどう、closed path）とは、始点と終点が同じ路のこと。すなわち、出発点に戻るような辿り方のことである。グラフ理論や位相幾何学において用いられる。 単純閉路（たんじゅんへいろ、simple cycle）とは、自分自身と交差していない閉路のこと。グラフの単純閉路であればいかなる頂点も一度しか現れない。 閉路ならば同じところを行ったり来たりして辿ってもよく、同じところを繰り返し通らない閉路のことを閉道という。 n個の相異なる頂点vi（i.
閉路グラフ
長さ6の閉路グラフ 閉路グラフ（へいろグラフ、cycle graph）は、グラフ理論において1つの閉路（正確には閉道）から成るグラフをいう。言い換えれば、いくつかの辺が相互に連なって1つの輪を形成しているグラフである。n個の辺による閉路グラフを Cn と表記する。Cn においては、辺と頂点の数は等しく、各頂点の次数は常に2である。つまり、各頂点は常に2つの辺と接合している。.
新しい！!: 正則グラフと閉路グラフ · 続きを見る »
連結グラフ
連結グラフ（れんけつグラフ, connected graph）は、グラフ上の任意の2頂点間に道が存在するグラフのことである。連結でないグラフを非連結グラフ (disconnected graph) と呼ぶ。極大で連結な部分グラフは、連結成分 (connected component) という。.
新しい！!: 正則グラフと連結グラフ · 続きを見る »
次数 (グラフ理論)
各頂点に次数を記したグラフ グラフ理論における次数（じすう、degree, valency）は、グラフの頂点に接合する辺の数を意味し、ループであれば2回カウントされる。頂点 v の次数を \deg(v) と表記する。グラフ G の最大次数を Δ(G) と表記し、その中の頂点群の最大次数を意味する。また、グラフの最小次数は δ(G) と表記し、その中の頂点群の最小次数を意味する。右のグラフでは、最大次数は3、最小次数は0である。正則グラフでは全頂点の次数が等しく、その次数をグラフの次数と呼ぶこともある。 有向グラフでは、頂点に入ってくる辺数を入次数 (indegree)、頂点から出て行く辺数を出次数 (outdegree) と呼ぶ。.
新しい！!: 正則グラフと次数 (グラフ理論) · 続きを見る »
2部グラフ
循環の無い2部グラフの例 完全2部グラフ 数学、とくにグラフ理論における2部グラフ（にぶぐらふ、bipartite graph）は、頂点集合を二つの部分集合に分割して各集合内の頂点同士の間には辺が無いようにできるグラフのことである。このような頂点の集合を独立集合といい、より一般にn個の独立頂点集合に分割可能なグラフのことをn部グラフ (n-partite graph) という。 完全2部グラフは、二つの頂点集合V1, V2に分割したとき、V1同士・V2同士の頂点間には辺が存在しないが、V1とV2間の任意の2点間に辺が存在するグラフのことである。m頂点の頂点集合とn頂点の頂点集合に分割されるような完全2部グラフのことをKm, nとかく。 隣り合った頂点同士を異なる色で塗ることを（頂点）彩色という。よって、n部グラフはn点彩色可能なグラフである。同様に、隣り合った辺同士を異なる色で塗ることを辺彩色という。 二部グラフの辺集合Mがマッチングであるとは、Mに属するどの2辺も隣接していないと言うことである。グラフGの最大マッチングとは、GのマッチングMのうち、辺の数が最大のものである。また、全ての頂点を含むマッチングのことを完全マッチングという。.
新しい！!: 正則グラフと2部グラフ · 続きを見る »
