ブラウザよりも高速アクセス！
12 関係: 多面体、完全グラフ、平面グラフ、バリンスキーの定理、ポリトープ、メンガーの定理、グラフ理論、道 (グラフ理論)、連結グラフ、K-辺連結グラフ、数学、2重連結グラフ。
多面体
多面体の一種、立方体 初等幾何学における多面体（ためんたい、polyhedron）は、複数（4つ以上）の平面に囲まれた立体のこと。複数の頂点を結ぶ直線の辺と、その辺に囲まれた面によって構成される。したがって、曲面をもつものは含まず、(円柱などは入らない)また、すべての面の境界が直線である場合に限られる。 3次元空間での多胞体であるとも定義できる。2次元空間での多胞体は多角形なので、多角形を3次元に拡張した概念であるとも言える。 英語ではポリヘドロン (polyhedron)、複数形はポリヘドラ (polyhedra) である。多角形のポリゴン (polygon) の複数形がポリゴンズ (polygons) であるのとは異なる。.
新しい！!: K-頂点連結グラフと多面体 · 続きを見る »
完全グラフ
記載なし。
新しい！!: K-頂点連結グラフと完全グラフ · 続きを見る »
平面グラフ
平面グラフ (plane graph) は、平面上の頂点集合とそれを交差なく結ぶ辺集合からなるグラフのことである。平面グラフと同型なグラフのことを平面的グラフ (planar graph) という。 平面的グラフは、球面などの種数0の曲面に描けるグラフと同値である。 極小な非平面的グラフは、K3,3とK5。.
新しい！!: K-頂点連結グラフと平面グラフ · 続きを見る »
バリンスキーの定理
数学の一分野であるにおけるバリンスキーの定理（バリンスキーのていり、）とは、三次元多面体およびより高次元のポリトープの持つグラフ理論的構造に関する定理である。あるd-次元凸多面体あるいはポリトープ（その）の頂点と辺から無向グラフを形成するとき、そのグラフは少なくとも''d''-頂点連結（すなわち、どのような d − 1 個の頂点を取り除いても、残されたグラフは連結）である、ということを述べた定理である。例えば、三次元のある多面体に対して、その頂点の内の二つ（およびそれらに接続している辺）が取り除かれたとしても、残された任意の頂点のペアにはそれらをつなぐ頂点と辺の路が存在する。 バリンスキーの定理は、その証明を1961年に与えた数学者のミシェル・L・バリンスキーの名にちなむ。しかし三次元の場合については二十世紀初頭に、三次元多面体のグラフは3-連結平面グラフであるというとして結果が得られていた。.
新しい！!: K-頂点連結グラフとバリンスキーの定理 · 続きを見る »
ポリトープ
初等幾何学における超多面体（ちょうためんたい、poly­tope; ポリトープ）は、平坦な縁を持つ幾何学的対象で、任意の有限次元において存在する。各次元 における超多面体を -次元（超）多面体 (-poly­tope) と呼ぶ。例えば二次元多面体は多角形、三次元多面体は通常の多面体である。多辺形や多面体のときと同様、「中身の詰まった」(solid) な -次元多面体だけでなく、一般にはその境界である図形を指して -次元多面体と呼ぶことが多々あるので、文脈に注意すべきである。 超多面体の更なる一般化として、非有界なや、曲がった多様体のや単体分割あるいは空間充填（例えば、、および集合論的ななどが現れる理論もある。 三次元より高次の超多面体を最初に考え出したのはである。ドイツの数学者によりpoly­topが造語され、それを として英語に導入したのはアメリカ人数学者のである。 語義は "poly-"（多くの）+ "-tope"（表面）であり「直訳」すれば「多面体」である。"" には多胞体（たほうたい）との訳語もある。これは頂点、辺、面に引き続く次元数 3 の部分を「胞」または「胞体」(cell) と呼ぶことから、多面体のより高次の対象との意図で用いられるものだが、しかし多数の胞からなる対象としての四次元の超多面体 (4-polytope) に限って多胞体と呼ぶ語法も自然である。なお、四次元超多面体には "poly­choron" (χώρος は「部屋」) との名称もある。 以下、誤解の虞があると思われる場合には多胞体の語はなるべく避けるものとする。.
新しい！!: K-頂点連結グラフとポリトープ · 続きを見る »
メンガーの定理
メンガーの定理（英: Menger's theorem）とは、グラフ理論および関連する数学の分野における定理であり、有限無向グラフに属する連結グラフに関する定理である。カール・メンガーが1927年、辺連結度と点連結度について見出した。辺連結度版のメンガーの定理は、後に最大フロー最小カット定理として一般化された。 辺連結度版のメンガーの定理は次の通りである。有限無向グラフ G で、x と y が隣接していない頂点であるとする。このとき、x と y の最小辺カット（辺切断。除去することで x と y が連結されなくなる最小の辺の数）の大きさは、x から y の辺独立経路 (辺素パス) の最大数と等しい。 点連結度版のメンガーの定理は次の通りである。有限無向グラフ G で、x と y が隣接していない頂点であるとする。このとき、x と y の最小点カット（点切断。除去することで x と y が連結されなくなる最小の頂点の数）の大きさは、x から y の頂点独立経路 (点素パス) の最大数と等しい。 メンガーの定理は、無限グラフでも成り立つことが証明されている（ポール・エルデシュが最初に推測していた）。.
新しい！!: K-頂点連結グラフとメンガーの定理 · 続きを見る »
グラフ理論
ラフ理論（グラフりろん、graph theory）は、ノード（節点・頂点）の集合とエッジ（枝・辺）の集合で構成されるグラフに関する数学の理論である。グラフ (データ構造) などの応用がある。.
新しい！!: K-頂点連結グラフとグラフ理論 · 続きを見る »
道 (グラフ理論)
有向閉道の例。矢印がなければ単なる閉道である。青い頂点は2度通るので、単純な閉道（すなわち閉路）ではない。 グラフ理論において、グラフの道（みち）またはパス（path）は、頂点の列であり、各頂点とその次の頂点との間に辺が存在する。道は無限の場合もあるが、有限な道には常に始点と終点がある。始点と終点をまとめて端子頂点 (terminal vertices) と呼び、道上の他の頂点を内部頂点 (internal vertices) と呼ぶ。閉道は始点と終点が同じ頂点となっている道である。なお、閉道においてどの頂点を始点とするかは任意である。 道と閉道はグラフ理論の基本的概念であり、グラフ理論の書籍では必ず導入部分で説明されている。例えば、Bondy and Murty (1976)、Gibbons (1985)、Diestel (2005)、Korte et al.
新しい！!: K-頂点連結グラフと道 (グラフ理論) · 続きを見る »
連結グラフ
連結グラフ（れんけつグラフ, connected graph）は、グラフ上の任意の2頂点間に道が存在するグラフのことである。連結でないグラフを非連結グラフ (disconnected graph) と呼ぶ。極大で連結な部分グラフは、連結成分 (connected component) という。.
新しい！!: K-頂点連結グラフと連結グラフ · 続きを見る »
K-辺連結グラフ
数学のグラフ理論において、あるグラフがk-辺連結（k-へんれんけつ、）であるとは辺連結度がk以上のグラフのことである。 言い換えると、グラフから k より少ない数の辺を除いてもであることを言う。.
新しい！!: K-頂点連結グラフとK-辺連結グラフ · 続きを見る »
数学
数学（すうがく、μαθηματικά, mathematica, math）は、量（数）、構造、空間、変化について研究する学問である。数学の範囲と定義については、数学者や哲学者の間で様々な見解がある。.
新しい！!: K-頂点連結グラフと数学 · 続きを見る »
2重連結グラフ
数学のグラフ理論における2重連結グラフ（2じゅうれんけつグラフ、）とは、任意の頂点が取り除かれても連結であるという意味で「分離不可能」なグラフのことを言う。したがって、2重連結グラフにはは存在しない。 2-連結であるという性質は、2重連結性と基本的に同値である。ただし、二つの頂点からなる完全グラフはしばしば、2重連結であるが2-連結ではないと見なされることに注意されたい。 この性質は特に、一つの辺（あるいは、接続）を取り除く際の非連結を防ぐための、グラフの2重冗長性を維持する上で有用である。 この冗長性に関する性質により、2重連結グラフは、ネットワークの分野（フローネットワークを参照されたい）において非常に重要となる。.
新しい！!: K-頂点連結グラフと2重連結グラフ · 続きを見る »
