何かを書き留める何かスマートフォン用の表示で見る何かを書き留める何か数学や読んだ本について書く何かです。最近は社会人として生き残りの術を学ぶ日々です。Python前回、グラフの定義を行いその同型も定義した。今回は部分グラフについて書きたい。部分グラフあるグラフが別のグラフに含まれるとか含むという概念をまず定義する。$G,G'$をそれぞれグラフとする。あるとき、$G'$は$G$の部分グラフであるという。$V(G')$の頂点を両端点に含む辺をすべて含む部分グラフを$V(G')$から誘導される$G$の誘導部分グラフであるという。誘導部分グラフは頂点集合$V(G')$に対して辺集合が極大であるような部分グラフであるとも言える。普通は誘導部分グラフを考えることが多い(と私は思っている)。NetworkXでも簡単に部分グラフを作ることが出来る。2]$から誘導される道グラフを作成している。G.subgraph([0,1,2])H.edges()部分グラフに関する話で面白いのが、ある程度大きいグラフには必ずある部分グラフを含む、という話である。以下にその例を見ていきたい。print("Unbelievable!!!")上記のプログラムは頂点数6のランダムグラフを作り、三角形が1つでも存在するか独立点集合の位数が3以上ならばそれらしいメッセージを出力し、それ以外では"Unbelievable!!!"と返す。独立点集合とは互いに隣接していない、辺でつながっていない点の集合である。実は、"Unbelievable!!!"と返すことは無い。頂点数6以上のグラフには三角形か位数3以上の独立点集合が存在するのである。人数が増えるとある種のトラブルが発生するのと同じで、グラフも頂点数が増えると必ずある構造を含んでしまうのである。EC技術カンファレンスに参加しました私は統計警察でも統計ヤクザでもなければ無限警察でもない。»プロフィールid:XaroCydeykn数学や計算機、読んだ本について書くブログのような何かです。(1)最近人気の記事はてなブログをはじめよう!XaroCydeyknさんは、はてなブログを使っています。ブログを報告するスターをつけました引用をストックしましたストック一覧を見る閉じる引用するにはまずログインしてくださいログイン閉じる引用をストックできませんでした。再度お試しください閉じる限定公開記事のため引用できません。