クラトフスキ定理
表示
![]() |
![](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の簡易な場合におけるグラフとしても知られている。