論文内容の要旨
The problem of finding the maximum flow, one of the important optimization problems, was first formulated by T. Harris and F. Ross and solved by L. Ford and D. Fulkerson, who created the first algorithm, known as the Ford-Fulkerson algorithm, to be repeatedly improved further. In this work, the classes of undirected networks with and without loops with fixed degrees of nodes and the arc weights of which do not exceed a given parameter are investigated. A method for investigating these classes is developed. The method is based on the following results. For an arbitrary partition of the set of nodes into two subsets, the variable quantities are the sums of arc weights on each subset and the sum of the weights of the arcs which are incident to the two subsets. For these variables, attainable upper and lower bounds are obtained both in the case of constraining the arc weights by a common constant and by the degrees of the nodes and in the case of constraining the arc weights only by the degrees of the nodes.
This method is applicable in the theory of network flows if the networks are considered as directed graphs with a symmetrical matrix of the capacities of arcs assuming, that the weights of arcs are the capacities, the partition of the set of nodes into two subsets specifies the network cut, and the third variable is the cut capacity. If in one of the subsets are the source 氏 名（本籍） セリン パヴェル（ロシア）
専攻分野の名称 博士（工学）
学 位 記 番 号 工博甲第２１８号 学位授与の日付 平成26年12月24日 学位授与の要件 学位規則第４条第１項該当
研 究 科 ・ 専 攻 工学資源学研究科（電気電子情報システム工学）
学 位 論 文 題 名 Optimization Problems on Classes of Networks with Fixed Degrees of Nodes and Flows
(固定された次数のノードとフロー量を有するネットワークの最 適化問題に関する研究)
論 文 審 査 委 員 （主査）教授 小原 仁
（副査）教授 五十嵐 隆治 （副査）教授 今野 和彦 （副査）教授 山村 明弘
Akita University
nodes, and in the other – the sink-nodes are chosen, then attainable upper and lower bounds for the third variable are those ones for the maximum flow value (the maximum flow value is equal to the minimum value of the cut capacity). For instance, for the two-pole network from the class under consideration, we have obtained the minimum value of the maximum flow and a bound for the maximum value of the maximum flow. An analogous problem is also solved in the case where any node is either a source or a sink. This method also allows constructing networks with a maximum density of arc weights on a chosen subset of nodes. The results can also be applied to communications networks. The partition of the network nodes into two subsets specifies two sub-networks, generated by the nodes of the subsets, as well as a bipartite network. Therefore, the class of the bipartite networks with the fixed degrees of nodes is investigated separately. Thus, the results of this work can be applied to transport type problems as well as in the nonlinear, multi-index and infinite-dimensional generalizations.
This work is based on the ideas contained in the works on the realizability of the sets of non-negative integers by the degrees of vertices into a graph and on the realizability of non-negative numbers into a weighted graph, the weights of edges of which do not exceed a given parameter. For an arbitrary non-negative integer vector the question arises: whether it is realized in the network or not. For the case of graphs without loops the answer was obtained by S. L. Hakimi. Later the analytical criterion of realizability was obtained by P. Erdos and T. Gallai. However, these results are not applicable in the case the weighted networks, networks with loops, bipartite networks, as well as in the case of constraint of the arc capacities by a constant. These cases were investigated by A. A. Mironov and will be considered in the work. Constructions are based on the characteristic functions and equations:
the non-negativity of the characteristic function is the criterion of the existence of a network with a specified degrees of nodes and a specified constraint for the arc weights (capacities);
the characteristic equations in case of special partitions of the set of the network nodes of the considered class by exact equalities for the sums of the arc weights on the subsets of nodes are determining the general properties of the networks of the class.
In transport problems, the classes of networks under consideration are called the truncated network and transport polyhedrons. One of the optimization problems in the transport-type models, where the classical minimization functionals are replaced by minimax is finding a minimax and constructing a hereditarily minimax network (matrix), any sub-network of which is a minimax network of the polyhedron to which the network belongs. For the truncated network and transport polyhedrons the analytical formulas of calculating the minimax values are obtained. The minimax values determine the necessary and sufficient conditions under which the truncated polyhedrons are not empty sets. Moreover, an algorithm for constructing a hereditarily-minimax networks in network polyhedrons is obtained. In
Akita University
practice, for example in communication networks, increasing the load on the node deteriorates its characteristics, which leads to the need of consideration of the class of networks with loops.
For this class of networks the problem under consideration also has been solved.
論文審査結果の要旨
本研究は，指定された次数（degree）とリンク容量（weight）を有するノードの集合が 与えられた場合，その構成条件を満たす２部グラフ（Bipartite Network）の存在の可否を 特性関数（Characteristic Function）によって判定するとともに，最大（または最小）フ ローを有するグラフを生成するアルゴリズムを対象としている。本研究の応用としては，
通信網の設計や化学物質の構造解析など多方面にわたる。本研究の起源は1960年に発表さ れたグラフ理論における著名な「Erdos-Gallaiの定理」である。その後，Hakimi，Mironov，
Tsurkov などによって，グラフに課される構成条件の拡張が試みられてきた。しかし，従
来の研究は理論が主体であり，具体的なグラフの生成手順に関する工学的な研究は非常に 少ない。本研究は，比較的構造が単純な２部グラフを対象として，最大（または最小）フ ローを有するグラフを生成するアルゴリズムに重点を置いている。本論文は以下の５章か ら構成される。
第１章は序論であり，本研究の背景，先行研究の概要，本研究の目的，本論文の構成，
本論文で用いられる用語や記号の定義などについて述べている。
第２章はノード間を接続するリンク容量が，ある一定の値に制限された２部グラフを対 象に，本論文で新たに導入したいくつかのパラメータ（後述）を用いた特性関数の表記方 法を提案する。これらのパラメータはグラフ構造に直結した意味を有している。従来の特 性関数はグラフの存在の有無のみを判定するだけであったが，提案する特性関数ではグラ フの最大（または最小）フローを求めることが可能になった。また，ノード間のフローを 表す行列式を元に，その最大（または最小）フローを実現するグラフを導出するための基 本的な考え方を提示した。すなわち，特性関数に対応して，フローの上限に該当するリン クを含む集合については，それらの「補フロー」（フローの上限と実際のフローの差分）を 新たなパラメータとして導入する。また，特性関数条件を満たす「限界フロー」を新たな パラメータとして導入する。これらの２つのパラメータを用いることによって，特性関数 はフローに対応した項の和によって記述することができ，最大（または最小）フローが評 価できることを明らかにした。
第３章と第４章では，第２章の結果を基に具体的なグラフの生成アルゴリズムを提案す る。第３章はループを持たないグラフを対象とし，第４章はループを有するグラフを対象 としている。それぞれの特性関数の表記は異なるが，基本的な考え方は２章で述べた通り
Akita University
である。具体的なグラフの設計は以下の手順で実行される。最初に，指定されたフロー行 列から特性関数を満たす限界フローを求め，初期フロー行列Ｘを作成する。次に，Ｘを初 期値として，与えられたフローから限界フローを引いた更新フロー行列Ｘ’とＸ”を計算する。
これらの計算を限界フローが最小値になるまで再帰的に繰り返す。提案したアルゴリズム を，いくつかの例に適用した結果，最大フローおよび最小フローがタイトな条件で求めら れることを明らかにした。また，その計算量についても評価した。
第５章は本論文の結論であり，本論文で得られた知見をまとめた。
以上，本論文は，与えられたノード数やリンク容量の制約の下で，最大（または最小）
フローを有する２部グラフの生成に関して，独自のコンセプトに基づいて効率的なアルゴ リズムを提案しており，グラフ理論の工学的な応用例として高く評価できる。よって，本 論文は博士（工学）の学位論文として十分に価値があるものと認められる。
