Wagner's theorem (original) (raw)
Der Satz von Wagner, englisch Wagner’s theorem, ist ein Lehrsatz aus dem mathematischen Teilgebiet der Topologischen Graphentheorie, welcher im Jahre 1937 von dem Mathematiker Klaus Wagner veröffentlicht wurde. Der Satz ist verwandt mit dem Satz von Kuratowski und gibt wie dieser eine Charakterisierung plättbarer Graphen.
| Property | Value |
|---|---|
| dbo:abstract | Der Satz von Wagner, englisch Wagner’s theorem, ist ein Lehrsatz aus dem mathematischen Teilgebiet der Topologischen Graphentheorie, welcher im Jahre 1937 von dem Mathematiker Klaus Wagner veröffentlicht wurde. Der Satz ist verwandt mit dem Satz von Kuratowski und gibt wie dieser eine Charakterisierung plättbarer Graphen. (de) En teoría de grafos, el teorema de Wagner es una caracterización de grafos prohibidos en grafos planos, llamado así por . El teorema establece que un grafo finito es plano si y solo si sus menores no incluyen a K5 (el grafo completo con cinco vértices) ni a K3,3 (el grafo del problema de los tres servicios, un grafo bipartito completo con seis vértices). Este fue uno de los primeros resultados en la teoría de menores y puede verse como un precursor del . (es) In graph theory, Wagner's theorem is a mathematical forbidden graph characterization of planar graphs, named after Klaus Wagner, stating that a finite graph is planar if and only if its minors include neither K5 (the complete graph on five vertices) nor K3,3 (the utility graph, a complete bipartite graph on six vertices). This was one of the earliest results in the theory of graph minors and can be seen as a forerunner of the Robertson–Seymour theorem. (en) Теорема Вагнера — характеризация планарных графов тесно связанная с теоремой Понтрягина — Куратовского. Названа в честь Клауса Вагнера. Теорема утверждает, что конечный граф является планарным тогда и только тогда, когда его миноры не включают ни K5 (полный граф с пятью вершинами), ни K3,3 (коммунальный граф, полный двудольный граф с тремя вершинами в каждой доле).Теорема была одной из наиболее ранних работ в теории миноров графа и её можно рассматривать как предшественницу теоремы Робертсона — Сеймура. (ru) 在图论中，瓦格纳理论（英：Wagner's theorem）是平面图的禁图表征，以Klaus Wagner的命名。 该定理说：当且仅当有限图的子式不包含完全图K5 或完全二分图K3,3 时候，那么该图就是平面的。 这是图子式论最早的结果之一，也是罗伯逊–西摩定理（Robertson-Seymour theorem）的先驱。 (zh) Теорема Вагнера — характеризація планарних графів, тісно пов'язана з теоремою Понтрягіна — Куратовського. Названа на честь . Теорема стверджує, що скінченний граф є планарним тоді й лише тоді, коли серед його мінорів немає ні K5 (повний граф із п'ятьма вершинами), ні K3,3 (комунальний граф, повний двочастковий граф із трьома вершинами в кожній частці). Теорема є однією з найраніших робіт у теорії мінорів графа і її можна розглядати як попередницю теореми Робертсона — Сеймура. (uk) |
| dbo:thumbnail | wiki-commons:Special:FilePath/Petersen_Wagner_minors.svg?width=300 |
| dbo:wikiPageID | 3126130 (xsd:integer) |
| dbo:wikiPageLength | 7820 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1094648407 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Multigraph dbr:Topological_minor dbc:Graph_minor_theory dbr:Kuratowski's_theorem dbr:Robertson–Seymour_theorem dbc:Planar_graphs dbr:Complete_bipartite_graph dbr:Complete_graph dbr:Clique-sum dbr:Graph_(discrete_mathematics) dbr:Graph_minor dbr:Graph_structure_theorem dbr:Path_(graph_theory) dbr:Matroid dbr:Matroid_minor dbr:Wagner_graph dbr:K-vertex-connected_graph dbr:Edge_(graph_theory) dbr:Forbidden_graph_characterization dbr:Graph_drawing dbr:Graph_embedding dbr:Graph_theory dbr:Graphic_matroid dbr:Kelmans–Seymour_conjecture dbc:Theorems_in_graph_theory dbr:Planar_graph dbr:Klaus_Wagner dbr:Utility_graph dbr:Vertex_(graph_theory) dbr:Euclidean_plane dbr:Subdivision_(graph_theory) dbr:File:Clique-sum.svg dbr:File:Petersen_Wagner_minors.svg |
| dbp:wikiPageUsesTemplate | dbt:Tesseract_graph_nonplanar_visual_proof.svg dbt:Reflist dbt:Short_description dbt:Use_American_English |
| dcterms:subject | dbc:Graph_minor_theory dbc:Planar_graphs dbc:Theorems_in_graph_theory |
| gold:hypernym | dbr:Characterization |
| rdf:type | yago:WikicatTheoremsInGraphTheory yago:Abstraction100002137 yago:Communication100033020 yago:Graph107000195 yago:Message106598915 yago:Proposition106750804 yago:Statement106722453 yago:Theorem106752293 yago:VisualCommunication106873252 yago:WikicatPlanarGraphs |
| rdfs:comment | Der Satz von Wagner, englisch Wagner’s theorem, ist ein Lehrsatz aus dem mathematischen Teilgebiet der Topologischen Graphentheorie, welcher im Jahre 1937 von dem Mathematiker Klaus Wagner veröffentlicht wurde. Der Satz ist verwandt mit dem Satz von Kuratowski und gibt wie dieser eine Charakterisierung plättbarer Graphen. (de) En teoría de grafos, el teorema de Wagner es una caracterización de grafos prohibidos en grafos planos, llamado así por . El teorema establece que un grafo finito es plano si y solo si sus menores no incluyen a K5 (el grafo completo con cinco vértices) ni a K3,3 (el grafo del problema de los tres servicios, un grafo bipartito completo con seis vértices). Este fue uno de los primeros resultados en la teoría de menores y puede verse como un precursor del . (es) In graph theory, Wagner's theorem is a mathematical forbidden graph characterization of planar graphs, named after Klaus Wagner, stating that a finite graph is planar if and only if its minors include neither K5 (the complete graph on five vertices) nor K3,3 (the utility graph, a complete bipartite graph on six vertices). This was one of the earliest results in the theory of graph minors and can be seen as a forerunner of the Robertson–Seymour theorem. (en) Теорема Вагнера — характеризация планарных графов тесно связанная с теоремой Понтрягина — Куратовского. Названа в честь Клауса Вагнера. Теорема утверждает, что конечный граф является планарным тогда и только тогда, когда его миноры не включают ни K5 (полный граф с пятью вершинами), ни K3,3 (коммунальный граф, полный двудольный граф с тремя вершинами в каждой доле).Теорема была одной из наиболее ранних работ в теории миноров графа и её можно рассматривать как предшественницу теоремы Робертсона — Сеймура. (ru) 在图论中，瓦格纳理论（英：Wagner's theorem）是平面图的禁图表征，以Klaus Wagner的命名。 该定理说：当且仅当有限图的子式不包含完全图K5 或完全二分图K3,3 时候，那么该图就是平面的。 这是图子式论最早的结果之一，也是罗伯逊–西摩定理（Robertson-Seymour theorem）的先驱。 (zh) Теорема Вагнера — характеризація планарних графів, тісно пов'язана з теоремою Понтрягіна — Куратовського. Названа на честь . Теорема стверджує, що скінченний граф є планарним тоді й лише тоді, коли серед його мінорів немає ні K5 (повний граф із п'ятьма вершинами), ні K3,3 (комунальний граф, повний двочастковий граф із трьома вершинами в кожній частці). Теорема є однією з найраніших робіт у теорії мінорів графа і її можна розглядати як попередницю теореми Робертсона — Сеймура. (uk) |
| rdfs:label | Satz von Wagner (de) Teorema de Wagner (es) Wagner's theorem (en) Теорема Вагнера (ru) 瓦格纳定理 (zh) Теорема Вагнера (uk) |
| owl:sameAs | freebase:Wagner's theorem wikidata:Wagner's theorem dbpedia-de:Wagner's theorem dbpedia-es:Wagner's theorem dbpedia-ru:Wagner's theorem dbpedia-uk:Wagner's theorem dbpedia-zh:Wagner's theorem https://global.dbpedia.org/id/4xjiX yago-res:Wagner's theorem |
| prov:wasDerivedFrom | wikipedia-en:Wagner's_theorem?oldid=1094648407&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/Clique-sum.svg wiki-commons:Special:FilePath/Petersen_Wagner_minors.svg |
| foaf:isPrimaryTopicOf | wikipedia-en:Wagner's_theorem |
| is dbo:wikiPageWikiLink of | dbr:Mac_Lane's_planarity_criterion dbr:Pathwidth dbr:Petersen_family dbr:Kuratowski's_theorem dbr:Pseudoforest dbr:Robertson–Seymour_theorem dbr:Complete_bipartite_graph dbr:Complete_graph dbr:Glossary_of_graph_theory dbr:Graph_minor dbr:Graph_structure_theorem dbr:Clique_(graph_theory) dbr:Matroid_minor dbr:Wagner_graph dbr:Three_utilities_problem dbr:Forbidden_graph_characterization dbr:Outerplanar_graph dbr:Graph_theory dbr:Graphic_matroid dbr:Kelmans–Seymour_conjecture dbr:Hadwiger_conjecture_(graph_theory) dbr:Hadwiger_number dbr:Planar_graph dbr:Klaus_Wagner dbr:List_of_theorems dbr:Planarity_testing dbr:Pfaffian_orientation dbr:Twin-width |
| is foaf:primaryTopic of | wikipedia-en:Wagner's_theorem |
