Balinski's theorem (original) (raw)
数学の一分野であるにおけるバリンスキーの定理（バリンスキーのていり、英: Balinski's theorem）とは、三次元多面体およびより高次元のポリトープの持つグラフ理論的構造に関する定理である。あるd-次元凸多面体あるいはポリトープ（その）の頂点と辺から無向グラフを形成するとき、そのグラフは少なくともd-頂点連結（すなわち、どのような d − 1 個の頂点を取り除いても、残されたグラフは連結）である、ということを述べた定理である。例えば、三次元のある多面体に対して、その頂点の内の二つ（およびそれらに接続している辺）が取り除かれたとしても、残された任意の頂点のペアにはそれらをつなぐ頂点と辺の路が存在する。 バリンスキーの定理は、その証明を1961年に与えた数学者のミシェル・L・バリンスキーの名にちなむ。しかし三次元の場合については二十世紀初頭に、三次元多面体のグラフは3-連結平面グラフであるというとして結果が得られていた。
| Property | Value |
|---|---|
| dbo:abstract | In polyhedral combinatorics, a branch of mathematics, Balinski's theorem is a statement about the graph-theoretic structure of three-dimensional convex polyhedra and higher-dimensional convex polytopes. It states that, if one forms an undirected graph from the vertices and edges of a convex d-dimensional convex polyhedron or polytope (its skeleton), then the resulting graph is at least d-vertex-connected: the removal of any d − 1 vertices leaves a connected subgraph. For instance, for a three-dimensional polyhedron, even if two of its vertices (together with their incident edges) are removed, for any pair of vertices there will still exist a path of vertices and edges connecting the pair. Balinski's theorem is named after mathematician Michel Balinski, who published its proof in 1961, although the three-dimensional case dates back to the earlier part of the 20th century and the discovery of Steinitz's theorem that the graphs of three-dimensional polyhedra are exactly the three-connected planar graphs. (en) En combinatoria poliédrica, una rama de las matemáticas, el teorema de Balinski es una declaración acerca de la estructura de la teoría de grafos de poliedros tridimensionales y politopos de dimensiones superiores. Afirma que, si uno forma un grafo no dirigido desde los vértices y aristas de un poliedro d-tridimensional convexo o politopo (su esqueleto), entonces la gráfica resultante es al menos d-vértices conectados: la eliminación de cualquier d - 1 vértices deja un subgrafo conexo. Por ejemplo, para un poliedro tridimensional, incluso si dos de sus vértices (junto con sus bordes incidentes) se eliminan, para cualquier par de vértices todavía existirá un camino de vértices y aristas que conectan el par. El teorema de Balinski se llama así por el matemático , quien publicó su demostración en 1961, aunque el caso tridimensional se remonta a la primera parte del siglo XX y el descubrimiento del que las gráficas de poliedros tridimensionales son exactamente los tres grafos planos conectados. (es) 数学の一分野であるにおけるバリンスキーの定理（バリンスキーのていり、英: Balinski's theorem）とは、三次元多面体およびより高次元のポリトープの持つグラフ理論的構造に関する定理である。あるd-次元凸多面体あるいはポリトープ（その）の頂点と辺から無向グラフを形成するとき、そのグラフは少なくともd-頂点連結（すなわち、どのような d − 1 個の頂点を取り除いても、残されたグラフは連結）である、ということを述べた定理である。例えば、三次元のある多面体に対して、その頂点の内の二つ（およびそれらに接続している辺）が取り除かれたとしても、残された任意の頂点のペアにはそれらをつなぐ頂点と辺の路が存在する。 バリンスキーの定理は、その証明を1961年に与えた数学者のミシェル・L・バリンスキーの名にちなむ。しかし三次元の場合については二十世紀初頭に、三次元多面体のグラフは3-連結平面グラフであるというとして結果が得られていた。 (ja) Теорема Балинского — это утверждение относительно структуры графа многогранника размерности 3 и выше. Теорема утверждает, что если образовать неориентированный граф из вершин и рёбер выпуклого d-мерного многогранника (его ), то полученный граф по меньшей мере вершинно d-связен — удаление любого набора из d − 1 вершин оставляет связный подграф. Например, для трёхмерного многогранника, если удалить две вершины (вместе с инцидентными им рёбрами), для любой пары вершин существует путь, соединяющий эту пару. Теорема Балинского названа именем математика , опубликовавшего доказательство в 1961, хотя доказательство трёхмерного случая датируется началом 20-го века (теорема Штайница, что графы трёхмерных многогранников — это в точности трёхсвязные планарные графы). (ru) |
| dbo:thumbnail | wiki-commons:Special:FilePath/Balinski.svg?width=300 |
| dbo:wikiPageID | 24732291 (xsd:integer) |
| dbo:wikiPageLength | 3738 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1033302798 (xsd:integer) |
| dbo:wikiPageWikiLink | dbc:Graph_connectivity dbr:Undirected_graph dbr:Polyhedron dbr:Connectivity_(graph_theory) dbc:Theorems_in_discrete_geometry dbr:Convex_polytope dbr:Steinitz's_theorem dbr:Linear_programming dbc:Polyhedral_combinatorics dbr:Graph_theory dbc:Theorems_in_graph_theory dbr:Polyhedral_combinatorics dbr:Michel_Balinski dbr:Skeleton_(topology) dbr:Simplex_method dbr:File:Balinski.svg |
| dbp:wikiPageUsesTemplate | dbt:Reflist dbt:Short_description |
| dct:subject | dbc:Graph_connectivity dbc:Theorems_in_discrete_geometry dbc:Polyhedral_combinatorics dbc:Theorems_in_graph_theory |
| gold:hypernym | dbr:Statement |
| rdf:type | yago:WikicatTheoremsInDiscreteGeometry yago:WikicatTheoremsInGraphTheory yago:Abstraction100002137 yago:Communication100033020 yago:Message106598915 yago:Proposition106750804 yago:Statement106722453 yago:Theorem106752293 |
| rdfs:comment | 数学の一分野であるにおけるバリンスキーの定理（バリンスキーのていり、英: Balinski's theorem）とは、三次元多面体およびより高次元のポリトープの持つグラフ理論的構造に関する定理である。あるd-次元凸多面体あるいはポリトープ（その）の頂点と辺から無向グラフを形成するとき、そのグラフは少なくともd-頂点連結（すなわち、どのような d − 1 個の頂点を取り除いても、残されたグラフは連結）である、ということを述べた定理である。例えば、三次元のある多面体に対して、その頂点の内の二つ（およびそれらに接続している辺）が取り除かれたとしても、残された任意の頂点のペアにはそれらをつなぐ頂点と辺の路が存在する。 バリンスキーの定理は、その証明を1961年に与えた数学者のミシェル・L・バリンスキーの名にちなむ。しかし三次元の場合については二十世紀初頭に、三次元多面体のグラフは3-連結平面グラフであるというとして結果が得られていた。 (ja) In polyhedral combinatorics, a branch of mathematics, Balinski's theorem is a statement about the graph-theoretic structure of three-dimensional convex polyhedra and higher-dimensional convex polytopes. It states that, if one forms an undirected graph from the vertices and edges of a convex d-dimensional convex polyhedron or polytope (its skeleton), then the resulting graph is at least d-vertex-connected: the removal of any d − 1 vertices leaves a connected subgraph. For instance, for a three-dimensional polyhedron, even if two of its vertices (together with their incident edges) are removed, for any pair of vertices there will still exist a path of vertices and edges connecting the pair. (en) En combinatoria poliédrica, una rama de las matemáticas, el teorema de Balinski es una declaración acerca de la estructura de la teoría de grafos de poliedros tridimensionales y politopos de dimensiones superiores. Afirma que, si uno forma un grafo no dirigido desde los vértices y aristas de un poliedro d-tridimensional convexo o politopo (su esqueleto), entonces la gráfica resultante es al menos d-vértices conectados: la eliminación de cualquier d - 1 vértices deja un subgrafo conexo. Por ejemplo, para un poliedro tridimensional, incluso si dos de sus vértices (junto con sus bordes incidentes) se eliminan, para cualquier par de vértices todavía existirá un camino de vértices y aristas que conectan el par. (es) Теорема Балинского — это утверждение относительно структуры графа многогранника размерности 3 и выше. Теорема утверждает, что если образовать неориентированный граф из вершин и рёбер выпуклого d-мерного многогранника (его ), то полученный граф по меньшей мере вершинно d-связен — удаление любого набора из d − 1 вершин оставляет связный подграф. Например, для трёхмерного многогранника, если удалить две вершины (вместе с инцидентными им рёбрами), для любой пары вершин существует путь, соединяющий эту пару. (ru) |
| rdfs:label | Satz von Balinski (de) Balinski's theorem (en) Teorema de Balinski (es) バリンスキーの定理 (ja) Теорема Балинского (ru) |
| owl:sameAs | freebase:Balinski's theorem yago-res:Balinski's theorem wikidata:Balinski's theorem dbpedia-de:Balinski's theorem dbpedia-es:Balinski's theorem dbpedia-hu:Balinski's theorem dbpedia-ja:Balinski's theorem dbpedia-ro:Balinski's theorem dbpedia-ru:Balinski's theorem https://global.dbpedia.org/id/2ybzo |
| prov:wasDerivedFrom | wikipedia-en:Balinski's_theorem?oldid=1033302798&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/Balinski.svg |
| foaf:isPrimaryTopicOf | wikipedia-en:Balinski's_theorem |
| is dbo:knownFor of | dbr:Michel_Balinski |
| is dbo:wikiPageWikiLink of | dbr:Hypercube_graph dbr:List_of_Williams_College_people dbr:Connectivity_(graph_theory) dbr:Steinitz's_theorem dbr:K-vertex-connected_graph dbr:Edge_(geometry) dbr:Polyhedral_combinatorics dbr:Michel_Balinski dbr:List_of_theorems dbr:Polyhedral_graph |
| is dbp:knownFor of | dbr:Michel_Balinski |
| is foaf:primaryTopic of | wikipedia-en:Balinski's_theorem |
