数学特別演習（第7回）

今日の授業では、greedy algorithm（欲張りアルゴリズム）とマトロイドの関係から始まりました。

マトロイドは、主に、数学の中でも組み合わせ論と呼ばれる分野において、線形代数の「1次独立」の概念をより抽象化した、「独立」の概念や構造のことをいいます。もちろん、この授業ではマトロイドの詳細には立ち入りませんが、今勉強しているグラフの木構造が、マトロイドの一例であること、ある与えられた構造において、greedy algorithm が常に最適な解を見つけるならば、その構造はマトロイドどなること、などの事実に触れました。

マトロイドは、1930年代に、幾何学者のホイットニー (H. Whitney) によって発見され、世界に広まった概念ですが、実は、同時期に、日本でも独立に発見されたことがわかってきました。東京文理科大学（筑波大学の前身の一つ）の中澤武雄氏が、東京文理科大学の紀要 (Science Reports of the Tokyo Bunrika Daigaku, Section A) に掲載した論文がそれです。この辺の概要は、筑波大学数学系のwebサイトにおいて、斎藤明先生による解説が掲載されています。

中澤武雄の数学的業績 (斎藤 明)
http://www.math.tsukuba.ac.jp/kouseki/knak/nakasawa.html

また、西村泰一先生と黒田享先生により、中澤氏の略歴と業績、マトロイドに関する論文（ドイツ語）およびその英訳が書籍にまとめられ、出版されています。

A Lost Mathematician, Takeo Nakasawa: The Forgotten Father of Matroid Theory
Nishimura, Hirokazu; Kuroda, Susumu (Eds.)
Birkhäuser, Basel, 2009, XII, 234 p. 14 illus., Hardcover
ISBN: 978-3-7643-8572-9

なお、この本のプレプリント（全文）は、つくばリポジトリ（筑波大学の機関リポジトリ）にて入手可能です。 http://hdl.handle.net/2241/104009

授業の後半では「ケーニヒスベルクの橋渡り問題」が取り上げられました。今後は、グラフの一筆書きの問題に話題を変えて話が進みそうです。