最終講義

「点　と　辺」（Vertices and Edges）

西関　隆夫（情報科学研究科教授）

１．はじめに

　どうも過分なご紹介をいただき有難うございます．

　本日の講義のタイトルを「点と辺」にしました．皆様はこのタイトルから何を連想するでしょうか．年配の方は，きっと松本清張の推理小説「点と線」を思い浮かべるでしょう．最近ビートたけし主演でテレビドラマ化もされたので，若い方も知っているでしょう．清張は列車ダイヤグラムや点と線を結ぶ推理を，このタイトルで表したかったのでしょう．初版本のカバーには「点」と「線」が描かれています．私はこの「線」を「辺」と呼んでいます．点と辺の集まりは「グラフ」と呼ばれております．グラフ理論やグラフアルゴリズムの研究を大学院生，助手，助教授，教授，そして定年になるまで，バカの一つ覚えのように，約40年間も続けてきました．コツコツと1つのことを忍耐強く続けるのが東北大学電気系の伝統ではありますが，どのような経緯で点と辺の世界に耽けることになったのか，今まで話したことがないので，本日はこの話をします．

２．学部時代

　須賀川高校という田舎の高校を卒業して，昭和40年に東北大学工学部に入学しました．入学手続きをして下宿に帰る途中，4月の第１週で冷たい風が吹いている中を，広瀬川に架かる「仲の瀬橋」を渡っていたときのことですが，これはもう明確に記憶しているのですが，「大学を卒業したら会社に勤めて技術者になって金儲けをするようなことはしないで，大学院に進もう．大学院を修了したら，大学の先生になって，大学生を教えたり，人類の役に立つ科学技術の研究をしよう」と，入学式前にこれは本当に心に誓いました．何の根拠もなかったし，自分にそんな能力があるとも思っていませんでした．でも田舎の高校から東北大に入るくらいの努力をすれば，仙台や東京など都会の，パンツの紐が伸びきったような学生相手なら，何とかなるだろうという，“カラ”自信みたいなものがありました．　

昭和42年の年末，通信工学科の3年生の時にPCM（Pulse Code Modulation）通信の研究がしたくて，喜安善市教授の研究室（回路網学講座）に配属を希望して，無事に喜安研に配属になりました．斎藤伸自先生は当時喜安研の助教授で，回路網の研究をなさっておりました．せっかく喜安研に配属になったのですが，4年生になった昭和43年4月に喜安先生は（株）岩崎通信機に移られてしまいました．ともかく，このようにして喜安研OBの会の末席を汚すことになりました．

回路網学講座の初代教授は永井健三先生で，伝送回路網や磁気記録で有名です．第二代は喜安善市先生で，PCM通信，回路合成，パラメトロン計算機で有名です．第三代は斎藤伸自先生で分布定数回路合成論が有名です．

4年生の卒論の指導は当時博士課程3年生の千葉信行さんがしてくれました．千葉さんの指導の下でまとめたのが処女論文「不確定性原理に基づく帯域制限パルス波形の考察」（信学論，昭45年5月）です．修士1年生の6月に投稿し，修士2年生の5月に掲載されました．符号間干渉零の帯域制限パルス波形で時間域の広がりが最小なものを求めたという内容です．4年生の1年間だけですが，千葉さんからは本当にいろいろなことを学びました．変分法，フーリェ解析，FFT，FORTRANなどの研究手法ばかりでなく，問題を発見し解決するという研究のし方から論文の書き方まで手取り足取り伝授してくれました．あとは，4年生の時に学んだこのアプローチをいろいろなテーマに適用することになります．このように人とのめぐり合いが人生に大きな影響を与えます．

「あのひと検索SPYSEE」をご存知でしょうか．私の名前で検索すると，私のプロフィールや，人間関係が顔写真付きで出てきます．これはグラフの木の描画です．木の中心が私で，関係が近い方ほど中心の近くに描かれます．これは，後で話すグラフ描画の一応用例です．

