ナ　チ　ュ　ー　ル

C 60周辺

グラフ理論

　そもそもグラフ理論で問題にされるグラフというのは何だろうか。ここでいうグラフとは、点(Vertices,V)と線(edges,E)の集合であって、棒グラフ、折れ線グラフ、円グラフ等の図式とは関係がない。ところが、化学者が自家薬篭中のものとして使っている構造式は、それをちょっと変形するだけで、たちまちグラフ理論家の絶好のターゲットとなってしまう。特に炭化水素のように、炭素原子１種類からできている骨格に炭素の原子価４を満足するように水素原子がぶら下がっているという分子の構造では、Ｃ原子＝点、ＣＣ結合＝線、という機械的な置き換えで、分子＝グラフという変換が完了してしまう。もちろんそれ以前に、少数の数学者がこの問題に注目していたのだが、化学者を長年悩ませていた異性体の数え上げの問題が数学的に非常に重要なものであると堂々と宣言したのが、今から６０年前の１９３６年のポリア(Polya)の論文である。1)
　ポリアは飽和炭化水素の異性体や誘導体の数を、幾何学的な直観や「目の子算」に頼らずに代数学的な計算によって求めることができるという、画期的な方法を考案した。彼の提出した数え上げ多項式とか、環指標という新しい概念は、置換群や組合せ理論の分野にも標準的な手法を提供して、それらの分野もグラフ理論と歩調を摘えて格段の進歩をとげることになった。
　このポリアの論文の丁度 200年前の1736年に、オイラー(Euler)は有名なケ－ニヒスベルグの７つの橋の問題を「グラフ理論的」に解いたのである。そして、科学史家達はこの年をもってグラフ理論の誕生の年としている。この長い200 年の間にこの分野にはめぼしい発見や発展がほとんどなかった。これは、オイラーの一筆書きの定理が、単にパズル的な応用の価値しかないと多くの人に思われていたのが一つの大きな理由であろう。
　さて、ポリアによって開花したグラフ理論と組合せ理論は、この後着実に成長して来たのだが、これらの数学が今日のように、自然科学だけでなく、人文社会の様々な分野からゲーム・パズルの領域にまで広く共通の言葉で語られ、かつ応用されるようになったのはハラリー(Harary)の業績である。即ち彼は1969年に名著「グラフ理論」を世に出して、この分野のプロパガンダ的な役割を果たした。2〕このように見てくると、グラフ理論の大きな貢献者は、オイラー、ポリア、ハラリーの３人ということができる。この３人に共適していることは、何れも純粋数学の畑で育ちながら、数学以外の分野にまで積極的に手を拡げて、しかもそれなりの収穫を得ていることであろう。オイラーの活躍した時代は、錬金術のレトルトの中から近代化学の種が昇華するはるか以前で、物理学者の目も天体の運動から地上の物にまだ移っていなかったので、残念ながら同時代の自然科学は彼の恩恵を受けることはできなかったのである。これが、オイラーの後を継ぐ仕事がなかなか出なかったもう一つの理由であろうか。ここでは、化学と関わりの大きいポリアの業績を簡単に紹介することにする。

ジャンル別一覧