ブラウザよりも高速アクセス！
12 関係: バリンスキーの定理、メンガーの定理、カット (グラフ理論)、グラフ理論、素集合データ構造、道 (グラフ理論)、閉路、連結空間、K-頂点連結グラフ、K-辺連結グラフ、次数 (グラフ理論)、最大フロー最小カット定理。
バリンスキーの定理
数学の一分野であるにおけるバリンスキーの定理（バリンスキーのていり、）とは、三次元多面体およびより高次元のポリトープの持つグラフ理論的構造に関する定理である。あるd-次元凸多面体あるいはポリトープ（その）の頂点と辺から無向グラフを形成するとき、そのグラフは少なくとも''d''-頂点連結（すなわち、どのような d − 1 個の頂点を取り除いても、残されたグラフは連結）である、ということを述べた定理である。例えば、三次元のある多面体に対して、その頂点の内の二つ（およびそれらに接続している辺）が取り除かれたとしても、残された任意の頂点のペアにはそれらをつなぐ頂点と辺の路が存在する。 バリンスキーの定理は、その証明を1961年に与えた数学者のミシェル・L・バリンスキーの名にちなむ。しかし三次元の場合については二十世紀初頭に、三次元多面体のグラフは3-連結平面グラフであるというとして結果が得られていた。.
新しい！!: 連結グラフとバリンスキーの定理 · 続きを見る »
メンガーの定理
メンガーの定理（英: Menger's theorem）とは、グラフ理論および関連する数学の分野における定理であり、有限無向グラフに属する連結グラフに関する定理である。カール・メンガーが1927年、辺連結度と点連結度について見出した。辺連結度版のメンガーの定理は、後に最大フロー最小カット定理として一般化された。 辺連結度版のメンガーの定理は次の通りである。有限無向グラフ G で、x と y が隣接していない頂点であるとする。このとき、x と y の最小辺カット（辺切断。除去することで x と y が連結されなくなる最小の辺の数）の大きさは、x から y の辺独立経路 (辺素パス) の最大数と等しい。 点連結度版のメンガーの定理は次の通りである。有限無向グラフ G で、x と y が隣接していない頂点であるとする。このとき、x と y の最小点カット（点切断。除去することで x と y が連結されなくなる最小の頂点の数）の大きさは、x から y の頂点独立経路 (点素パス) の最大数と等しい。 メンガーの定理は、無限グラフでも成り立つことが証明されている（ポール・エルデシュが最初に推測していた）。.
新しい！!: 連結グラフとメンガーの定理 · 続きを見る »
カット (グラフ理論)
ラフ理論において、グラフ G(V, E) の頂点 V の 2 分割 (S, T) をカット（Cut）とよぶ。このとき、ある辺 (u,v) \in E の端点が u \in S かつ v \in T（有向グラフの場合 u \in T でかつ v \in S の場合もある）であるとき、この辺を「カットエッジ」と呼ぶ。 カットのサイズ (カットの重み) は、カットエッジの総数 (辺重みグラフの場合はカットエッジそれぞれの辺重みの総和) で表される。フローネットワークでは、カットのサイズは始点側から終点側へ向かう辺重みの総和で定義される（逆方向のエッジは加算されない）。 頂点集合のべき集合を定義域としたカットのサイズを返す集合関数は「カット関数」と呼ばれ、 劣モジュラ関数、かつ、正モジュラ関数である。.
新しい！!: 連結グラフとカット (グラフ理論) · 続きを見る »
グラフ理論
ラフ理論（グラフりろん、graph theory）は、ノード（節点・頂点）の集合とエッジ（枝・辺）の集合で構成されるグラフに関する数学の理論である。グラフ (データ構造) などの応用がある。.
新しい！!: 連結グラフとグラフ理論 · 続きを見る »
素集合データ構造
素集合データ構造（そしゅうごうデータこうぞう、英: disjoint-set data structure）は、データの集合を素集合（互いにオーバーラップしない集合）に分割して保持するデータ構造。このデータ構造に対する以下の2つの便利な操作をUnion-Findアルゴリズムと呼ぶ。.
新しい！!: 連結グラフと素集合データ構造 · 続きを見る »
道 (グラフ理論)
有向閉道の例。矢印がなければ単なる閉道である。青い頂点は2度通るので、単純な閉道（すなわち閉路）ではない。 グラフ理論において、グラフの道（みち）またはパス（path）は、頂点の列であり、各頂点とその次の頂点との間に辺が存在する。道は無限の場合もあるが、有限な道には常に始点と終点がある。始点と終点をまとめて端子頂点 (terminal vertices) と呼び、道上の他の頂点を内部頂点 (internal vertices) と呼ぶ。閉道は始点と終点が同じ頂点となっている道である。なお、閉道においてどの頂点を始点とするかは任意である。 道と閉道はグラフ理論の基本的概念であり、グラフ理論の書籍では必ず導入部分で説明されている。例えば、Bondy and Murty (1976)、Gibbons (1985)、Diestel (2005)、Korte et al.
新しい！!: 連結グラフと道 (グラフ理論) · 続きを見る »
閉路
有向閉路の例。青い頂点を2度通るので単純閉路ではない。 閉路（へいろ、cycle, circuit, closed walk）あるいは閉道（へいどう、closed path）とは、始点と終点が同じ路のこと。すなわち、出発点に戻るような辿り方のことである。グラフ理論や位相幾何学において用いられる。 単純閉路（たんじゅんへいろ、simple cycle）とは、自分自身と交差していない閉路のこと。グラフの単純閉路であればいかなる頂点も一度しか現れない。 閉路ならば同じところを行ったり来たりして辿ってもよく、同じところを繰り返し通らない閉路のことを閉道という。 n個の相異なる頂点vi（i.
連結空間
位相幾何学や関連する数学の分野において、連結空間（れんけつくうかん、connected space）とは、2つ以上の互いに素な空でない開部分集合の和集合として表すことのできない位相空間のことである。空間の連結性は主要なの1つであり、位相空間の区別をつけることに利用できる。より強い意味での連結性として、弧状連結 (path-connected) という概念があり、これは任意の2点が道によって結べることをいう。 位相空間 X の部分集合が連結であるとは、X の相対位相によってそれ自身を位相空間と見たときに連結であることをいう。 連結でない空間の例は、平面から直線を取り除いたものがある。非連結空間（すなわち連結でない空間）の他の例には、平面からアニュラスを取り除いたものや、2つの交わりを持たない閉円板の和集合がある。ただし、これら3つの例はいずれも、2次元ユークリッド空間から誘導される相対位相を考えている。.
新しい！!: 連結グラフと連結空間 · 続きを見る »
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-辺連結グラフ
数学のグラフ理論において、あるグラフがk-辺連結（k-へんれんけつ、）であるとは辺連結度がk以上のグラフのことである。 言い換えると、グラフから k より少ない数の辺を除いてもであることを言う。.
新しい！!: 連結グラフとK-辺連結グラフ · 続きを見る »
次数 (グラフ理論)
各頂点に次数を記したグラフ グラフ理論における次数（じすう、degree, valency）は、グラフの頂点に接合する辺の数を意味し、ループであれば2回カウントされる。頂点 v の次数を \deg(v) と表記する。グラフ G の最大次数を Δ(G) と表記し、その中の頂点群の最大次数を意味する。また、グラフの最小次数は δ(G) と表記し、その中の頂点群の最小次数を意味する。右のグラフでは、最大次数は3、最小次数は0である。正則グラフでは全頂点の次数が等しく、その次数をグラフの次数と呼ぶこともある。 有向グラフでは、頂点に入ってくる辺数を入次数 (indegree)、頂点から出て行く辺数を出次数 (outdegree) と呼ぶ。.
新しい！!: 連結グラフと次数 (グラフ理論) · 続きを見る »
最大フロー最小カット定理
最大フロー最小カット定理（さいだいフローさいしょうカットていり、Max-flow min-cut theorem）は、フローネットワークにおいて最大フロー問題についての定理である。これは、ネットワークに流れる「もの」の最大流量が、ボトルネックによって決まることを意味している。線形計画法についての定理メンガーの定理から導出することもできる。.
新しい！!: 連結グラフと最大フロー最小カット定理 · 続きを見る »