３．修士時代

　昭和43年の秋には斎藤伸自先生が教授に昇進されましたので，斎藤研の第1回生として学部を卒業しました．PCMの研究を続けたかったのですが，4年生のときに指導してくれた千葉さんは電々公社武蔵野通研に就職してしまうしで，どうしようか迷っておりました．卒業式の頃に斎藤先生に相談すると，日頃温厚な先生が「PCMの研究を続けたいならば，東大など他の大学に進学したらどうか」と厳しく明言されました．斎藤先生からこのような厳しいお言葉をいただいたのは後にも先にもこの時だけです．これが切っ掛けで大学院修士課程では，斎藤先生の指導の下で，トランスを用いない多端子対電気回路網合成の研究をする決心をしました．修士論文はハイブリッド行列を用いた回路合成理論を扱いました．これが私の研究に大きな影響を与えることになります．

　電気の卒業生は誰でも知っているように，2つの抵抗を直列接続すると，全体の抵抗は2つの抵抗の和になります．しかし，2端子対回路の直列接続では，トランスを挿入しない限り，全体のインピーダンス行列が2つの部分回路のインピーダンスの行列の和になるとは限りません．この和公式が成立する必要十分条件を回路の位相幾何学的（グラフ理論的）公式を用いて求めました．並列接続のアドミタンス行列の場合の条件も求めました．これが論文「変成器を含まない二端子対網の相互接続と位相幾何学的公式」です．

　この頃斎藤研には阿江忠助手（現広島大学名誉教授）がおられ，研究室の学生の指導法や取りまとめ方を学ぶことができました．その後，高浪五男先生（元山口・岩手大学教授，一関高専校長）が斎藤研の助手や助教授になられ，論文や本の厳密な読み方や理論的考え方をしっかり学ぶことができました．

４．博士時代

　最近のインターネットの検索技術はめざましいものがあります．名前を入力するだけで，書いた論文が他の方々によって何回引用されているか，たちどころに出力してくれます．Google scholarに「Nishizeki」を入力すると，私の論文が被引用回数が多い順に出力されます．一番引用が多いのは「秘密共有法」の論文です．この論文の内容は2月23日の情報科学研究科の最終講義で話しました．2番目以降は全て点と辺のグラフに関する論文です．今日はこれらのいくつかについて，話します．

　グラフ理論の勉強を本格的に始めたのは博士課程に進学してからです．最も熟読したのはFrank Hararyの著書“Graph Theory”で，本はぼろぼろになってしまいました．これを修士の学生や4年生と輪読しました．このゼミの参加者は

浅野孝夫（修士，現中央大学教授）

鹿島英一（修士，現九州大教授）

高見沢一彦（4年生，現ベンチャー社長）

滝内政昭（4年生，現富士通）

小松敏秀（4年生，現日立技師長）

伊藤行雄（4年生，現 NEC常務）

らであり，毎週1回午後1時から夕方6時か7時頃までやっており，証明の付いてない定理は数学科図書室から学術雑誌を借りて，元論文を読んで証明を理解し，ゼミで説明するという方式だったので，各自毎週少なくとも2，3編は論文を読まないといけないというハードなゼミでしたが，4年生もしっかりついてきてくれました．勉強ばかりでなく，学生と一緒に遊び，楽しんでいた時代です．ゼミの参加者は現在皆んなそれぞれ社会で大活躍をしています．

