組合せグラフによる消去法のグラフ表現
清 木 泰 弐*
Graphical Representation of E1imination by Combinatorial Graphs
by
Yasukazu SEIKI
(Department of Electrical Engineering)
A graphical approach to solving simu1taneous equations was tried in a previous paper by a signaJ f10w graphical representation of elimination. In this paper， elimination is characterized by "combinatorial graphs" ， which are defined as the graphs consisting of a set of points with
"coordinates" and a Set of branches with "coefficients". The "coordinates" of points are given by combinations of suffices corresponding to equations， and the coefficient" of a branch between two points is given by a definite operation concerning the "coordinates" of these points.
A signal f10w graph called "elimination graph" is obtained from a graphical representation of e1imination on the combinatorial graph associated with a given system of equations. The elimination graph connected to a graph of equations gives a soJution of the equations， and also gives a graphical method for computing the determinant related to the coefficients of the equations.
1. まえがき
シグナルフローグラフが一次形式の演算をもっグラ フであることに費目して連立方程式およびその解法を 共にグラフ表現し，問題と解法との結びつきをグラフ 的に把握することを前報告1)において試みた.連立方 程式の解法の中で最も基本的な逐次消去法は，与えら れた方程式の組合せとも関連性をもつので，これを系 統的に考察するため本稿において"組合せグラフ"な る新らしい概念を導入し，それに関していくつかの重 要な命題を導いた.さらに，このグラフにもとずく消 去法のグラフ表現(消去グラフ〉の求め方を示した.
組合せグラフにおいて，点の"座標"は方程式を表 わす添数の組合せとして与えられ，また点と点とを結 ぶ枝にはこれらの点の座標に対する特定の演算から得 られる"係数"が与えられている.このようにして構 成された組合せグラフにおいて，等しい係数をもっ 2
*電気工学科
つの径路 (p‑パス〉が存在することが証明される.
この Pーパスの概念は，消去グラフに関する基本的性 質を説明するための最も重要な役割りを果す.
組合せグラフから消去グラフを求めるとき，消去グ ラフにおける弧(枝に対応するもの〉の係数の絶対値はj
消去される未知数と組合せグラフ中の校の係数が与え られれば一義的に決定される.弧の係数の符号に関し ては，基本的には Pーパスにもとずく符号の決め方が 可能であるが cーパスとよばれる単純な部分グラフ の係数の符号のみを用いて pーパスによる方法より もはるかに簡単に弧の符号を決めることができること を示した.
最後に，消去グラフによる連立方程式の解の求め方 を示し，またこのような方法が行列式のグラフ的計算 法とも関連することを示した.
2. 組合せゲラフとその性質
連立方程式を逐次消去法により解く場合，第 1段階
では2つの方程式を1組とする消去が行われ，さらに 第2段階でも2つの方程式を1組とする消去が行われ るのがふつうである．しかし前報告において例示した ように，第2段階で3つの方程式を1組とし，さらに 第3段階で4つQ方程式を1組とする消去が可能であ る．一般に第r段階の消去において（r＋1）個の方程 式を1組とする消去法が存在することが予想されるが，
逐次消去法におけるこのような方程式の組合せに関す る一般的な考察を行なうため，本節において次のよう な璽組合せグラフ とよばれるグラフを導入し，それ に関する基本的な性質を求めてみる．
与えられたn個の1次独立な方程式の系｛e1， e2，
…en｝に対して，方程式の組合せをその計数集合N＝
｛1，2，…n｝における要素の組合せとして表わすことに
する．
組合せグラフにおける点を次のように定義する．
D1． P…（il i2…ir）と表わされる点Pは，聖座標
（ili2…ir）をもつr次の点とよばれる．ここにi1，
i2，…，i・はNの異なる要素である． r次の点の集合を P。と表わす．
また0次の点としてPoを定義する． Poは未知数 に対応する点として用いられるが，集合ではなく唯1 つの点を表わす．その座標を（φ）とする．またP1＝
｛（1），（2），…，（n）｝，Pn≡（12…n）である．
点と点を結ぶ枝は次のように定義される．
D2． 2つの点p， q問に枝が存在するのは，各回の 座標に関して次の条件が成立する場合およびその場合 に限る．
P≡（il i2…ir−1）∈Pr−1， q藁（jl j2…jr）∈Pr＆
｛ili2…i・一1｝⊂｛jlj2…」。｝（r：任意） （＊）
（＊）を単にp⊂qと表わす場合もある．
このときの枝を〔p，q〕と表わし， pからqへの方 向をもつとする．P・一1， P。問のすべての枝の集合を E。と表わす．またE1は， PoとP1の野点を結ぶ n本の枝の集合を表わす．
このような点および枝の定義により，一般にr次の 点は㈲個存在し，またその各々闘して（・一・）次 の鯛（，の一・個枝で結ばれている・
枝の係数を次のように定める．
D3． P≡（il i2…ir−1）， q≡（」1 j2…jr）＆P⊂qと するとき，q≡（ili2…i。一1a・），a・≠i1，i2，…，i・一1と 表わされることは明らかである．このとき枝〔p，q〕
の係数を〔a。〕と定める．この〔a・〕はまた次のよう な演算から得られる．
〔ar〕 ＝ 〔P㊦q〕 躍 〔（i1… ir−1）∈D（j1… jr）〕
ここに（Dは（A）㊥（AB）＝（B）， A≠Bなる演算 を表わす．一般にp，q間に枝が存在するときp㊦q は常に唯1つの要素により表わされるので，枝p係数 は㊦なる演算により一義的に定まる．
枝に関するこのような定義から次の命題が導かれる．
P1．同次の2点p1，p2∈P・に対してFig．1（a）の ような点p∈P・畦が存在するための必要十分条件は p1∩p2＝pなることである．ここに∩は2つの点の各 座標に関する積集合を求める演算である．
また，同次の2点q1， q2∈P・に対してFig．1（b）
のような点q∈P。＋1が存在するための必要十分条件 はqlUq2＝qなることである．ここにUは2つの点 の各座標に関する和集合を求める演算である．
P
（a）
R 宕4
名ユ
Fig．1
（b）
曾
（証明） 命題の前半を証明しよう．Fig．1（a）の ような点pがp1， p2に対して存在すると仮定すれば，
P≡（i1…ir1），〔P， P1〕≡〔ir〕，〔P， P2〕…≡〔ir＋1〕と
与えることによりp1，p2は次のように表わされる．
P1…（i1…ir−1ir）， P2ヨ（i1…ir＿1ir＋1）
∴P1∩P2＝｛ir・・ir−1ir｝∩｛i1… ir−1ir＋1｝＝｛i1… ir−1｝
したがってp1∩p2＝pが成立する．逆にこの関係か らp⊂p1＆p⊂p2が得られるので枝の定義により
〔P，P1〕，〔P，P2〕が存在し， Fig．1（a）のような点 pが存在することになる，
命題の後半を証明しよう． Fig．1（b）のような点 qがq1， q2に対して存在すると仮定すれば，
q≡（」1」2… jr−1jr jr÷1）， 〔q1，q〕≡〔jr〕，〔q2，q〕≡≡
〔j。＋1〕と与えることにより，q1， q2は次のように表 わされる．q1華（11…j・一1j・＋1），q2…三（11…j「一1j「）
∴q1 U q2＝｛j1… jr−1 jr＋1｝U｛j1… jr−1jr｝＝｛j1…jr−1
1。j。＋1｝したがってqlUq2＝qが成立する．逆にこ の関係が成立するとすれば，q1⊂q＆q2⊂qである から枝〔q1， q〕，〔q2，q〕が存在することになり，
Fig．1（b）のような点qが存在する． （Q．E．D）
組合せグラフを構成する部分グラフとして，次のよ うなグラフを定義する．
1）4． Gn＝＜P■一1，Pr， Er＞
r
また・G呈およびG恥は共通の点集合P・をもつ ので連結可能である．これをG呈［＞G㌫1と表わす．
以上の定義によ．り組合せグラフを次のように与える．
（n＝5に対する例をFig．10に示す．）
D5・ Gn≡≡G呈［＞G昌［〉…L＞G且 Gnをn次の組合せグラフとよぶ．
また G呈≡G塗［＞G§［〉…［＞G且＿1とする．
次にこの組合せグラフにおける径路（パス）の定義 を与える．
D6．同方向に連結した枝の系列を径路（パス）とよ ぶ．その係数を個々の枝の各係数の順序積として与え る．尚それらの枝の各係数は互いに異なるものとする．
点Pからqに到るパスに対して，Pをその始点， qを その終点とよぶ．
P2．組合せグラフ中の任意の2点p，q間にパスが存 在するための必要十分条件はp⊂qなることである．
またそのパスの係数は｛p④q｝の要素の順列により与 えられる．ただし，pを始点， qを終点とする．
〈証明） p，q間にパスが存在してその係数を
〔K〕…〔j1〕〔j2〕…〔lm〕とするとき，次のような点の 系列が存在する．P≡（i1…i・），P1≡（i1…irj1），P2≡
（i1…i， jl j2），…， pm…（i1…i・j1…jm）≡q． ただし j1，…，jmはi1，…，i・のいずれとも等しくないものと する．このとき，p㊦p1＝j1，p1㊦p2＝12，…pm−1
㊥Pm＝jmであるから，この点列は係数〔K〕のパス を形成することが確められる．したがって，p⊂p1⊂
p2⊂…⊂Pm＝q ．●． p⊂qとなる．このパスの係数が p㊥q＝｛j1，j2，…， jm｝の要素の順列で与えられるこ とは明らかである．逆にp⊂qなるときp㊦qの要素 を用いて上記と同様の方法でp⊂p1⊂p2⊂…⊂Pm・＝q なる並列を構成することができる．よってp，q間に パスが存在する． （QED）
P3． p…（i1…i・）， q≡（i1…i・j1…jm）とするとき，
p，q間にはm！個の異なるパスが存在する，
（証明） P2の証明において明らかなようにj1，」2，
…jmの配列を変えても， p， qの各座標は変らない．
一方」1，j21…，jmの配列が変わることにより，点 p1，…， Pm−1の各座標が変ることは明らかであり，ま た」1，j2，…， jmに対する異なる順列の数はm！であ るので，結局p，q間にm！個の異なるパスが存在 することになる． 、（QED）
p，q間に2つのパスが存在する場合を考えてみる，
Fig．2のようなグラフを並列閉径路（c一パス）とよ ぶ．これはFig．1の（a）（b）両雄を合併させたも のであるから明らかに次の関係が成立する．
P4． Fig．2の。一パスが存在するための必要十分条 件は，p1∩p2＝porp1Up2＝qなることである．
P5．〔P㊤P1〕＝〔P2㊥q〕＆〔P㊥P2〕＝〔P1㊦q〕
（証明） P≡（i1…ir−1），〔P， P1〕≡〔u〕，〔P，P2〕≡
〔v〕とすれば，p1≡（i1…i・一1u）， p2…（i1…i・一1v）と
なる．P4によりq・＝plUp2≡Li1…irluv）が
得られる．よって次式が成立する．
〔P2（Dq〕≡≡（i1一・ir−1v）（D（i1… ir−1uv）＝〔u〕≡
〔P㊦P1〕
〔P1㊦q〕≡（i1…ir−1の㊦（i1…ir−1uv）＝・〔v〕≡
〔P㊦p2〕 （QED）
C一パスのこのような性質は後で扱う消去グラフの 構成方法の基本となる．
P
ε償了
R
B
ω3
C・Paths Fig．2
〔？）〕
〔刎
次に係数の等しいパスを定義する．
1）7．同次の異なる2点をそれぞれ始点とする2つの パスを考える．それらの係数をそれぞれ〔a1〕〔a2〕…
〔a。〕および〔b1〕〔b2〕…〔b・〕とするとき，〔ai〕＝
〔bi〕， iニ1，…，rであるならば，このような2つのパ スを並列同値径路（P一パス）とよぶ．各パスの始点 の対をP一パスの始点とよぶ．終点に関しても同様．
また2つのパスの各々がr本の枝の連結により構成さ れているとき，これをr次のP一パスとよぶことにす
る．
P3．から次の命題が得られる．
P4．同じ始点，終点に対するm次のパスはm！組
存在する．
（証明） P3．における証明と同様である．ただし，
2つのパスの係数を同じ配列で構成する必要がある．
次の命題はP一パスにおける始点の座標と係数との 関係を示したものである。
P5． Gnにおける任意の始点p1，p2に対するP一パ スの係数が〔k1〕〔k2〕…〔km〕（順序不同）であると き，次の関係が成立する．
｛k1，k2，…，km｝⊂N一｛plUp2｝
（証明） 一般に始点p1≡（ili2…i．）に対するパス の係数を｛k1，k2，…，k皿｝とするとき， ki（i＝1，…，
m）はi1，…，i・のいずれとも等しくない．またki もすべて相異なる要素である．パスの最初の枝の係数 たとえばkbがi・に等しいと仮定したとき，パスに
おける2番目の点の座標が（ili2・ ・・i・k1）＝・（ili2…
i・i．）となり点の定義に反する． kiについても同様 のことがいえる．したがって，P一パスの係数は
｛plUp2｝以外の要素で与えられねばならない．
N一｛plUp2｝がそのような要素の集合である．
（QED）
G呈をP一パスの集合により特徴づける事ができる．
TL・1G購一を・1組の（・一2）次のP一パス喋 合により形成されるグラフである．
（証明） 磯中の（n−2）次のパスがP1において 始点をもち，Pn一ユにおいて終点をもつことは明らか である．（i），（j）を始点とするP一パスを考えるとき，
P5．により次のような係数をとることができる．〔K〕
＝〔1〕 〔2〕一一一〔i−1〕 〔i一ト1〕一一一〔j−1〕 〔j＋1〕 。一・ 〔n−1〕
〔n〕このような係数をもつP一パスを次のようにして 構成することができる．
（i）→（i1）→（i12）→… →（i12… j−1， j＋1）→一・（i12
…n）
（」）→（」1）一→・（j12）→。，一→（j12一一・j−1， j＋1）→。。・（j12
…n）
上記の2つの点列が係数〔K〕をもつP一パスを形成 していることは明らかである． 〔K〕の配列を変える ことにより（n−2）1組のP一パスが得られることは P4．から明らかである． P1から2つの点を選び出す
旧記㈲通りであるから瀦購セこおけるすべ
てのP一パスの数は（n2）・（・一2）！一÷・！となる・
また，このようにして得られるP一パス上の点はG呈 中のすべての点を表わす． （QED）
P一パスを含む次のようなパスは，C一パスと同様，
消去グラフの構成において重要な意味をもつ．
1）8．Fig．3に示すような， CP一パスを含む閉じた2 つのパスを並列同値閉径路（CP一パス）とよぶ．
R
皿コ fKユ
P 〔リコ
［K］
CP・paths・
Fig．3
各・朗
名
3・fω
P6．始点p1，p2，終点q1， q2をもつP一パスが Fig．3のようなCP一パスを形成するための必要十分 条件は，p1∩p2＝pもしくはqlUq2・＝qとなるこ
とである．
（証明） p1∩p2＝pであるときp≡（i1…i・）に対 して，p1ミ（i1…iru）， p2≡（i1…ir v）となる．ただ し〔u〕＝〔P㊤p1〕，〔y〕＝〔ゴ①P2〕である．
〔K〕＝〔k1〕〔k2〕…〔km〕をP一パスの係数とするとき，
q1≡（i1…ir uk1…km）， q2≡≡（i1…ir v k1…km）
となるから，qlUq2＝（i1…iruvk1…km）ど表わ される点はFig．3のqを与える．逆にql U q2＝q なる条件からpが得られることは，上記の証明と同様 にして行われる．またFig．3のようなCP一パスにお いて命題の条件が成立する・ことは，P1．より明らか である． （QED）
P7．始点p1，p2，終点q1， q2をもつP一パスによ り形成されるCP一パス（Fig．3）において，次の関係 が常に成立する．
〔P①P1〕＝〔q2㊦q〕＆〔P（DP2〕＝〔q1㊥q〕
（証明） P6．の証明において〔q1①q〕，〔q2㊥qユ を求めれば，それらは〔v〕，〔u〕となる．したがって，
P7．の関係が成立することが確められる． （QED）
P7．はP5．と類似の関係をもつことがわかる．
P4。により， p1∩p2＝・pなるときp1Up2により 与えられる唯1つの点pノが存在し，pからpノへ到
るC一パスが得られることがわかる．このように，
CP一パスに関する条件はCパスの条件も満たすことが わかる．
次の定理は，組合せグラフとCP一パスとの関係を示 したものである．
Th．2組合せグラフGn中のPoからPnに到るすべ てのパスの集合は，CP一パスの集合として表わされる．
（証明） Th．1によりG呈はP一パスの集合により 形成されるので，それらの始点もしくは終点に関して，
P6．の条件が満たされればGnにおいてCP一パスが 存在することになる．P1における任意の2点（i），（j）
に対して（i）∩（j）ニ（φ）…Po，またこの2点に対応し て一i義的にきまるPn−1の2点に関して，
（i12…i−1，i＋1，…j−1，」＋1，…，n）U（j12…i−1，i＋
1，…j−1，」十1，…，n）＝（12…n）≡Pn
が成立するので，PoおよびPnはCP一パスの点であ る．よって，定理が証明された （QED）』
組合せグラフの構成のしかたから明らかなように，
同じ次数の組合せグラフ同志の間には，その添数集合 の種類に関係なく，点と点および枝と枝との間に一対 一の対応関係があることがわかる．このような関係を
璽伺型 と定義する．組合せグラフの大きな特徴とし て，自分よりも低い次数の組合せグラフを部分グラフ
として含む，ということがあげられる．
P8．組合せグラフにおける任意の2点p∈P・，q∈P・
（r＜s）に対してp⊂qなる関係があるとき，点pか ら点qに到るすべてのパスにより形成される部分グラ フはGS一「と同型である．
（証明） p≡（i1…i。）とするときp⊂qなる条件か らq墜（i1…i・i。＋1…i・）と表わされる．パスの構成の しかたから明らかなように， p，q間のすべてのパス における点の座標は｛i。＋1，…，i・｝における任意の組 合せに｛i1…i。｝を付け加えたものとして表わされる．
したがって，（i1…ir）→φ， ir＋1→1，…is＝ir＋（s．r）→
（s−r）なる対応づけを行うことにより，これらの点 の座標は｛1，2，…，（s−r）｝における組合せにより表 わされる点に対応づけられる．またこのとき枝の係数 に関しても，（i1…ir ir＋1…ir＋m．1）㊦（i1＿irir＋1＿
ir＋m）＝〔ir＋m〕→（12…，m−1）①（12…m）＝〔m〕 で あるから，点と同じ対応関係が得られる．したがって，
上記のようにして形成されるグラフはGS雪と同型で ある． （QED）
3．組合せゲラフによる消去ゲラフの構成 一次独立な方程式の系｛e1，e2，…，e・｝に関して，
ei≡Σαij xj＝ci（i＝＝1，2，…．n） （＊）
j
｛α1k，α2k，…，αnk｝＝Kk（k＝1，2，…，n、）と定める．
（＊）をシグナルフローグラフで表わせばFig．4の ようになる．Fig．4をG（x1，x2，…，xn）≡Gn（x）
とする．またFig．4の太実線部分のグラフを
つ。肛
α1電
Qどユ星，
削ぐ捜7
：
●
o
●
q三Cl
つCL
ノ ノ
、 ）《
ゾ．（メ菰
色ヨC2
ノ
・ ， 謡疲 ・
o 、 o
、
の
α俄舵
θレ三CL
e侃≡C 駄
G呈（xi）とする． Fig・4のc1，c2，…，cn点にG登
［＞G§［〉…［＞G且なる構造をもつシグナルフローグラ フを連結させ，信号源｛x1，…，Xn｝から1点Pnに到 る信号の流れ（signal flow）を考察することにより，
逐次Xiを消去するようなグラフを構成することが本 節の主旨である．そのため，本節において組合せグラ フをシグナルフローグラフとして扱うが，枝に対応し て弧という言葉を用い，また点Pの値をv（p）と表わ すことにする．組合せグラフのPoは未知数に対応す る点として用いられ，Pnはすべての未知数の一次結 合を表わす点として用いられる．POを始端点， Pn を終端点とよぶことにする．
今，XiからPnに到るすべてのパスの係数の和を Aiとすれば， Pnの値は次のように表わされる；
v（Pn）＝AI x1十A2 x2十…十Aixi十…十Anxn したがって，XiからPnに到るすべてのパスの係数 の和が0になるとき，Ai＝0となり， v（Pn）におけ るXiの項が消えることになる．このような考えにも とずき，ある未知数を消去するグラフ（これを消去グ ラフとよぶ）を逐次構成してみよう．
始端点から終端点に到るすべてのパスの係数の和が 0であるような組合せグラフを， 0一グラフとよぶこ とにしよう．消去の第一椴階でたとえばXkを消去す る場合，XkからP2の減点に到るC一パスが0一グラ フとなるための条件を求めてみる．Fig．5にその。一 パスの1つを示す．このC一パスが0一グラフとなるた めには，αik・A十αjk・B識0でなければならない．
この式が恒等的に成立するようなA，Bの値は， A，B 共に0なる自明な場合は除いて，A＝土α」k，B＝干αik
（複号同順）として与えられる．A，Bの絶対値を考 えるとき，C一パスにおけるこのような係数間の関係 は，P5．に示された関係から得られることがわかる．
すなわち，Fig，5においては〔i〕がαikに対応し
〔j〕がαjkに対応している．したがって，逆にA，B の値をその枝の係数とKkにより上記のように定める とき，Xkを消去するグラフが構成されることになる．
コG俺
Grapllical represelltatioll
of
SimultalleOus equa・tiolls
Fig．4
dL色
つ。免 偶簡向
、（し），
、、 ！！
（5）
（メ脆 ！ 、！ 、 〆 、
Fig．5
A
B
（乙」）
このようにして得られる消去グラウをG易（Xk）と表
わす。
C一パスにおける2つのパスの係数の和が0になる という条件は，係数の符号を無視すれば，2つのパス の係数が等しいという条件と同値である．
M〔A〕十N〔B〕……ゴ0←→〔A〕≡N，〔B〕≡M （＊）
・係数の符号は一義的に定められないので，本節におい ては（＊）なる仮定のもとで0一グラフの構成を考え ることにする．尚符号のつけ方に関しては次節で詳し く論ずる．
一般に第r段階の消去においては，PoからP・中の 1点に到るパスの集合（P8．によりこれはr次の組合 せグラフとなる）が0一グラフとなるための条件を，
CP一パスに関して求めることになる． Th．2により組 合せグラブをCP一パスの集合と考えることができるの で，各CP一パスにおける2つのパスの係数の和を0と すれば，その組合せグラフは0一グラフとなる．とこ ろが，P7．によりその係数問の関係は， C一パスにお ける係数問の関係に帰着せられることがわかる．
Fig．6においてこれを示そう． P一パスの係数を
〔K〕とするとき，図の2つのパスの係数の和はαik
〔K〕〔j〕＋αjk〔K〕・〔i〕となる．〔i〕≡αik，〔」〕≡比jk とすれば，αik〔K〕αjk＋αjk〔K〕αik＝〔K〕（αik・αjk＋
αjk・αik）≡0（（＊）により）．したがってP一パスの 係数に関係なく，前記のひパスによる係数の決め方 と同じ方法でCP一パスに対する係数が決められること がわかる．一般に第r段階の消去グラフを得るために は，GPこおける枝の係数〔i〕に対して鐸（Xk）に おける弧の係数をαikと定めればよい．
コ℃免
P
@dz蔭
@ ／B
ﾆミ 、 ◎健
〔kコ
kKコ
・3・
f・3、
＼ζ刀 、 、
h蹄［乙］
CP−paths in
combinatorial graph G「
Fig．6
このようにして得られる消去グラフを結合させるこ とにより，次のような関係が得られる．
Th・3 Gn（x）［＞G珍（xi1）［＞G§（xi2）［〉…＞G丑
（xin−1）＝G牙（xi且）［＞G登（xi1）［＞G§（xi2）［〉…
［＞GR（xin−1）ここに（il i2…in）は（12…n）の置換
を表わす．
（証明） 消去グラフの性質により，点Xir（r≒n）か らP。＋1中の1点に到るすべてのパスの集合は0一丁 目フを形成する．Pnの値はP・＋1における点の一次 結合としても与えられるので，点Xi。から点Pnに到 るすべてのパスの係数の和は0となり，Pnにおいて
Xi・の項が存在しないことがわかる． i 1， i2，…，in−1 に対して上記のことがいえるので， Pnにおける値は
Xinの項だけを含むことになる． （QED）
4．消去ゲラフにおける弧の符号のつけ方
消去グラフにおける弧の係数はαtjもしくは一αij なる形で与えられるので，符号づけの問題をαij＞0 なる仮定のもとで負号のみに関する符号づけの問題と 考えても本質的には同じである．したがって，本節に おいてはαi」（i，j＝1，…，n）＞0とする．
本節で用いられる符号に関する定義および命題を以 下に示す．
Aの符号をsgn（A）と表わすことにする．
AB＞0←→sgn（A）＝sgn（B）
AB〈0←→sgn（A）＝一sgn（B）or −sgn（A）＝sgn（B）
sgn（AB＝sgn（A）・sgn（B）
C・≒0，sgn（AC）＝・sgn（BC）←→sgn（A）＝sgn（B）
前節においてM〔A〕＋N〔B〕≡…0←→〔A〕≡N，〔B〕
≡Mなる仮定のもとに弧の係数を扱ってきたが，実
際にMA＋NB＝0かつMAとNBの絶対値が等し
い場合，（MA）・（NB）＜0となることは明らかである．
そしてこのときA＝土N，B＝芋M（複号同順）とな る．したがって弧の係数の符号を単独に決めるのでは なく，パス全体の係数の符号にもとずいて決めること が1つの方法として考えられる．消去グラフの構成で 用いられたC一パスおよびCP一パスを再び本節でも取 り上げる．C一パスもしくはC一パスにおけるすべての 係数の積を表わす記号として◇を用い，またCP一パ スに対しては□なる記号を用いることにする．
Gn（x）［＞GnにおけるC一パスの符号を考えてみる．
2
たとえばFig．5においてαik・A＋αjk・B＝0である ときA＝・土α」k，B＝平αikとなるので，（αik・A）（αjk B）＝（αik・α」k）・（AB）〈0， またαik，αjk＞0である
からAB＜0が得られる．したがってXk以外の未知 数に対しても，ABにより形成されるC一・ミスに関し て◇＜0が成立する．AB以外の弧についても同様の ことがいえるので，結局G（x）［〉砺におけるすべて のC一パスに関して，それが0一グラフであるか否かに
係わりなく◇〈0となる．こうしてG登における弧 の符号は未知数と無関係に，◇〈0なる条件のみを 用いて定められることがわかる．
G§における弧の符号を定める場合はCP一パスの符 号を考えることになるが，CP一パスに関してもC一パ スと同様□＜0が成立することは明らかである．し たがって，G§の弧の符号は□〈0なる条件により 定められる．結局，原理的には□＜0なる条件のみ を用いて消去グラフの弧の符号を定めることができる が，高い次数の組合せグラフになるほどCP一パスの長 さが増し，その係数積の符号を求めることが困難とな る．ところがC一パスのみを用いて弧の符号を定める ことができる．以下にそれを示そう．
Fig．7は。一グラフであるとし，その。一パス，
CP一パスを次のように表わす．
B
一一A一〇
ノ
α β b♂
b ，／d ＼
P
＜o（i＝1，2，3）が得られる．したがってCP一パス［コi によるα，β，γの符号づけと，C一パス◇勲こよる α，β，γの符号づけとは互いに等価であることがわかる．
4次の組合せグラフに対しても同様のことがいえる．
Fig．8が。一グラフであるとする．またこのグラフの 醍の弧の符号は上記の方法により定められているも のとする．次のようなC一パス，CP一パスを考える．
（PoからPに到る組合せグラフにおけるC一パス，
CP一パスに対しては上記と同じ表現を用いることにす
る）
ご コラ A／ワA・ぐ、
（1）ノ／ン！B、、，）＼こ＼（ ・3・
一一7一一一一六一一一一 マー一う咲
α、働・9で論＼1）・（騰、
ζ爵綴ご簸穿＼戸
瓦 ＼
＼＼ 34ク
Fig．8
F
・、 D！
C、 ／ E 払一F一一
Fig．7
β づ
◇1螺aAbB，◇杢・＝aCcD，◇§＝bEcF ◇釜＝AαBβ，◇塁＝BαEγ，◇§臨DβFア
ロ1＝aCβ・bEγ，□2＝aAα・cFγ，□3＝・bBα・cDβ ◇｝（i＝1，2，3）＜0，□i＜0（i＝1，2，3）は明らかであ る．したがって次の関係が得られる．
◇毒・◇毒識。2・aCbE・DF＞0 □1 ＝・aCbE・βγ ＜0
（1） より sgn（aCbE）＝sgn（DF）
（2） より sgn（aCbE）・＝一sgn（βγ）
（3） （4） より sgn（DF）＝一sgn（βγ）
（5） より DF・βγ＝DβFγ＝◇碁く0
（1）
（2）
（3）
（4）
（5）
（6）
（6）式は，CP一パスロ1の代わりにC一パス◇§を 用いて，弧β，γの符号が定められることを表わす．
同様iにして，◇1・◇§＞0，□2＜0から◇舞く0 が得られ，◇1・◇♪0，□3＜0から◇1＜0 が得
られる．上記の証明から明らかなように，◇｝＜0な る仮定のもとに，逆に◇書く0（i＝1，2，3）から□i
ノ
ロ釜＝aCC β ・bEE γノ，□1＝DC βノ・FEノγノ
◇§＝D βノ・F1γノ
ロ1はCP一パスの1つである． Fig．8が。一グラ フであるから □呈く0は明らかである．前記の結果
（3）より，□子＝aCbE・C β E γ として
sgn （□ぞ）＝sgn（aCbE・C，βノE γノ）・＝・sgn（DF・
ノCノβ E！γノ）＝sgn（DC βノ・FEノγノ）＝sgn（□］）が得 ノられる．Fig．8において， PoからP に到る組合 ノせグラフは3次の組合せグラフであり，□1はこのグ ラフにおけるCP一パスの1つであることがわかる．上 ノ
記の結果より□1＜0が得られ，他のCP一パスに関 しても同様の結果が得られるので，◇〜（i＝1，2，3…）
＜0なる仮定のもとに，前記と同様の関係が得られる ノことは明らかであろう．すなわち，□1＜0より◇§
ノ ノ
＜0が得られる．したがって，□1によるβ・γ ノの符号づけと◇§によるβ・γ の符号づけとは互 いに等価となる．
一般に，G匙1の弧の符号が定まっているとき，
G呈における弧の符号は￠＿ユ［〉￠におけるC一パ スにより定められる．このように，消去グラフ中の弧 の符号はすべてG一パスの符号のみにより決定される．
G丑中の弧の符号づけに関して重要なことは，同じ 点と結びつく弧同志の符号は互いに他の弧の符号に依 存している，ということである．したがって，1つの 弧の符号が定まれば他の残りの弧の符号もこれに準じ て必然的に定まる．Fig．9においてこれを示そう．
Fig．9
各
P・中の1点qに対して，k1，k2，…，k．なる係数をも つr本の弧が結びついているとする．これらの弧に対 して，◇1，◇2，…◇・なるr個のC一パスが存在する ことは明らかであろう．（p1，p2，…p・はP．4の条件 をみたす．）今，◇1〈0なる条件のもとでsgn（k1）
を任意に定めるとき，sgn（k2）はこれにより必然的 に定まる．このk2と◇2＜0なる条件によりsgn
（k3）が定まる．以下同様にして，◇r 1＜0とsgn
（k，一1）によりsgn（k・）が定まる．一方，◇・＜0な る条件からもsgn（k1）により，＄gn（k・）が定まるこ とがわかる．この符号づけが，◇1，…◇・一1を用いる 符号づけと同じであることを以下に示す．
C一パス◇iに対して，◇i＝〈iki．1 ki。2なる部分 グラフ＜］iを定める．◇i＜0（i＝1，2，…，r）である から，sgn（◇1…◇r−1）＝一sgn（◇1…◇r−1◇r）．
◇1…◇r−1により順次k，の符号を定めることは，
次のように表わされる．
◇・…◇・一・一く・…〈・一・k・（k甕k§…k整、）k・
．●Dsgn（kl kr）sgn（＜」1…＜1 r−1）＝＝sgn（◇1…◇r−1）．
一方，◇1…◇。＝＜］1…〈。一1・＜］f（k釜…k2）からsgn
r
（◇1…◇。）＝sgn（＜コr）sgn（〈1…〈r−1）となり，さ らに◇iの積の符号に関する上記の関係から，
sgn（klk，）＝一sgn（＜］・）が得られる．これは◇。＜0 を表わし，また◇，によりkrの符号が定められる
ことを表わす．
このように，P・中の同じ点に結びつく弧同志は，
その中の任意の1つの符号が定まれば他の残りの符号 も必然的に定まる，という関係にある．P。中の異な る点に結びつく弧同志に関しては，各々に関係した C一パスが共通の弧をもたないので，互いに他の弧の 符号に関係なく独立した符号づけが行われる．
以上の諸結果から，符号の定められた消去グラフに 関して次の命題が得られる．
P9．消去グラフGn＞Gn＞…＞G丑における任意
ヨ
のC一パスおよびCP一パスに対して◇＜0および
□〈0が成立する．
最後に，G5に対する符号づけの一例をFig．10 に示す．破線で示された弧には負号がつくものとする．
この図において，上記の命題が成立することが確かめ られる． （図中の数字は点の座標を表わす．）
5．解法ゲラフと行列式との関係
本節においては，まず消去グラフによる連立方程式 の解の求め方を示し，さらにこのような方法が行列式 計算の一方法であることを示す．
前節の符号づけにより，消去グラフの構成に必要な 条件はすべて与えられたといえる．Th．3から得られ る次のようなグラフを，未知数Xinに対する解法グラ フとよぶことにする．
G呈（xin）［＞G量（xi1）［＞G§（xi2）〉…［＞G丑（xir 1）．
このグラフにおける始端点XinからPnに到るすべて のパスの係数の和をAinと表わす． また， P 1中の
（i）なる座標をもつ点からPnに到るすべてのパスの 係数の和を□｝と表わすことにする．
エユ
Th．4Xinは次式により求められる．
・垣一 ﾓ孝…□益
ここに，Cjは方程式ejの定数項である．
（証明） Xinを始端点とする組合せグラフに関して，
P。の値は次のように表わされる．
v（Pn）＝Ain・Xin （1）
一方，P1中の点（i）にはCiなる定数が与えられ ていることに着目し，P1の各点を始端点とする組合 せグラフにより， P・の値を次のように表わすことも できる．
v（Pn）・＝c1□｝十 c2□3十…十 CR□F （2）
ユエユ ユエユ ロ
（1） （2）により定理の式が得られる． （QED）
尚Ai。は次のように表わすこともできる．
Ain＝α1in□1＝α2in□3 十…十αn in□ρ
in ln ユ且、
解法グラフを用いたこのような連立方程式の解法は，
行列式の計算をグラフ的に行うことに相当すると考え
β
2，
！ ！ ！ 3 ノ
／！ ， ，！つ
！ ！ ！ ！ 4
！ ！ ，
14一ラ〆
！ 15
！ 1
匙 ／ ／、 、x
§、汽一一｝∠一…
3！ 、 ！ 、
＞ 24ノ ！ 、 ノ ノ ふ チ 4 、 ， 、
ζ5＼ ＼・・
総
、 、 ！ ！
＼＼ ◎ラ／！
＼、 ！ ＼＼45！！
23 ＼＼
・24 こ・
＼こ・、
！ ・ 、 ＼ ユヨ
∠ 、 ・＼＼＼、，、34
、 ＼
134 ＼ 、 ＼
＼ ＼ N∬235 ＼ 、
135 ＼ 、、
、 、 、、 12345 ＼ 、 ！ 245 、、
ロロ ！ 145 ＼ ！！
ノ ！ ！ 、 34・5 ！
！
／234 ！
ノ！
！ノ 2ヨ4与1 な 235 ，つ一 、
へ ノ ノ
！
24S ！！ positive arc
！
一一一一一一11egative arc 345
Combinatorial grapll G5 witll signed arcs
Fig．10 られるので，以下に，この解法グラフと行列式との関 係を考察してみる．次のような解法グラフにおけるパ スの係数を考えることにする．
G呈（x1）［＞G量（x2）［〉…［＞GR（Xn）
このグラフにおけるPoからPnに到る1つのパス の係数として〔i1〕〔i2〕…〔in〕を考えるとき，これに 対応して実際の係数αi11αi22…αinnが得られる．
この係数は符号づけ次第で正負いずれの符号もとりう るが（たとえばG畳における弧の符号の正負を逆にす ることもできる），正と仮定して議論を進めることに する．（il i2…in）は（12…n）の任意の置換を表わす ので，これによりPOからPnに到るすべてのパスの 係数を表わすことができる．置換は互換の組合せによ り得られるので，互換とそれにより得られるパスの係 数との関係を調べてみる．
αi11…αij」αij・1j．1，…αin nに対して（i， i＋1）
なる互換を施せば，αi11…αij＋1jαijj＋1，＿αinnな る係数をもつパスが得られる．このときこの2つのパ スはFig． nのようにC一パスを形成する．◇＜0な
る条件により，2つのパスのうちαij j，αij＋1」・1お よびαij＋1 j，αij」．1は互いに異符号であることがわ かる．したがって，互換により得られたパスの係数は 負．となる．また，（jk）なる互換により得られるパス に対しては，Fig．12のようにCP一パスが形成され るので，□〈0なる条件により上記と同様のことが いえる．一般に，互換の数が偶数であれば，その結果 得られるパスの係数の符号は正，奇数ならば負である
ことがわかる．
このようにして置換（il i2…in）から得られるすべ てのパスの係数の和はn！個の項からなり，明らかに 行列式det（αij）の値を表わしている．任意の解法グ ラフに対して上記と同様のことがいえるので，解法グ ラフと行列式det（αij）との間には次の関係が成立す
る．
Ljコ
r樹
〔旬
［∂2
「■咀@鯛陰 ロ噛
εtコ
εL十り C・Paths Fig．11
［計1コ
｝
〔τコ
綱■■ ■陶 一
CP・paths Fig．12
Th．5未知i数Xkに対する任意の解法グラフおよび 行列式D＝det（α｝j）に関して次式が成立する．
＝ k＝1ジ2，…，nIA・1 1DI
したがって，解法グラフから行列式Dの真の値を 求めるためには，符号に対する考慮が必要である．そ の真の符号を求めるためには次のようにすればよい．
行列〔αij〕の対角線の要素の積α11α22…α・nの符 号を求める．次に，これを係数としてもつ解法グラフ 中のパス（このようなパスは明らかに唯1つである）
に関して符号を求め．その符号がα11α22…α皿の符 号と同じであれば，その解法グラフから得られる値は 行列式Dの値と同じであるといえる．もし両者の符 号が異なる場合は，解法グラフから得られた値に負号 を付すか，あるいは解法グラフの最終段における各々 の弧の符号をそれぞれ正負逆にすればよい．
6．あとがき
問題およびその解法を共にグラフ表現し，それら2
つのグラフの結合により解を求めるという試みから出 発した本研究も，逐次消去法のグラフ表現に関しては ほとんど完成されたと言えよう．本稿で述べられてい る連立方程式のグラフ的解法は，内容的には行列式を 用いたCramerの公式に帰着するが，逐次消去法と 行列式との関係および行列式のグラフ計算法が得られ たという点で意義をもつと思われる．尚，解法グラフ により行列式に関する種々の基本的性質が説明される が，それらの議論は割愛した．
参考文献
1）清木：「連立方程式の解法とそのグラフ表現」
長崎大学工学部研究報告第4号 昭和48年12月
