図 1 Ｋ端子グラフ分割
図 2 カットセット分割
図 3 ダイアモンド図形
図 4 左メッシュグラフ
図 5 ハミルトン直並列グラフ
図 6 左メッシュグラフに１点を追加する
図 7 枝の確定と除去
図 8 Ｋ端子ＩＯ
図 9 カットセットＩＯ
図 10 ３端子分割の左右部分グラフ
図 11 過疎グラフ
図 12 直並列矛盾枝
図 13 原始文字グラフ
図 14 検定グラフと短絡グラフ
図 15 枝の脱落によるデッドロック
図 16 パスの分裂によるデッドロック
図 17 分裂から分裂は派生しない
図 18 脱落点の復活確定
図 19 新たな矛盾点の復活確定
図 20 分裂点の復活確定
図 21 脱落枝の復活確定と救済枝の再生
図 22 復活・除去・再生
図 23 復活経路と脱落点の移動
図 24 復活径路
図 25 半点グラフ
図 26 交差する極性の等しい復活径路（分裂パス）
図 27 交差する極性の等しい復活径路
図 28 交差する極性の異なる復活径路
図 29 例題１
図 30 Ｎ木による解法
図 31 例題２
図 32 ２部グラフによる解法
図 33 マーキングによる解法
図 34 ハミルトン検定概念図
表 目次
表 1 デッドロックマップ上の枝
表 2 デッドロックマップ上の点
参考文献
[1] Liu, C.L. : Elements of Discrete Mathematics, 2nd
Edition, McGraw-Hill, Inc., 1985,
成嶋弘，秋山仁訳，離散数学入門，マグロウヒル，1986
[2] 高橋磐郎，藤重悟：離散数学, 岩波講座 情報科学 17, 岩波書店,
1981
[3] 梶谷洋司：回路のためのグラフ理論，昭晃堂，1979
[4] 石畑清: アルゴリズムとデータ構造，岩波講座
ソフトウェア科学 3, 岩波書店, 1989
[5] 井田哲雄: 計算モデルの基礎理論，岩波講座 ソフトウェア科学
12, 岩波書店, 1991
[6] Lewis, H.R., Papadimitriou, C.H. : The efficiency of algorithms,
野崎昭弘訳，アルゴリズムの有効性，コンピュータ数学
別冊サイエンス，日経サイエンス社，1983
[7] Graham, R.L. : The Combinatorial Mathematics of Scheduling,
伊里正夫，伊里由美訳，スケジューリングの組合せ数学，コンピュータ数学
別冊サイエンス，日経サイエンス社，1983
[8] 今井浩：線形計画法と計算の複雑さ，コンピュータ
ソフトウェア vol.5 No.1, 日本ソフトウェア科学会，岩波書店，1988
[9] 前原昭二：数学基礎論入門，基礎数学シリーズ 26, 朝倉書店，1977
[10] 上坂吉則，船田哲男，木俣昇：情報科学の基礎，培風館，1979
[11] 村上温夫，榎本彦衛，森本光生：シンポジウム
数学と計算機，数学セミナー vol.25 no.01|290，日本評論社，1986
[12] Aho, A.V., J.E. Uilman：アルゴリズムの設計と解析Ⅱ
野崎昭弘，野下浩平共訳，，サイエンス社，サイエンスライブラリ
情報 電算機＝３６
1977
[13] Harary, F.: Graph Theory, ADDISON-WESLEY SERIES IN MATHEMATICS, ADDISON-WESLEY
PUBLISHING COMPANY, 1969
[14] Buckley, F., Harary, F.: DISTANCE IN GRAPHS, ADDISON-WESLEY PUBLISHING COMPANY, 1990
[15] Schmidt G., Strlein T.: Relations and Graphs, Discrete Mathematics for Computer
Scientists, Springer-Verlag, 1993
[16] Palmer E.M.: GRAPHICAL EVOLUTION, An Introduction to the Theory of Random Graphs,
Wiley-Interscience Series in Discrete Mathematics, JOHN WILEY & SONS, 1985
96/3/3