　点の配置をかえれば辺の交差がないように描けるグラフは平面グラフと呼ばれます．グラフ理論で一番有名な定理はKuratowskiの定理です．平面グラフであるための必要十分条件は，K₅やK_3,3を含まないことであるという定理です．したがって，平面グラフは，禁止グラフK₅とK_3,3で特徴付けられることになります．これを初めて読んだとき，何と簡潔で美しい定理なんだと感激しました．こういう美しい定理を是非とも証明したいと考え，修士論文の回路合成で扱った3端子回路に注目し，直列接続や並列接続を繰り返して得られるグラフを禁止グラフで特徴付けることを思い付きました．いかんせん数学的な熟練不足もあり，最終的な命題も思いつかないし，なかなか証明も完成しません．博士の1年生から2年生の間はほとんど朝から晩まで1日中証明を考え，やっと証明が完成しました．3端子直並列縦続グラフの必要十分条件は，ある2つのグラフを含まないことであるという定理です．これらの成果をまとめて，博士論文としたのは，昭和49年のことです．国内の「回路とシステム研究会」で発表すると，きわめて好評でした．海外に出掛ける旅費がなくて，この結果を国際会議で発表する機会はなかったが，IEEE Trans.やJ. Combinatorial Theoryに掲載された．当時グラフ理論的回路網学で第一人者でおられた伊理正夫先生（当時東大教授）に博士論文を送ると，半年後くらいに「おもしろい結果であるが，将来どう発展・展開するかはわからない」というような正直なコメントをいただいた．私自身も美しい定理だけど，この段階ではどう発展し応用されるのかあまり自信はなかった．

５．助手以降

　このようにして昭和49年に通信工学科回路網学講座の助手になりました．一応グラフ理論なら論文は書き続けることができそうだけど，このままグラフ理論の研究を続けていくだけの価値がグラフ理論にあるかどうかは大いに迷いました．高浪五男先生から「グラフ理論は東北大学に専門家が1人くらいいてよい重要な分野である」という強いアドバイスをもらい，背中を押された気持だった．この頃，C. Berge，F. Harary，W.T. Tutteらグラフ理論の大家達が続々と東北大を訪問してくれた．

　工学部にいるのだから，数学的なグラフ理論ばかりでなく，もっと研究の幅を拡げようと，アルゴリズムの勉強を開始しました．当時日本はおろか世界にもアルゴリズムの専門家はほとんどいなく，アルゴリズム理論は確立していませんでした．むしろ情報工学の主流はオートマトンや言語理論でした．最初に読んだアルゴリズムの専門書はDon Knuth著“Sorting and Searching”です．これは部厚い大作で，アセンブラもどきの言語で全てのアルゴリズムが記述されており，難解そのものですが，ほぼ最後まで読み切りました．後に1996年にKnuth先生が京都賞を受賞された時に，自ら希望して東北大学を訪問された折に，本にサインを書いてもらいました．Knuth先生を白布高湯温泉に案内し，一緒に温泉に入ったのもよい思い出です．

　Knuth先生の本は初学者が完読するには適当とはいえないでしょう．2番目に読んだアルゴリズムの本は，Aho, Hopcroft, Ullmanの名著“The Design and Analysis of Computer Algorithms”です．この本のおかげでアルゴリズムの本質がようやく理解できた．

