「クラトフスキ定理」の版間の差分
表示
削除された内容 追加された内容
m編集の要約なし |
編集の要約なし |
||
(7人の利用者による、間の11版が非表示) | |||
1行目: | 1行目: | ||
{{複数の問題 |
{{複数の問題 |
||
| 出典の明記 = 2019年4月 |
| 出典の明記 = 2019年4月 |
||
| 孤立 = 2020年9月 |
|||
| Wikify = 2019年4月 |
|||
| 要改訳 = 2019年4月 |
| 要改訳 = 2019年4月 |
||
}} |
}} |
||
{{Expand English|Kuratowski's theorem|date=2024年5月}} |
|||
{{表記揺れ案内|表記1=クラトフスキーの定理}} |
{{表記揺れ案内|表記1=クラトフスキーの定理}} |
||
[[ファイル:GP92-Kuratowski.svg|サムネイル|240x240ピクセル| {{仮リンク|一般化ピーターセングラフ|en|Generalized_Petersen_graph|label=一般化ピーターセングラフ}}G(9, 2) |
[[ファイル:GP92-Kuratowski.svg|サムネイル|240x240ピクセル| {{仮リンク|一般化ピーターセングラフ|en|Generalized_Petersen_graph|label=一般化ピーターセングラフ}}G(9, 2)は''K''<sub>3,3</sub>(緑の点が青い3点と、青い点が緑の3点と接続している)の[[細分]]を含むため、平面的グラフではない。]] |
||
[[グラフ理論]]において、'''クラトフスキの定理'''(英:Kuratowski's theorem)とは、[[平面グラフ]]に対する{{仮リンク|禁止グラフの特徴づけ|en|Forbidden graph characterization|label=}}を述べた定理である。[[カジミェシュ・クラトフスキ]]にちなんで命名された。この定理は,有限グラフが平面グラフであるためには、部分グラフとして''K''<sub>5</sub>(5 |
[[グラフ理論]]において、'''クラトフスキの定理'''(英:Kuratowski's theorem)とは、[[平面的グラフ]]に対する{{仮リンク|禁止グラフの特徴づけ|en|Forbidden graph characterization|label=}}を述べた定理である。[[カジミェシュ・クラトフスキ]]にちなんで命名された。この定理は,有限グラフが平面的グラフであるためには、部分グラフとして''K''<sub>5</sub>(5[[頂点 (グラフ理論)|頂点]]の[[完全グラフ]]、五角形とその対角線5本からなる)や''K''<sub>3,3</sub>(3頂点ずつの[[完全2部グラフ]]、3つの頂点が他の3頂点とそれぞれ結ばれている)の[[細分]]を含まないことが必要十分であると述べる。 |
||
なお、''K''<sub>3,3</sub>は、{{仮リンク|utility graph|en|Three utilities problem|label=utility graph}}の簡易な場合におけるグラフとしても知られている。 |
|||
== 脚注 == |
== 脚注 == |
||
14行目: | 15行目: | ||
{{Math-stub}} |
{{Math-stub}} |
||
⚫ | |||
⚫ | |||
[[Category:グラフ理論の定理]] |
[[Category:グラフ理論の定理]] |
||
[[Category:数学に関する記事]] |
2024年5月24日 (金) 19:17時点における最新版
![]() |
![]() | この記事は英語版の対応するページを翻訳することにより充実させることができます。(2024年5月) 翻訳前に重要な指示を読むには右にある[表示]をクリックしてください。
|
![](http://upload.wikimedia.org/wikipedia/commons/thumb/7/73/GP92-Kuratowski.svg/240px-GP92-Kuratowski.svg.png)
グラフ理論において、クラトフスキの定理(英:Kuratowski's theorem)とは、平面的グラフに対する禁止グラフの特徴づけを述べた定理である。カジミェシュ・クラトフスキにちなんで命名された。この定理は,有限グラフが平面的グラフであるためには、部分グラフとしてK5(5頂点の完全グラフ、五角形とその対角線5本からなる)やK3,3(3頂点ずつの完全2部グラフ、3つの頂点が他の3頂点とそれぞれ結ばれている)の細分を含まないことが必要十分であると述べる。
なお、K3,3は、utility graphの簡易な場合におけるグラフとしても知られている。