藤重 悟:「グラフ・ネットワーク・組合せ論」

(工系数学講座18巻,共立出版) (2002年4月出版)

 

1997年より,大阪大学の基礎工学部システム科学科(電子システム学コース)で「グラフ・ネットワーク」という講義を担当し,その講義の原稿である本書の第1章と第2章の原案が大体出来上がるのは早かったのですが,第3章の構想をまとめるのに時間がかかってしまいました.そのため,本書の執筆を承諾して脱稿まで多くの年数を要し,関係の方々には大変ご迷惑をおかけしました.

さて,このホームページは,本書で書き足りなかった部分を補足したり,出版後に見つかった誤りなどを訂正するために設けました.必要に応じて更新を繰り返していくことになります.読者の皆さんのご意見なども私宛,お寄せください.


カタカナ表記  (2002年4月)


本書の執筆に当って,外国の人の名前を,たとえば,Lovasz (ロヴァース)のように「読み・発音」を括弧で示すという形を取りたかったのですが,出版社の方針に従って,名前をカタカナで示し,ロヴァース (Lovasz)の形を取ることになりました.(なお,正しくは,Lovaszのaにはアクセント記号が付くのですが,ここでは落としていますので,ご了解ください.)私の元々の方針は,カタカナの名前は,本来の呼名の日本語による近似的な発音であり,正しい表記はオリジナルな文字によるもの,という考えによります.また,良く分からない読みや自信のないものは,括弧内の読みを表記しないことによって,それを示すことができます.逆に,今回,自信のないものも読みを書かなければならなくなりました.

今回の読みの確定で苦労したのは,155ページの Hirsch予想のハーシュ(Hirsch)です.この人は,ドイツ語読みでは「ヒルシュ」となりますが, first nameが Warrenであり,恐らくアメリカ人ではないかと推測し,「ハーシュ」としました.

その他の読みについて,

上述のロヴァース (Lovasz)を,ロヴァーシュと発音するのをしばしば耳にしますが,これは間違いです.また,アクセント記号がaに付きますが,これは音を長く延ばすだけで,「ロ」を強く発音します.同様に,39ページの ヤルニーク (Jarnik)(アクセント記号がiに付く)も「ヤ」が強く発音されます.ただし, Lovaszはハンガリ,Jarnikはチェコの人です.その他に,Brouwerは,ブラウワー,ブラウアーなども見かけますが,岩波の数学辞典に従って,ブラウエルとしました.

読みについては,音を延ばす「ー」を入れるかどうかで,議論が分かれるところですが,本書の執筆において一つの方針を貫くようにはなっておりません.自分自身悩むところなのですが,たとえば,劣モジュラ関数(submodular function)として,劣モジュラー関数のように「ー」を入れておりませんが,オイラー(Euler),ファルカーソン(Fulkerson)などには「ー」を入れて音を延ばしています.このタイプの読みは,「ー」を入れない方が元の発音に近いと思いますが,日本語での発音のしやすさに起因する慣用的な記法にしました.(ファルカーソンは「ファ」が強く発音されますが,これを初めて読む人は「カー」にアクセントをおく可能性が大きくなるのも,気になるところですが.)「劣モジュラ」の方は,私が submodular function の研究に入り込んだ1975年の時点で,これに対応する日本語の用語が見つからず,既に用語として確立されていた,モジュラ束(modular lattice)などのモジュラと劣加法的(subadditive)より,「劣モジュラ」を使い始めて30年近くになり,過去の自分の用法を守って,劣モジュラ関数としています.

それから,2部グラフのマッチングに関連して出て来る K\"{o}nig (\"{o} は LaTexで o の上に2つドットを付けた o Umlaut)はハンガリの人なので,ドイツ語読みのケーニヒではなく,ケーニグとなっています.自身の著作物で K\"{o}nig となっているので,これでもよいはずですが,ハンガリの発音(\"{o}を延ばす)に対応して,K\H{o}nig (\H{o}は o に2重のアクセント記号が付いたもの)と書かれたものもしばしば見かけます(ハンガリの人の名前としてはこちらが正しいようです).なお,\"{o} の音は「エ」とはほど遠いように思いますが,ゲーテ(Goethe)が受け入れられているのでよいのでしょう.カタカナ表記の無理が感じられます.


k 連結性について  (2002年6月)


22ページの最後の方に,k 連結性の定義が出て来ます.この定義は W. T. Tutte(タット)先生の記述をそのまま採用した(ただし,連結なグラフを考える前提条件が落ちていますので補ってください)のですが,私の同僚の牧野助教授から以下のような指摘がありました.

このままの定義では,5点完全グラフが4連結でないことになる.すなわち,5点完全グラフに対して,3点完全グラフ(3角形グラフ)と残りの枝からなる部分グラフとを考えると,22ページの l(エル)=3に対する (i), (ii)の条件を満たす.

