日常の悩みを解決するブログ毎日のふとした困り事。その解決法がここにあるかもしれません。グラフ理論グラフ理論において、あるグラフが平面的であるかどうかを判定するための重要な定理があります。それは、クラトフスキーの定理です。このクラトフスキーの定理ですが、なぜこのような定理が成り立つのか、インターネットや本で調べてもなかなか証明が出てこないんですよね。「難しいので省略します」と。「いや、いや、そこが知りたいんですけど!」みたいな。あれば、この際、自分がクラトフスキーの定理の証明を分かりやすく解説しようと思い立ったわけです。クラトフスキーの定理の証明を知りたい人が日本で何人いるのかよく分かりませんが、もうアクセス数とかどうでもいいんです。「日本で最初にクラトフスキーの定理の証明を分かりやすく解説したサイトを作成した」これが重要なんです。自分の書いた記事が、グラフ理論を勉強する人たちの役に立てばそれで十分だと。前置きが長くなりましたが、早速行きましょう。個あり、すべての2頂点間に辺があるグラフのことです。\(K_{m,n}\)二部グラフとは、頂点が2つのグループに分けられ、同じグループの頂点同士は辺で結ばれていないグラフのことです。個の頂点グループがあり、異なるグループのすべての2頂点間に辺がある二部グラフのことです。非平面的グラフであることが知られています。細分とは、グラフの辺上に新たな頂点を0個以上加えて作ったグラフのことです。細分しても、それらを平面的グラフにすることはできません。細分して平面グラフになるなら、細分で加えた頂点を消去することで元のグラフも平面で描けることになってしまうからです。位相的マイナーである」といいます。クラトフスキーの定理グラフが平面的である。位相的マイナーとして持たない。左から右の証明は何となく理解できると思います。位相的マイナーを含む」ことの証明です。まとめクラトフスキーの定理を証明する記事の第1弾は、定理を紹介するだけで終わってしまいました。それなりに難しい定理ですからねぇ。次回は、いよいよ定理の証明に入っていきます。cue関連記事クラトフスキーの定理の証明(2)点連結度から1-連結の証明までクラトフスキーの定理の証明第2弾。点連結度の解説と最小の非平面的グラフが1-連結である証明まで。記事を読む四色問題の解き方。四色問題の塗り絵パズルアプリで、周りを4色で囲まれてしまい、行き詰まった時の対処法をお教えします。記事を読むクラトフスキーの定理の証明(7)そして完結へクラトフスキーの定理の証明第7弾。3-連結グラフが平面的であることを示し、ついに証明が完結します。記事を読むクラトフスキーの定理の証明(5)3-連結は平面的を証明する準備クラトフスキーの定理の証明第5弾。3-連結グラフが平面的になることを証明するための準備です。記事を読む四色問題とは何か?四色定理の歴史と塗り絵パズルのコツ四色問題(四色定理)の説明と塗り絵パズルのコツ、四色問題の歴史についての記事です。記事を読むクラトフスキーの定理の証明(6)3-連結は凸埋め込みを持つ証明クラトフスキーの定理の証明第6弾。凸多角形の説明と、3-連結グラフが凸埋め込みを持つ証明。四色問題の証明にあたり、双対グラフや平面グラフ、オイラーの多面体定理について解説しています。記事を読むクラトフスキーの定理の証明(3)誘導部分グラフから2-連結の証明クラトフスキーの定理の証明第3弾。記事を読むクラトフスキーの定理の証明(4)3-連結の証明と縮約・拡逆クラトフスキーの定理の証明第4弾。コメントをキャンセルメールアドレスが公開されることはありません。生活・暮らし人気記事一覧お悔やみメールの文例。友人や友達に硬くない文面を送りたいとき。初穂料の封筒の書き方。裏や金額の書き方を中袋なし、ありで解説。?申請書や70歳以上の区分と有効期限。パソコンの起動が遅い、動作が重いときはスタートアップの管理を!記号の読み方一覧。キーボードから数学、ギリシャまで。表面張力とは?原理を子供にもわかりやすく簡単に解説。中袋と外袋、縦書きと横書きについて解説。温度によって決まる?湿度の計算での求め方。日常の悩みを解決するブログ.。