The main aim of this thesis is to introduce a polyhedral realization, called the tight span, of a finite asymmetric distance space and its applications. A finite asymmetric distance space is a pair of a finite set and an asymmetric distance on the set. A distance does not necessarily satisfy the triangle inequality. The term "asymmetric" is used to emphasize that the symmetry condition is not imposed; namely, a distance between two elements depends on the direction to measure the distance. Hence, a symmetric distance is an asymmetric distance. Isbell (1964), Dress (1984), and Chrobak and Larmore (1994) independently established that for any metric space there exists an essentially unique maximal tight extension, which is called the injective envelope by Isbell, the convex hull by Chrobak and Larmore, and the tight span by Dress, respectively. Recently, Hirai (2006) has extended the notion of tight spans to symmetric distance spaces. In this thesis, we introduce the tight spans for asymmetric distance spaces.

We explain the concept of realizations of finite distance spaces through the best known realization: the tree representation of a tree metric. A tree metric is representable by the lengths of the paths between vertices of a certain tree with nonnegative edge lengths. In this case, the tree is called a tree representation of the tree metric. The tree realization is endowed with some desirable properties, such as uniqueness, tightness, and universality. It is known that a tree metric has a unique, up to isomorphism, tree representation. The tightness of a tree representation means here that every point on the tree, which might be a point on an edge, is contained in the geodesic between a pair of certain leaves. The universality of a tree representation can be explained as follows.

Given a tree metric on a set, we take points on the tree representation of the tree metric and add the points to the given set. Then, we obtain a new tree metric on the enlarged set. Moreover, the tree representation of the new tree metric is essentially the same as that of the originally given tree metric, that is, all the tree metrics that have a certain tree as their tree representations are already embedded into the tree.

The tight span proposed in this thesis is also provided with those properties. Actually, Dress introduced the tight span as a generalization of the tree representation of a tree metric. The tight span for a tree metric is a tree as a union of line segments and thus the tight span is the tree representation. Tight spans allow us to geometrically investigate the structure of a distance space.

Contributors in the theory of tight spans have also established applications of the theory, such as phylogenetic tree construction problems and multiflow or multi-commodity flow problems. This thesis includes investigations on those problems.

Buneman's and Bandelt and Dress' split decompositions of metrics are two well-known tools for phylogenetic tree construction problems. Bandelt and Dress' split decomposition of a metric induces a decomposition of the tight span for the metric. Hirai (2006) derives Bandelt and Dress' split decomposition as a special case of the polyhedral split decomposition of polyhedral convex functions. Our result shows that Buneman's split decomposition can be also understood as a special case of the polyhedral split decomposition. This result provides a geometric and unified interpretation of the two split decompositions.

In the multiflow theory, clarifying the bounded fractionality of a polyhedron of solutions is a central issue. We give a complete characterization of the class of the weighted maximum multiflow problems whose dual polyhedra have bounded fractionality. A key ingredient is the tight spansfor asymmetric distance spaces. The theory of tight spans provides a unified duality framework to the weighted maximum multiflow problems,and gives a geometric interpretation of combinatorial dual solutions of several known min-max theorems, such as Ford and Fulkersons' max-flow min-cut theorem and Frank's directed free multiflow theorem, in the multiflow theory.

有限集合上の距離データから系統樹を構成する手続きは,基本的なデータ解析手法である.特に最近は,遺伝情報の解析に基づいて生物種の分化過程を研究する上で重要な手法として注目されている.系統樹で表されたモデルからは,木構造上での距離が自然に導入できる.しかし,観測された距離データは何らかの木構造で得られる距離に一致することは稀である.むしろ,できるだけデータに近いモデルを採用することになる.このようなプロセスにおいて,系統樹を推定するための手続きの妥当性を説明するためには,距離データに関する構造的な理解が必要となる.これは,新しいタイプの数学の研究対象として注目され,1960年代以降,研究が積み重ねられてきた.