　助手になって2年目の1976年に助教授に昇任し，翌年の1977年4月から1年間の間，村田海外留学奨学会の援助を受けて，カーネギー・メロン大学（CMU）数学科に客員数学者として滞在しました．お世話いただいたのはRobert J. Duffin先生です．任意の正実関数はトランスを用いないでL，C，Rだけを用いて合成できることを示したBott-Duffinの合成法が有名です．また2端子直並列グラフは禁止グラフK₄で特徴付けられることも証明しております．これらの論文を読んでいたことがDuffin先生の所に滞在した理由です．R. BottはDuffin先生の弟子で，不動点定理など幾何学の分野で著名な数学者です．CMUに行ってからわかったことですが，Duffin先生はE.L. PetersonやC. Zenerと一緒にGeometric Programmingも創始しております．このZenerはツェナーダイオードを発明していて，学部の電子工学の教科書にも出てくる方です．また，ノーベル経済学賞を受賞し，Nash均衡で有名なJohn Nashの修士課程での指導教授がDuffin先生でした．Nashがプリンストン大学の博士課程に入学する時のDuffin先生の推薦状には“The man is genius.”の一文しかなかったことが有名になったのは，映画“A Beautiful Mind”が上映されてからでしょう．このようにDuffin先生は物理学出身の応用数学者で，電気回路網のお仕事はほんの一部です．CMU滞在中にDuffin先生と共著論文を書く機会はなかったが，CMUの学生を実質的に指導して博士号を取得させることができた．現在彼はCMUのビジネススクールの研究科長代理を務めている．当時，1ドル360円の時代で，国際電話の通話料金は高くて，日本に電話をかけることも，かかってくることもなく，むろん現在のように電子メールもなかったので，日本に残してきた学生の指導や講義や雑務から一切遮断され，1年間毎日，朝から晩まで研究に没頭でき，天国のような1年間であった．計算幾何学を創始したMike Shamos，Programming Pearlsで有名なJohn Bently，Systolic Arrayを発明したH. T. Kung，日本IBM東京基礎研所長になられた鈴木則久氏，ロボティックスで著名な金出武雄氏はCMUの計算機科学科の助教授をしており，知り合うことができた．また，CMUでポスドクをされていた安西祐一郎氏（前慶応義塾長）や文部省在学研究員として滞在されていた木村泉氏（東京工業大学名誉教授）とも知り合うことができ，茨木俊秀先生（京都大学名誉教授）と初めて会ったのも先生がCMUを訪問された時でした．Shamosに計算幾何学をどうして始めたのかと聞くと，「もう既にグラフ理論やグラフアルゴリズムの分野は成熟していて，難しい問題しか残っていないから，グラフと似ているけど誰も注目していない初等幾何のアルゴリズムを計算幾何学と名付けて，その研究を開始した」とのことであった．またShamosの講義を聴講して，講義のし方を学ぶことができた．当時のShamosは学生と打打発止に対話しながら，機知に富んだ説明を講義でしており，東北大学で受けた講義とはまったく異なり，「目からうろこ」であった．帰国後はこのような対話型の授業をするように心掛けた．滞米中にやっとAllerton Conferenceなどいくつかの国際会議に出席でき，C. L. Liu先生やF. Preparata先生など計算機科学の分野で既に著名になっておられた方や，当時新進気鋭の若手であったAndy Yao，Nick Pippenger，Vasek Chvatal，David Avis，Sue Whitesidesらとも知り合えたのは，後で大きな財産となった．

　CMU滞在中は平面グラフのマッチングの論文を3，4編書いて，雑誌Discrete Math.等に発表した．この結果は大分後になってから何度も再発見され，ひどい時にはFOCS，ISAAC等の国際会議で発表されることもあった．マッチングの論文を書いて，グラフ理論の論文ならばいくらでも書ける自信ができた．しかし，工学部に籍を置いているという理由だけではないが，専門をグラフ理論からあえてアルゴリズムに変えることにした．当時の日本には情報工学科も計算機科学科も存在しなく，現在のようにアルゴリズムが計算機科学のコアになるなんてことは誰も予想もしていなかった．しかし，アルゴリズムと言っても，扱う問題はグラフ問題を中心に据えた．

　1978年に帰国すると，日本に残していった博士課程の学生が待っていた．「（2端子）直並列グラフ上のどんな組合せ問題も線形時間で解けるのではないか」というアイディアが浮かんだので，当時博士2年生の高見沢一彦君につめてもらうことにした．これをまとめてJACMに投稿したのは，彼がNECに就職した後であった．前刷や別刷の送付依頼の葉書や手紙が山のように来た．また，S. Hedetniemiが手紙で絶賛してきた．これがGoogle scholarで4番目に引用が多い論文であり，構造的グラフの線形時間アルゴリズム構成論の最初の論文です．