実は,点連結度に関係するこの部分を書く際に,定義をどうするかについて悩んだ挙げ句,組合せ最適化の分野においては神様のような存在であるTutte 先生の一般的な連結度の定義を使うことにしたものです.私がTutte先生の一般的な連結度の定義をそのまま用いたのがまずかったようです.定義なので,論理的な破綻ではないのですが,他書等で「点連結」と呼ばれているものと違っているので注意してください.条件(i)の $|B_i|\ge l (i=1,2)$ を削除して、 $W_1\setminus W_2, W_2\setminus W_1 \neq \emptyset$ を加えれば、通常の点連結度に合わせることができます。

与えられたグラフG=(V,E)と正整数k < |V|に対して,通常のk点連結性は,「すべての正整数 i < kに対して,i個の点を取り除いても残ったグラフが連結であるとき,グラフGはk点連結である」と定義されているようです.

なお,本書の2連結性,3連結性の議論は,Tutte先生の定義での連結性に正しく対応しています.

因に,Tutte先生は,2002年の5月2日に,85才の誕生日(5月14日)を迎える直前に亡くなられました.


パーフェクトグラフについて (2010年5月)


2003年に数理解析研究所へ転任して、長らくコメントの追加を怠ってきましたが、その間、2刷り、3刷り、と刷りを更新する機会に、誤植の訂正などの対応をしてきています。

ここでは、本書の刊行後の特筆すべき、パーフェクトグラフに関する成果について、述べます。

本書の34ページに述べたように、グラフ G は、その任意な誘導部分グラフのクリーク数と彩色数が等しいとき、パーフェクトグラフと呼ばれます。グラフ G がパーフェクトグラフであることと、G の補グラフがパーフェクトグラフであることとが同値であることが C. Berge(ベルジュ)によって予想され、1972年の論文で L. Lov\'{a}sz(ロヴァース)が証明して決着が付きました。こちらの予想を「弱予想」呼んで、これに対して、Bergeによる「強パーフェクトグラフ予想」(1961年)と呼ばれるものがあります。

グラフ G は、Gおよびその補グラフの任意な誘導部分グラフが5以上の奇数長のサイクルを含まないとき、Bergeグラフと呼ばれます。Bergeグラフであることとパーフェクトグラフであることとが同値である、というのが「強予想」です。

2006年に刊行の論文
M. Chudnovsky, N. Robertson, P. Seymour, and R. Thomas: "The strong perfect graph theorem," Annals of Mathematics, Vol. 164 (2006), pp. 51--229.
によって「強予想」が肯定的に解決され、2009年のFulkerson Prizeが授賞されています。なお、肯定的に証明されたとの最初のアナウンスは、2002年の5月ですが、それはBergeが亡くなる1ヶ月前のことでした。

一方、この「強予想」の証明とは独立に、与えられたグラフがBergeグラフであるか否かを判定する多項式時間アルゴリズムが、
M. Chudnovsky, G. Cornuejols, X. Liu, P. Seymour, K. Vuskovic: "Recognizing Berge graphs," Combinatorica, Vol. 25(2005), pp. 143--186.
によって、示されています。これによって、パーフェクトグラフであるか否かの判定が多項式時間(O((|V|+|E|)^9))で実行できることになっています。
 


Hirsch(ハーシュ)予想について (2010年12月)


今年の5月にニュースが流れて、一種の衝撃を与えましたが、本書の155ページにも述べましたHirsch予想の反例が、Francisco Santos によって示されました。
これは、43次元で86個のファセットをもつ多面体で、Hirsch予想の不等式を1だけ破るものです。これによって、Hirsch予想が否定され、多面体グラフの直径が(ファセットの数)-(次元)で一般的には抑えられないことが判明しましたが、多面体グラフの直径を抑える同種の不等式の存在を否定したものではありません。依然として、もっとゆるい形である、ファセットの数と次元の多項式で多面体グラフの直径を抑えることができるかどうかも、未解決問題として残されたままです。
 


最大フロー・最小カット定理の証明について (2010年12月)


本書の57ページに、最大フロー・最小カット定理の証明を与えていますが、そこでは、脚注にも触れましたように、最大フローの存在を仮定しています。このことは、大変気になる箇所で、読者の中にも気にして問題であると思われる方もおられるものと思います。

そこで、注意しておきたいのは、まず、整数値容量関数の場合は、その証明中に示された増加道に沿うフロー増加を有限回繰り返すことによって、最大フローが求められ、本定理が証明され、そして、それによって、定理2. 6の整数性の定理の証明が完結します。さらに、本書の59ページから述べられていますが、ディニツのアルゴリズム等によって、容量関数の整数性の仮定無しで、多項式時間で最大フローが見出されることが、 (補題2. 7の弱双対性のみに基づいて)証明されています。したがって、そこまで進めば、本書において閉じた形で(最大フローの存在を仮定しないで)「最大フロー・最小カット定理」の証明が完結する、というように考えることもできます。
 


E-mail : fujishig@kurims.kyoto-u.ac.jp