Kuratowski's theorem (original) (raw)
Der Satz von Kuratowski (nach Kazimierz Kuratowski) ist ein Satz aus der Graphentheorie, der wichtige Aussagen zu planaren Graphen macht und die Frage nach der Planarität (Plättbarkeit) eines Graphen beantwortet.
| Property | Value |
|---|---|
| dbo:abstract | Der Satz von Kuratowski (nach Kazimierz Kuratowski) ist ein Satz aus der Graphentheorie, der wichtige Aussagen zu planaren Graphen macht und die Frage nach der Planarität (Plättbarkeit) eines Graphen beantwortet. (de) In graph theory, Kuratowski's theorem is a mathematical forbidden graph characterization of planar graphs, named after Kazimierz Kuratowski. It states that a finite graph is planar if and only if it does not contain a subgraph that is a subdivision of (the complete graph on five vertices) or of (a complete bipartite graph on six vertices, three of which connect to each of the other three, also known as the utility graph). (en) En teoría de grafos, el teorema de Kuratowski, desarrollado por el matemático polaco Kazimierz Kuratowski, es una caracterización de los grafos planares. (es) グラフ理論において、クラトフスキの定理（英：Kuratowski's theorem）とは、平面的グラフに対するを述べた定理である。カジミェシュ・クラトフスキにちなんで命名された。この定理は，有限グラフが平面的グラフであるためには、部分グラフとしてK5（5頂点の完全グラフ、五角形とその対角線5本からなる）やK3,3（3頂点ずつの完全2部グラフ、3つの頂点が他の3頂点とそれぞれ結ばれている）のを含まないことが必要十分であると述べる。 なお、K3,3は、の簡易な場合におけるグラフとしても知られている。 (ja) Na teoria dos grafos, o teorema de Kuratowski é uma de grafos planares, em homenagem a Kazimierz Kuratowski. O teorema declara que um é planar se, e somente se, ele não contém um subgrafo que é uma subdivisão da K5 (o grafo completo em cinco vértices) ou de K3 (grafo bipartido completo em seis vértices, três dos quais se conectam a cada um dos outros três), também conhecido como o gráfico de utilidade. (pt) Теорема Понтрягина — Куратовского, или теорема Куратовского, — теорема в теории графов, дающая необходимое и достаточное условие планарности графа.Имеет эквивалентную формулировку на языке миноров, так называемою теорему Вагнера. Теорема утверждает, что графы K5 (полный граф на 5 вершинах) и K3,3 (полный двудольный граф имеющий по 3 вершины в каждой доле) являются единственными минимальными непланарными графами. (ru) Kuratowskis sats är en matematisk sats inom grafteori som säger att en graf G är planär om och endast om det inte existerar någon delgraf av G som är med av eller . Satsen formulerades och bevisades av Kazimierz Kuratowski 1930. Denna artikel om kombinatorik eller diskret matematik saknar väsentlig information. Du kan hjälpa till genom att lägga till den. (sv) Twierdzenie Kuratowskiego – twierdzenie teorii grafów sformułowane i udowodnione przez Kazimierza Kuratowskiego w 1930 roku. (pl) Теорема Понтрягіна — Куратовського — теорема теорії графів, що дає необхідну й достатню умову планарності графу. Доведена в 1930 році польським математиком Казимиром Куратовським і незалежно від нього радянським математиком Понтрягіним. Однак останній не опублікував свого доведення, тому часто літературі теорема називається просто теоремою Куратовського. (uk) 库拉托夫斯基定理（英語：Kuratowski's theorem）是一个关于平面图的等价判定定理，它由波兰数学家卡齐米日·库拉托夫斯基提出。这个定理表明，一个图是平面图当且仅当它不包含K5 或 K3,3的细分。其中，K5是包含5个顶点的完全图，K3,3是包含6个顶点的完全二分图，其中三个顶点和另外三个顶点两两相连，K3,3也被称作。 (zh) |
| dbo:thumbnail | wiki-commons:Special:FilePath/GP92-Kuratowski.svg?width=300 |
| dbo:wikiPageID | 54493 (xsd:integer) |
| dbo:wikiPageLength | 9422 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1120387474 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Cubic_graph dbr:Line_segment dbc:Planar_graphs dbr:Complete_bipartite_graph dbr:Complete_graph dbr:Glossary_of_graph_theory dbr:Graph_minor dbr:Branch_and_cut dbr:Lev_Pontryagin dbr:Linear_time dbr:Path_(graph_theory) dbr:Fáry's_theorem dbr:Forbidden_graph_characterization dbr:Graph_drawing dbr:Graph_isomorphism dbr:Graph_theory dbr:Kelmans–Seymour_conjecture dbc:Theorems_in_graph_theory dbr:Karl_Menger dbr:Kazimierz_Kuratowski dbr:Homeomorphism_(graph_theory) dbr:Planar_graph dbr:Soviet_Union dbr:Orrin_Frink dbr:Proof_by_cases dbr:Utility_graph dbr:Vertex_(graph_theory) dbr:Euclidean_plane dbr:Euler_characteristic dbr:Planarity_testing dbr:Paul_Althaus_Smith dbr:Wagner's_theorem dbr:Robertson-Seymour_theorem dbr:Simple_curve dbr:Subdivision_(graph_theory) dbr:File:GP92-Kuratowski.svg |
| dbp:wikiPageUsesTemplate | dbt:Tesseract_graph_nonplanar_visual_proof.svg dbt:For dbt:Reflist dbt:Short_description |
| dct:subject | 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 Kuratowski (nach Kazimierz Kuratowski) ist ein Satz aus der Graphentheorie, der wichtige Aussagen zu planaren Graphen macht und die Frage nach der Planarität (Plättbarkeit) eines Graphen beantwortet. (de) In graph theory, Kuratowski's theorem is a mathematical forbidden graph characterization of planar graphs, named after Kazimierz Kuratowski. It states that a finite graph is planar if and only if it does not contain a subgraph that is a subdivision of (the complete graph on five vertices) or of (a complete bipartite graph on six vertices, three of which connect to each of the other three, also known as the utility graph). (en) En teoría de grafos, el teorema de Kuratowski, desarrollado por el matemático polaco Kazimierz Kuratowski, es una caracterización de los grafos planares. (es) グラフ理論において、クラトフスキの定理（英：Kuratowski's theorem）とは、平面的グラフに対するを述べた定理である。カジミェシュ・クラトフスキにちなんで命名された。この定理は，有限グラフが平面的グラフであるためには、部分グラフとしてK5（5頂点の完全グラフ、五角形とその対角線5本からなる）やK3,3（3頂点ずつの完全2部グラフ、3つの頂点が他の3頂点とそれぞれ結ばれている）のを含まないことが必要十分であると述べる。 なお、K3,3は、の簡易な場合におけるグラフとしても知られている。 (ja) Na teoria dos grafos, o teorema de Kuratowski é uma de grafos planares, em homenagem a Kazimierz Kuratowski. O teorema declara que um é planar se, e somente se, ele não contém um subgrafo que é uma subdivisão da K5 (o grafo completo em cinco vértices) ou de K3 (grafo bipartido completo em seis vértices, três dos quais se conectam a cada um dos outros três), também conhecido como o gráfico de utilidade. (pt) Теорема Понтрягина — Куратовского, или теорема Куратовского, — теорема в теории графов, дающая необходимое и достаточное условие планарности графа.Имеет эквивалентную формулировку на языке миноров, так называемою теорему Вагнера. Теорема утверждает, что графы K5 (полный граф на 5 вершинах) и K3,3 (полный двудольный граф имеющий по 3 вершины в каждой доле) являются единственными минимальными непланарными графами. (ru) Kuratowskis sats är en matematisk sats inom grafteori som säger att en graf G är planär om och endast om det inte existerar någon delgraf av G som är med av eller . Satsen formulerades och bevisades av Kazimierz Kuratowski 1930. Denna artikel om kombinatorik eller diskret matematik saknar väsentlig information. Du kan hjälpa till genom att lägga till den. (sv) Twierdzenie Kuratowskiego – twierdzenie teorii grafów sformułowane i udowodnione przez Kazimierza Kuratowskiego w 1930 roku. (pl) Теорема Понтрягіна — Куратовського — теорема теорії графів, що дає необхідну й достатню умову планарності графу. Доведена в 1930 році польським математиком Казимиром Куратовським і незалежно від нього радянським математиком Понтрягіним. Однак останній не опублікував свого доведення, тому часто літературі теорема називається просто теоремою Куратовського. (uk) 库拉托夫斯基定理（英語：Kuratowski's theorem）是一个关于平面图的等价判定定理，它由波兰数学家卡齐米日·库拉托夫斯基提出。这个定理表明，一个图是平面图当且仅当它不包含K5 或 K3,3的细分。其中，K5是包含5个顶点的完全图，K3,3是包含6个顶点的完全二分图，其中三个顶点和另外三个顶点两两相连，K3,3也被称作。 (zh) |
| rdfs:label | Satz von Kuratowski (de) Teorema de Kuratowski (es) Kuratowski's theorem (en) クラトフスキ定理 (ja) Twierdzenie Kuratowskiego (pl) Teorema de Kuratowski (pt) Теорема Понтрягина — Куратовского (ru) Kuratowskis sats (sv) 库拉托夫斯基定理 (zh) Теорема Понтрягіна — Куратовського (uk) |
| owl:sameAs | freebase:Kuratowski's theorem yago-res:Kuratowski's theorem wikidata:Kuratowski's theorem dbpedia-de:Kuratowski's theorem dbpedia-es:Kuratowski's theorem dbpedia-fa:Kuratowski's theorem dbpedia-fi:Kuratowski's theorem dbpedia-hu:Kuratowski's theorem dbpedia-ja:Kuratowski's theorem dbpedia-pl:Kuratowski's theorem dbpedia-pt:Kuratowski's theorem dbpedia-ru:Kuratowski's theorem dbpedia-sv:Kuratowski's theorem dbpedia-uk:Kuratowski's theorem dbpedia-vi:Kuratowski's theorem dbpedia-zh:Kuratowski's theorem https://global.dbpedia.org/id/4za24 |
| prov:wasDerivedFrom | wikipedia-en:Kuratowski's_theorem?oldid=1120387474&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/GP92-Kuratowski.svg |
| foaf:isPrimaryTopicOf | wikipedia-en:Kuratowski's_theorem |
| is dbo:knownFor of | dbr:Kazimierz_Kuratowski |
| is dbo:wikiPageRedirects of | dbr:Kuratowski_reduction_theorem dbr:Pontryagin-Kuratowski_theorem dbr:Pontryagin–Kuratowski_theorem dbr:Kuratowski_subgraph dbr:Kuratowski's_Theorem dbr:Kuratowski_theorem |
| is dbo:wikiPageWikiLink of | dbr:Eodermdrome dbr:David_Blackwell dbr:Library_of_Efficient_Data_types_and_Algorithms dbr:K5 dbr:Kuratowski_reduction_theorem dbr:Timeline_of_Polish_science_and_technology dbr:Complete_graph dbr:Essential_complexity dbr:Clique_problem dbr:Dan_Archdeacon dbr:Lev_Pontryagin dbr:Clique_(graph_theory) dbr:Matroid dbr:Certifying_algorithm dbr:Three_utilities_problem dbr:5 dbr:Forbidden_graph_characterization dbr:Outerplanar_graph dbr:Graph_Theory,_1736–1936 dbr:Graph_theory dbr:Hanani–Tutte_theorem dbr:Kelmans–Seymour_conjecture dbr:Karl_Menger dbr:Kazimierz_Kuratowski dbr:Homeomorphism_(graph_theory) dbr:Planar_graph dbr:Pontryagin-Kuratowski_theorem dbr:Pontryagin–Kuratowski_theorem dbr:Kuratowski_subgraph dbr:Klaus_Wagner dbr:FKT_algorithm dbr:Planarity_testing dbr:Structured_program_theorem dbr:Wagner's_theorem dbr:Kuratowski's_Theorem dbr:Kuratowski_theorem |
| is dbp:knownFor of | dbr:Kazimierz_Kuratowski |
| is foaf:primaryTopic of | wikipedia-en:Kuratowski's_theorem |
