-
正則
-
完全
グラフ理論プレイグラウンド
グラフとは、頂点と呼ばれる点の集まりを、辺と呼ばれる線で結んだものです。ここで数回クリックしてグラフを描くと、それがどんなグラフなのかをプレイグラウンドが教えてくれます。いくつの部分に分かれているか、木かどうか、最低何色で塗り分けられるか、一筆書きできるか、などです。性質をクリックするとグラフ上に表示されます。辺を変えて、答えが変わる様子を見てみましょう。 何もない所をクリックすると頂点を追加します。頂点をクリックしてから別の頂点をクリックすると、辺で結びます。もう一度同じ操作をすると辺を削除します。頂点はドラッグで移動できます。クリックを「消す」に切り替えて頂点や辺をクリックすると、削除できます。頂点を選択した状態では、Delete キーで削除、Escape キーで選択を解除します。性質をクリックすると、グラフ上に表示します。「例」は有名なグラフを読み込み、「ランダムグラフ」はグラフを作り、「整える」は頂点を広げて配置し、「補グラフ」はつながっていなかった頂点の組をちょうど結びます。Ctrl+Z で1ステップ元に戻します。
使い方
- 何もない所をクリックすると頂点を追加します。頂点をクリックしてから別の頂点をクリックすると結びます。もう一度すると辺を削除します。頂点はドラッグで移動できます。
- グラフの下に並ぶ性質を読み、クリックすると表示されます。彩色、2つの側、オイラー路、全域木、最短閉路、直径などです。
- ピーターセングラフなどの例を読み込んだり、ランダムグラフを作ったり、補グラフにしたり、クリックを「消す」に切り替えて頂点や辺を削除したりできます。
性質の意味
頂点の次数とは、その頂点につながる辺の数です。どの頂点からも辺をたどって他のすべての頂点に行けるとき、グラフは連結です。連結で閉路がなければ木です。頂点を2つの側に分けて、どの辺も両側をまたぐようにできるとき、グラフは二部グラフです。これは長さが奇数の閉路がないことと同じです。彩色数は、隣り合う頂点が違う色になるように塗るのに必要な最小の色数です。最短閉路の長さを内周といい、直径は2つの頂点の間の距離(辺の数で数える)の最大値です。
一筆書き
オイラー路は、すべての辺をちょうど1回ずつ通ります。1736年、レオンハルト・オイラーはケーニヒスベルクの7つの橋の問題から、何が妨げになるのかを見抜きました。道は頂点を通過するたびに、その頂点の辺を2本使います。したがって、すべての次数が偶数で出発点に戻ってこられるか、ちょうど2つの次数が奇数で、その一方から他方へ進むしかありません。のちにカール・ヒールホルツァーが、すべての辺がひとつながりなら、この条件で十分であることを証明しました。家の例を読み込んで、一筆書きをどこから始めればよいか探してみましょう。
よくある質問
グラフ理論でいうグラフとは?
頂点またはノードと呼ばれる点の集まりと、その一部の組を結ぶ、辺と呼ばれる線のことです。関数のグラフとは違い、何と何がつながっているかだけを表します。道路地図、ソーシャルネットワーク、分子、コンピュータネットワークはどれもグラフです。
彩色数はどうやって求めるのですか?
プレイグラウンドは、まず1色でグラフを塗ろうとし、次に2色、3色と増やしていきます。それぞれの色数について意味のある塗り方をすべて探し、そのとき常に、隣接する頂点がすでに最も多くの色を使っている頂点から先に塗ります。最初にうまくいった色数が彩色数です。ここで描けるグラフなら長くても一瞬で終わりますが、非常に難しいグラフでは探索を早めに打ち切り、値を上界として表示します。
グラフにオイラー路があるのはどんなときですか?
すべての辺がひとつながりで、次数が奇数の頂点が2つ以下のときです。奇数次の頂点がなければ、出発点に戻るオイラー閉路があります。2つあれば、どのオイラー路もその一方から始まり、もう一方で終わります。奇数次の頂点の数は必ず偶数なので、ちょうど1つになることはありません。
グラフの補グラフとは?
同じ頂点を持ち、元のグラフでつながっていなかった組をちょうど辺とするグラフです。補グラフの補グラフは元のグラフに戻ります。たとえばピーターセングラフの補グラフは 6-正則です。各頂点は他の 9 個のうち 3 個とつながっていたからです。
ピーターセングラフはなぜ有名なのですか?
頂点 10 個、辺 15 本の小さなグラフですが、期待を込めた多くの予想の反例になっています。どの頂点も次数は 3、最短閉路の長さは 5、どの2頂点も最大 2 本の辺で行き来でき、辺を交差させずに描くことはできません。プレイグラウンドはこのグラフから始まります。
試してみますか?
ブラウザで PictorX を開きます。インストール不要、始めるのにクレジットカードも不要です。
エディターへ