　上で述べたように博士論文の主な結果は3端子直並列グラフの定義と禁止グラフによる特徴付けでしたが，一般化したk端子直並列グラフの定義と簡単な性質も博士論文に含めておいた．これをきちんと発展させなかったことが後になって悔やまれた．というのも，k端子直並列グラフとほぼ同じ概念が，A. Proskurowskiによって「Partial k-tree」として，N. RobertsonとP. Seymourによって「木幅がk以下のグラフ」として定式化され，このようなグラフに対しては多くの組み合せ問題が効率よく解けることが示された．もっとも，周暁先生が大学院生として入学してから，部分k木に対するアルゴリズムを沢山発表し，点型の問題ばかりでなく辺型の問題も線形時間で解けることを示してくれて，構造的グラフの線形時間アルゴリズムを開始した者としての面目を施してくれます．

　グラフが与えられたとき，平面グラフかどうか判定し，平面グラフならば具体的に平面埋め込みを求めるアルゴリズムをPQ木というデータ構造を用いて与えた．これが2番目に引用回数が多い論文です．

　平面グラフに対しては，平面埋込み以外に，点彩色，辺彩色，多種フロー，ハミルトン閉路など多くの問題を線形時間で解くアルゴリズムを与えました．それらの多くは当時大学院生だった千葉則茂君（現岩手大学教授）との共同研究です．これらをまとめて，T. Nishizeki, N. Chiba著“Planar Graphs: Theory and Algorithms”としてNorth-Holland社から1988年に出版した．永らく絶版になっていたが，去年ペーパーバックとしてDover社から再版された．これが3番目に引用が多いものです．

　グラフをいろいろな基準で最適に描画するのがグラフ描画です．いろいろな描画法がありますが，全ての面が凸多角形になるようなのを凸描画と言います．従来グラフ描画は，W.T. TutteやC. Thomassenによって数学的理論として扱われてきました．グラフ描画をアルゴリズムの観点から研究を始めたのは我々（Nishizeki，N. Chiba，T. Yamanouchi，K. Onoguchi）が世界で初めてです．凸描画を求める線形時間アルゴリズムを与えた論文は引用が8番目に多く，凸描画法を利用してグラフをきれいに描くアルゴリズムを与えた論文は7番目に引用が多い．これら2つの論文はグラフ描画アルゴリズムの最初の論文として評価されている．上の2つの論文以降，グラフ描画の研究を中断していたが，中野眞一助手（現群馬大学教授），三浦一之助手（現福島大学准教授），バングラディシュからの留学生のM. Saidur Rahman君（現 BUET教授）と再開することになります．Saidurと一緒にまとめた著書が，T. Nishizeki, M. S. Rahman著“Planar Graph Drawing”（World Scientific社，2004年）です．

　残された時間が少ないので，共著の皆様には申し訳ありませんが，その他最近のアルゴリズムの成果は全て割愛いたします．

６．新しい分野の開拓

　輝かしい伝統ある回路網学講座を引き継ぎ，どう発展させたかと聞かれると忸怩なる思いがあるが，対象を電気回路網より，グラフに拡げ，そのアルゴリズム理論を発展させたという自負がない訳でもない．狭い分野かもしれないが，次のような新しい専門分野の創成と発展に貢献できた．

　　・構造的グラフの線形時間アルゴリズム構成論

　　・平面グラフアルゴリズム

　　・グラフ描画アルゴリズム

　　・秘密共有法

アルゴリズムの分野を日本で発展させるために，決して学会ゴロツキ（Academic Politician）ではないが，いくつかの戦略をアルゴリズムの「同志」である浅野孝夫氏（現中央大学教授）や浅野哲夫氏（現北陸先端大教授）らと練った．

最初は1986年に日米セミナー“Discrete Algorithms and Complexity”を京都で開催した．R. KarpやR. Rivestのようなチューリング賞受賞者など，きら星のような研究者が多数参加した．このセミナーの論文集はD.S. Johnson，T. Nishizeki，A. Nozaki，H.S. Wilf編著としてAcademic Pressから出版された．このセミナーは日本の学界に大きなインパクトを与えた．

