Q&A

講演のテーマ・内容に関するQ&A

各講演に関してお寄せいただいた質問に講演者が回答しております。
上の顔写真をクリックして切り替えてください。

グラハム数を定義する時に3をもとにしているのはなぜですか？

テクニカルですが、自然な質問ですね。実は、グラハムの本論文は公表されておらず、グラハムの本ではもっと簡略化された証明が紹介されています。ですから、私もよくは存じません。質問をされた方は2の方がよいのではとおっしゃっておられますが、おそらく2よりも3の方が効率的な表現ができるということだと思います。2の2乗は4で、3を超えますので、それほど大きな違いはないと思います。

道路地図からグラフを作る際、道路には車線などいろいろあるけれどどうするのですか？

道路地図からグラフを作るとき、交差点を点、道路を線とするのが直感的ですね。実は、道路を点、交差点で接続している道路同士を線で結んでもグラフができます。これをライングラフといいます。この手法なら、車線という情報を落とさずに道路網をグラフ化できます。右折や左折、一方通行なども含めたければ、グラフの辺に向きをつけるという方法も考えられます。これを有向グラフと言います。グラフにはさまざまな構造を付加することができて、幅広い分野で応用されています。