総合大会 パネル討論報告
「グラフネットワークの応用と展望」田村 裕 (新潟工科大) |
3月29日(水)午後，2000年総合大会において， 回路とシステム(CAS)研究専門委員会の企画による標記パネル討論が行われた． 最初に，座長をお願いした豊橋技科大の増山繁氏が グラフネットワーク理論の歴史について概説され， 現在は「情報技術(IT)」と「情報通信網」の発展に伴い， 「ネットワークの大規模化」と「関連した新しい問題の出現」が 重要なポイントとなっているとの指摘があった． 今回のパネリストの方々の講演もこれに沿った形となった．
インターネットを代表とする巨大ネットワークでは， ネットワーク全体を把握するのは難しい． そのため，全体を把握できない， またはそれが困難なネットワークに関するグラフ理論が必要である． ここでは，点に計算能力があるような通信ネットワークを仮定し， 比較的現実に近いモデルと， データの流れに注目した単純なモデルについての結果が報告された．
インターネットの発展に伴い， ネットワークを介したマルチメディア環境が一般的になりつつある． これは，クライアントがマルチメディアサービスを提供するサーバと 通信を行うことで実現される． この場合，各点(クライアントを表す)と点のある集合(サーバを表す)との 通信の確保が必要である． この概念をモデル化した接点領域連結性についての結果が報告された．
抽象的な関係や構造を表現するためにグラフがよく使われるが， それを``適切に''描画することにより，複雑な概念を簡潔に表現したり， 全体の構造を感覚的に把握することが可能となる． この研究では，点数は高々数百程度である (これ以上多いと，人間が構造を感覚的に把握することが困難) ので，NP完全性の議論から離れたところにある． また，描画というジャンルよりデザイン等の他分野の研究者が多いのも特徴である．
LSI CADは代表的な大規模グラフネットワーク問題である． トランジスタ数にして一千万を超え，それをつなぐ配線線分などを含め， LSIマスクパターンを表現する要素は膨大となってきている． 現在のLSI設計は大きく分けて，機能設計，論理設計， レイアウト設計となるが，どの部分でもグラフ理論やアルゴリズム分野の 手法が用いられることが多い．
最後に，上記講演とは異なり， 教育分野でグラフ理論の問題がいかに扱われているかの報告があった． 最短路等のグラフ理論における代表的な問題は，応用が広い， 視覚的で取り組みやすい，高度な知識は不要等の理由から プログラミング演習問題として適当である． そこで，C言語に限定して市販の初級者用演習書を調べたが， グラフ・ネットワーク理論に関連した問題はほとんど採用されていない という残念な結果となった．
例えばLSIの設計にかかわる人は， グラフ理論やアルゴリズムは勉強しておいて欲しいというように， 基礎理論としては重要である． しかしながら，グラフは主として静的なものしか扱えない等， 基礎研究と応用研究には乖離が存在する．
モデルは明確だが， これは複雑な部分をそぎ落としてシンプルにしているからである． よって，逆にいうと現実とのギャップが大きいということになる． しかしながら， 現実とのギャップは他の分野でも存在する． いかに基礎研究の成果を生かすかが重要であり， その点の努力が必要であろう．
IT関連は大変活発であるが，computer science全体の研究はそれほどではない．
大学等で現在活発な分野の話をうまく取り入れた講義ができないものか．
例えば，Javaを使ったグラフ理論やアルゴリズムなど．また，
基礎理論であるゆえ，使った結果がわかりやすい形で製品等の表面にでない．
これが研究者が増えない理由ではないか．
研究者が面白いと思ってやっているだけだとそこで閉じてしまう．
外部に向かった働きかけが大切であろう．
例えば，回路設計やLSI設計にグラフネットワーク理論は使える，
との認識で研究が盛んになった．
これからの研究の主役となるのはITであり情報ネットワークである．
これらにグラフ理論は使えると啓蒙し，結果を出すことが重要である．
将来プログラミングに関わる職業につく人は， アルゴリズムやグラフ理論をよく勉強して欲しいとの意見があった． 現在はまだ時間的にも不足しており，興味を持てるような環境が十分ではない． これについて，例えば，中学，高校生のプログラミングの勉強には 最短路等の問題は適当ではないか． 情報が高校で必修となることもありよいチャンスであろう． また，グラフはリレーションの学習に適している． 集合，写像がうまく扱える等の利点もある．