ブラウザよりも高速アクセス！
10 関係: 多項式時間、メンガーの定理、カット (グラフ理論)、グラフ理論、連結グラフ、K-頂点連結グラフ、NP困難、次数 (グラフ理論)、最大フロー問題、数学。
多項式時間
多項式時間（たこうしきじかん）とは計算理論において多項式で表される計算時間。 多項式時間のアルゴリズムとは、解くべき問題の入力サイズnに対して、処理時間の上界としてnの多項式で表現できるものが存在するアルゴリズムを指す。問題入力サイズの増大に対する、処理時間の増大を表すものであることに注意されたい。 たとえばバブルソートの処理時間は要素数nに対して要素の比較・交換を行う回数は高々 \frac n(n-1) である。したがって、この場合の最悪計算量のオーダーは''O''記法を用いてO()と表される。 またクイックソートの期待計算量のオーダーはO(n \log n)、最悪計算量のオーダーはO()である。.
新しい！!: K-辺連結グラフと多項式時間 · 続きを見る »
メンガーの定理
メンガーの定理（英: Menger's theorem）とは、グラフ理論および関連する数学の分野における定理であり、有限無向グラフに属する連結グラフに関する定理である。カール・メンガーが1927年、辺連結度と点連結度について見出した。辺連結度版のメンガーの定理は、後に最大フロー最小カット定理として一般化された。 辺連結度版のメンガーの定理は次の通りである。有限無向グラフ G で、x と y が隣接していない頂点であるとする。このとき、x と y の最小辺カット（辺切断。除去することで x と y が連結されなくなる最小の辺の数）の大きさは、x から y の辺独立経路 (辺素パス) の最大数と等しい。 点連結度版のメンガーの定理は次の通りである。有限無向グラフ G で、x と y が隣接していない頂点であるとする。このとき、x と y の最小点カット（点切断。除去することで x と y が連結されなくなる最小の頂点の数）の大きさは、x から y の頂点独立経路 (点素パス) の最大数と等しい。 メンガーの定理は、無限グラフでも成り立つことが証明されている（ポール・エルデシュが最初に推測していた）。.
新しい！!: K-辺連結グラフとメンガーの定理 · 続きを見る »
カット (グラフ理論)
ラフ理論において、グラフ G(V, E) の頂点 V の 2 分割 (S, T) をカット（Cut）とよぶ。このとき、ある辺 (u,v) \in E の端点が u \in S かつ v \in T（有向グラフの場合 u \in T でかつ v \in S の場合もある）であるとき、この辺を「カットエッジ」と呼ぶ。 カットのサイズ (カットの重み) は、カットエッジの総数 (辺重みグラフの場合はカットエッジそれぞれの辺重みの総和) で表される。フローネットワークでは、カットのサイズは始点側から終点側へ向かう辺重みの総和で定義される（逆方向のエッジは加算されない）。 頂点集合のべき集合を定義域としたカットのサイズを返す集合関数は「カット関数」と呼ばれ、 劣モジュラ関数、かつ、正モジュラ関数である。.
新しい！!: K-辺連結グラフとカット (グラフ理論) · 続きを見る »
グラフ理論
ラフ理論（グラフりろん、graph theory）は、ノード（節点・頂点）の集合とエッジ（枝・辺）の集合で構成されるグラフに関する数学の理論である。グラフ (データ構造) などの応用がある。.
新しい！!: K-辺連結グラフとグラフ理論 · 続きを見る »
連結グラフ
連結グラフ（れんけつグラフ, connected graph）は、グラフ上の任意の2頂点間に道が存在するグラフのことである。連結でないグラフを非連結グラフ (disconnected graph) と呼ぶ。極大で連結な部分グラフは、連結成分 (connected component) という。.
新しい！!: K-辺連結グラフと連結グラフ · 続きを見る »
K-頂点連結グラフ
数学のグラフ理論において、頂点集合 V(G) を備えるグラフ G が k-頂点連結（k-ちょうてんれんけつ、）あるいはk-連結であるとは、 k より少ない数の頂点を取り除いても依然として連結グラフであることを言う。 つまり、点連結度がk以上のグラフのことである。 代替的に、グラフがk-連結であるとは、それらを除いたときに グラフが非連結となるような頂点の最小部分集合の大きさが k であることを言う。 グラフが完全でないことと同値な定義は、任意の二つの頂点が k 独立な道 (点素パス) によって 結ばれるときにグラフがk-連結であることである; メンガーの定理を参照されたい。 しかしながら、完全グラフに対して、上述の二つの定義は異なるものとなる: n-頂点の完全グラフは、 頂点を除去することに基づいた定義に従うとその連結度は非有界となるが、 独立な道に基づいた定義に従うと、その連結度は n − 1 になる。 そして、何人かの研究者は、連結度が n となるような代替的な定義を用いている。 1-頂点連結グラフは、連結であると言われ、2-頂点連結グラフは2重連結であると言われる。 グラフの頂点連結度あるいは単純に連結度とは、 そのグラフ k-頂点連結であるような k の最大数のことを言う。 任意のk-次元凸ポリトープのは、 k-頂点連結グラフを形成する（バリンスキーの定理、）。 その部分的な逆として、では、任意の3-頂点連結平面グラフは凸多面体のスケルトンを形成する、ということが述べられている。.
新しい！!: K-辺連結グラフとK-頂点連結グラフ · 続きを見る »
NP困難
NP完全、'''NP困難'''の相関を表すベン図 NP困難（エヌピーこんなん、NP-hard）とは計算量理論において、問題が「NPに属する任意の問題と比べて、少なくとも同等以上に難しい」ことである。正確にいうと問題 H がNP困難であるとは、「NPに属する任意の問題 L が H へ帰着可能である」と定義される。この「帰着」の定義として何を用いるかにより微妙に定義が異なることになるが、例えば多項式時間多対一帰着や多項式時間チューリング帰着を用いる。NP困難問題を解ける多項式時間の機械がもしあれば、それを利用してNPに属するどの問題も多項式時間で解くことができる。 NP完全問題とは、NP困難であり、かつNPに属する問題である。これと異なり、NP困難である問題はNPに属するとは限らない。NPは決定問題のクラスなのでNP完全もまた決定問題に限られるが、定義に用いる帰着の種類によってはNP困難には決定問題、探索問題(en)、組合せ最適化問題など様々な問題が属しうる。 上に挙げた定義から、問題 H がNP困難なとき次のことが言える（以下は定義ではなく主張）。.
新しい！!: K-辺連結グラフとNP困難 · 続きを見る »
次数 (グラフ理論)
各頂点に次数を記したグラフ グラフ理論における次数（じすう、degree, valency）は、グラフの頂点に接合する辺の数を意味し、ループであれば2回カウントされる。頂点 v の次数を \deg(v) と表記する。グラフ G の最大次数を Δ(G) と表記し、その中の頂点群の最大次数を意味する。また、グラフの最小次数は δ(G) と表記し、その中の頂点群の最小次数を意味する。右のグラフでは、最大次数は3、最小次数は0である。正則グラフでは全頂点の次数が等しく、その次数をグラフの次数と呼ぶこともある。 有向グラフでは、頂点に入ってくる辺数を入次数 (indegree)、頂点から出て行く辺数を出次数 (outdegree) と呼ぶ。.
新しい！!: K-辺連結グラフと次数 (グラフ理論) · 続きを見る »
最大フロー問題
最大フローのあるフローネットワークの例。始点 s と終点 t があり、各枝の数値はフローと容量を示す。 最大フロー問題または最大流問題（Maximum flow problem）とは、単一の始点から単一の終点へのフローネットワークで最大となるフローを求める問題である。単にフローの最大値を求める問題と定義されることもある。最大フロー問題は、より複雑なネットワークフロー問題である最小費用流問題の特殊ケースと見ることもできる。 最小カット問題（Minimum cut problem）とは、辺の重みが非負値の有向グラフにおいて、始点から終点までのパスが存在しなくなるように辺を除去した時に、除去した辺の重みの総和を最小にする問題。始点から終点への最大フローは始点から終点への最小カットと等しい。これを最大フロー最小カット定理と呼ぶ。 2部グラフの最大マッチング問題（Maximum bipartite matching）とは、2部グラフの最大マッチングを求める問題で、これも最大フロー問題のアルゴリズムを使用して解ける。.
新しい！!: K-辺連結グラフと最大フロー問題 · 続きを見る »
数学
数学（すうがく、μαθηματικά, mathematica, math）は、量（数）、構造、空間、変化について研究する学問である。数学の範囲と定義については、数学者や哲学者の間で様々な見解がある。.
新しい！!: K-辺連結グラフと数学 · 続きを見る »
