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).
| Attributes | Values |
|---|
| rdf:type
| |
| 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)
|
| 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)
|
| foaf:depiction
| |
| dcterms:subject
| |
| Wikipage page ID
| |
| Wikipage revision ID
| |
| Link from a Wikipage to another Wikipage
| |
| sameAs
| |
| dbp:wikiPageUsesTemplate
| |
| thumbnail
| |
| has 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)
|
![[RDF Data]](/fct/images/sw-rdf-blue.png)
![[cxml]](/fct/images/cxml_doc.png)
![[csv]](/fct/images/csv_doc.png)
![[text]](/fct/images/ntriples_doc.png)
![[turtle]](/fct/images/n3turtle_doc.png)
![[ld+json]](/fct/images/jsonld_doc.png)
![[rdf+json]](/fct/images/json_doc.png)
![[rdf+xml]](/fct/images/xml_doc.png)
![[atom+xml]](/fct/images/atom_doc.png)
![[html]](/fct/images/html_doc.png)
