マトロイドと劣モジュラ関数

摘要

私が「マトロイド」という言葉に最初に出会ったのは，1974年の6月であったと思うが，当時東京大学工学部（計数工学科）の教授になられて間もなくの伊理正夫先生に，助手採用の面接でお目にかかり，「マトロイドを知っていますか？」と聞かれたときである．私はそのときマトロイドについて全く知らなかったのであるが，当時，伊理先生は冨澤信明氏（当時，東工大助手）と共同で電気回路網への応用を目指したマトロイド理論を展開されており，控え目な話し方ではあったが，最前線での研究の熱気がひしひしと伝わってきた．早速先生の一連の御研究のすべての論文を頂いて，勉強した．このときが，マトロイドをはじめとする離散システムの研究の私の出発点であり，伊理先生の御指導を得て，マトロイドや劣モジュラ関数に関連する研究にのめり込んで30年近くになる．伊理先生と．いう素晴らしい先生に巡り合えたのを大変幸運に思っている．さて，本文では，マトロイドや劣モジュラ関数についての基本的事項と関連する組合せ最適化モデルを概説し，更に，最近の成果と今後の期待される展開について述べたい．多少なりとも，学生諸君のこれからの研究の進め方の参考になれば幸いである．