Buneman は,今日 Buneman 指数と呼ばれる量を導入し,これに基づいて距離データから系統樹を構成する手法を提案した.一方,Bandelt, Dress は,これとは別に分離指数と呼ばれる量を導入して,三角不等式を満たす距離の分解原理を確立したが,これに対して,平井広志が最近幾何的解釈を与えている.平井の理論では,有限集合の要素対を実空間上に配置し,その上で関数値が距離データに一致するような凸関数への拡張を考える.このようにして得られた多面体的凸関数は,スプリット関数と呼ばれる簡単な関数の和と剰余部分とに分解できる.このときのスプリット関数の部分が,Bandelt, Dress が構成するネットワークを与えているというのが,平井の理論の概要であった.

一方,多品種流問題とは,ネットワーク上で複数の品種を輸送する際に,各枝を通る輸送量の総和が各枝の容量を超えない範囲で,できるだけ効率的な方法を求める問題である.各品種には供給点と需要点が与えられ,各品種を流す量の重み付き総和を最大化することを目的としている.各枝を通る輸送量に関して整数制約がない場合には,線形計画問題として定式化して解くことができる.しかし,整数制約が加わると,一般にNP困難となり,厳密な最適解を見出す多項式時間解法は存在し得ないだろうと信じられている.そのため,整数制約を緩和して得られる線形計画問題に整数最適解が存在するような特殊な問題群を抽出しようとする試みがなされてきた.

本論文は,有限集合上の距離データを元に系統樹を構成する手法に幾何的な解釈を与えている.さらに,非対称な距離の幾何的実現の基礎的な性質の究明を通して,有向グラフ上の多品種流問題の双対問題の整数性に関する新たな知見を導いている.

本論文は,10章からなる.第1章では,距離データに関する基本的な概念を導入した後,本論文の主要な成果を概説している.

第2章は,準備として,木構造から得られる距離を解説し,Bunemanの手法とBandelt, Dressの手法を解説している.

第3章は,平井による先行研究に従って,多面体的凸関数の分解原理を記述している.

第4章は,本論文のオリジナルな結果である Buneman 指数の幾何的解釈を述べている.有限集合の要素の順序対の実空間への異なる配置を考えることによって,平井の理論と類似の解釈が可能であることを示している.

第5章から第7章では,この結果と離散数学の諸概念との関係を考察している.第5章では,マトロイド理論を用いて,離散関数のスプリット分解の性質を解析している.第6章では,三角不等式を満たす距離の凸拡張に関して,離散凸解析の観点からの考察を述べている.一般に,M凸関数の和がM凸関数になるとは限らないのに対し,木構造距離のスプリット分解が,M凸関数をM凸関数の和に分解した形になっていることを指摘している.第7章では,タイトスパン,付値マトロイドとトロピカル幾何の関連を考察している.特に,付値マトロイドのタイトスパン,サーキット付値,トロピカル線形空間の三者が本質的に等価であることが示されている.

第8章では,非対称距離のタイトスパンの概念を導入し,基本的な性質を解明している.その応用として,第9章では,有向グラフ上の多品種流問題の双対問題の整数性を考察している.重みを表す非対称距離が定めるタイトスパンの次元が1になることが双対問題に整数最適解が存在するための必要十分条件であることを導出している.この結果を用いることで,Frank (1989) や 茨木, Karzanov, 永持 (1998)によって整数性が明らかとなっていた問題群に対して,双対問題の整数性が統一的に導かれる.

以上のように,本論文は,実際上有用なデータ解析手法の研究に端を発しながらも,その背後にある数学的構造を捉え,新たな解釈を与えることで理解を深めようという試みを実践している.その結果,単に既存の手法の解釈が得られるだけでなく,有向グラフ上の多品種流問題の整数性という異なる領域の未解決問題へのアプローチを提示するに至っており,数理情報学の分野の発展に大きく貢献するものである.

よって本論文は博士(情報理工学)の学位請求論文として合格と認められる.