当時，アルゴリズムを専門に扱う研究会がなかった．そこで情報処理学会にアルゴリズム研究会を1988年に創設し，日本での研究発表・討論の場を設けた．既にアルゴリズム研究会は100回以上開催されている．

日本やアジア地区にアルゴリズムに関する国際会議がなかったので，次にISAAC（Int. Symp. on Algorithms and Computation）を1990年に創設した．日本，アジア，太平洋地区を中心に毎年1回開催されている．その論文集はSpringer社からLecture Notes in Computer Scienceのシリーズとして出版されている．ISAACの創設以来，そのAdCom Chairを務めてきた．去年からその任を徳山豪先生に引き継いだので，ISAACを今後益々発展させてくれるものと期待している．

更に，1992年にグラフ描画を専門とする国際会議Graph DrawingをR. TamassiaやP. Eadesらが創設するのを手伝った．以後毎年1回開催されている．

アルゴリズム研究会，ISAAC，Graph Drawingなどで揉まれて若手研究者が成長・活躍していくのを目の当たりにすることは，それらの創設に関わった者として，きわめて嬉しいものがあります．

また，本を書いたり，訳本を出したのも戦略の一環だったかもしれない．

７．むすび

　東北大学電気系の伝統は，あまり時流に流されないで，一つのことをコツコツと長く継続して研究することでしょう．点と辺の世界に浸り，グラフ理論やグラフアルゴリズムの研究を40年も続けることができたのは，単にグラフが好きだっただけかもしれない．「好きこそ物の上手なれ」，「継続は力」をモットーにしてきた．また，5年や10年で消える成果でなく50年は生き延びる簡潔で美しい研究成果を出すよう努めた．更に新しい専門分野の開拓と発展に尽くしたつもりである．回路網学講座の伝統をうまく発展継承できたかどうか忸怩たる思いであるが，その講座を実質的に継承した「アルゴリズム論分野」は現教員の周暁准教授，伊藤健洋助教，内澤啓助教が今後うまく発展継承してくれるものと期待しています．

　私自身は電気回路網やVLSI配置配線等をグラフで表現し，そのアルゴリズムを扱ってきました．次の世代がアルゴリズム理論を更に発展させてくれるでしょうが，グラフアルゴリズムを扱ってくれるかどうかはわかりません．たとえグラフを扱うにしても，対象は電気回路やVLSIとは異なるものになるでしょう．MicrosoftのLibraに私の名前を入力すると，年毎にどのような専門分野で活躍したかわかります．例えば2000年はlinear time，bounded tree，tree widthのキーワードで表される分野（Community）に私が属したことがわかります．そのCommunityのCore MemberはH. Bodlaenderであり，Active MemberはD. Seeseらであり，私やA. ProskurowskiはOrdinary Memberであることがわかります．このようなデータマイニングでは，論文を点，引用を辺で表した巨大なグラフを作り，そのクリークなどを見つけたりしてます．このようなこともグラフアルゴリズムの1つの応用例であり，既に浅野泰仁助手（現京都大学特定准教授）といくつか論文を発表してます．

　ともかく，これまでの40数年の研究生活を通じて多くの人との出会いがありましたし，大学の先生になるという大学入学時の誓いも実現でき，自分なりに満足のいく研究生活であったと思います．これも御指導いただき，温かく見守っていただいた恩師の斎藤伸自先生をはじめとする諸先生，いろいろ教えていただいた千葉信行さんや三木哲也さんらの先輩，一緒に研究し，テニス・麻雀などで遊びも楽しんだ浅野孝夫さんら後輩や学生の皆さん，アルゴリズムやグラフ理論の同志やコミュニティの国内外の皆さん，ならびに東北大学電気系の伝統のおかげだと思っております．ここに心から御礼を申し上げます．

　これで私のつたない話を終わらせていただきます．御清聴どうもありがとうございました．