連立方程式の解法とそのグラフ表現
清 木 泰 弌＊、
A Solution of Simultaneous Equations and Its Graphical Representation．
by
Yasukazu SEIKI
（Electrical Engineering）
Problem Solving is an important theme of Information and Systems． As an example of Problem Solving， a graphical representation of simultaneous equations with solutions is discussed in this paper．
Simultaneous equations are represented by signal flow graph． Elimination is a general method to solve the problems which contain some unknown variables．
Asolution graph as the system which deals with information about unknowll variables can be constructed by the graphical representation of elimination．
1．まえがき
最近，Problem Solvingというテーマが情報とシ ステムに関する研究の分野において重要な意味をもっ てきた．澗題を解く ということ自体は当然重要な 課題であるが，解が得られるまでの過程の表現形式を 確立することは，Problem Solvingの一般的な研究 にとってさらに重要なことであると思われる．問題を 解くことの第一段階として，与えられた問題をどのよ うな形式で表現するかということを考えねばならない．
問題の表現形式が与えられて，はじめて解法の形式も 与えられる．多くの表現形式の中でも，幾何学的表現 は解法に対する手がかりを直観的に求めやすいという 点でしばしば用いられる．本稿でも問題の表現形式と してグラフ理論を用いる．そして問題表現の例として，
シグナルフローグラフによる連立方程式の表現を考え てみる。連立方程式のように未知数を舎む問題に対す る解法としては，未知数の数を減らしていく消去法が 最も一般的である．問題のグラフ表現と共にその解法 もグラフ表現することにより，問題と解法との結びつ きが同一の空間で表わされる．
問題を解くということを情報とシステムの立場から
＊電気工学教室
考察することが本稿の主旨であるが，その一例として の連立方程式の解法のグラフ表現は，未知数という情 報の流れに関するシステム構成を試みたものである．
解法のグラフ表現から，問題に対する解は単に表現形 式の面からのみでなく，演繹を通しての情報とシステ ムの立場から考察することにより，その真の構造が明 らかにされることがわかる．
2．連立方程式のグラフ表現および解法ゲラフ シグナルフローグラブ（以下単にグラフという）は 次のような表現形式をもつ．
Fig．1はy＝axを表わし， Fig．2は y＝a1×1十 a2×2十 ∴十an Xn
α ぼ一→一・一ウ弩
Fig．1
謁 α巳 τ2 α2
0覗
γ飢
Fig．2
宮
を表わす．またFig．3は次のように変形できる．
z ＝ax， y＝bz→y ＝：（ab）x
したがってこれはFig．1のように表わされる．
α． b 実一・→一噂一〉一・宮
Fig．3
くコl
Fig．4
Fig．4のような場合
y1＝ax， y2＝＝ax →y1＝y2＝＝ax
であるから，これもFig．1と同形になる． ・ 以上のグラフの性質を用いて，次のような連立方程 式をグラフ表現してみよう．（Fig．5）
alx1＋a2x2＝c1 （1）
｛
blx1＋b2x2＝c2 （2）
α1
二Σ民
Fig．5
一般に連立方程式を手計算で解く場合，未知数を順次 消去していく方法が用いられる．1つの未知数を消去 するためには2つの関係式が必要である．上記の例に おいてx1だけを含む関係式を求めるための操作を示
してみよう．
（1）×b2＋（2）×（一a2）
これをグラフ表現したものがFig．6である．ここ
τ8
ω− σr
ム2
τ2
02 ＼
＼ 一αa b。C』 ＼＼
b2 ＿＿→一＿一）≧、Rぐ＝と2）
三子α。）
Rα1）
金2
Fig．6
に，G2は2元連立方程式のグラフ表現を表わし， R
（X1）はX1だけを含む関係式であることを表わす．
このグラフにおけるX1およびX2に関する情報の流 れを考えてみよう．シグナルフローグラフの性質によ り，R（x1）はx1とx2との1次結合により表わさ れるが，R（x1）はx1のみを含む関係式であるので x2の項の係数の和は0になるはずである． x2の項の 係数はx2からR（x1）に到る径路により与えられる，
Fig．6から，径路x2 cl R（x1）はa2b2なる係数 を・もちかつ径路x2 c2 R（x1）はb2（一a2）なる係数 をもつことがわかる．2つの径路の係数の和をとれば，
a2b2＋b2（一a2）＝0
となり，x2の項が消去されていることが確かめられ・
る．6呈（X2）をX2に対する消去グラフという．
Fig．6をG2［＞6呈（x2）と表わす．ここに〉は消 去法によるグラフの結合を表わす．問題のグラフと消 去グラフとの結合が解を与えるとき．これを解法グラ フという．Fig．6においてR（x1）の値を求めると き，x2の項は存在しないので太線の部分のみを考え ればよい． G2の太線部分をG言（x1）と表わせば，
解法グラフGl（x1）＞61（x2）からx1が得られる．
実際径路xlclR（x1）および径路xlc2R（x1）から R（x1）＝（alb2−a2b1）x1 （3）
が得られる．一方，c1および￠2からR（⊇【1）を求め れば次のようになる．
R（x1）＝clb2−c2a2 （4）
（3）および（4）からR（x1）を消去してx1が得 られる．x2についても同様の方法を適用すればよい．
x1を求めるための解法グラフをG2（x1）と表わす．
Fig．6を完成させればG2（x1）UG2（x2）が得られ ちる．一般に，解法グラフを同一の構成により同時に表 わすことができるのは2つの未知数に対してのみであ
る．
次に3元連立方程式を考えてみよう。
alx1十a2x2十a3x3＝d1 （5）
｛
blx1十b2x2十b3x3＝d2 （6）
clx1十。2x2十。3x3＝d3 （7）
まずX3を消去するためのグラフG皇（X3）を構成 する．3元連立方程式の場合，x3を消去して得られ
る式は全部で3つ存在する．これらをR｝（x1， x2），
R養（x1， x2）， R§（x1，x2）と表わす． Fig．7に示
dI コごf k一一一一一一乃
＼、 ノ も ノ
ノ く
／て、 ＼d2 臨くご一⊃r一∴
、． ＼ 、 、 、 、
二と3
＼＼dヨ
、、
Rl
Rと
研3 Fig．7
駅 R5
すように，x3からRlへ到る径路を考えると， x3 dlRlおよびx3d2R｝の2つが存在する．，これらの 係数の和が0となるためにはdlRl＝b3かつd2
Rl・＝一a3とすればよいことがわかる． R杢に対し てはx3dlR当および， x3d3R支，またR§に対して
はx3 d2 Rlおよびx3 d3 Rlを考えれば63（x3）の すべての係数が決まる．
次にRRx1，x2）からx2を消去するためのグラフ 1
6塁（X2）を構成する． X2を消去すればX1のみを含 む関係式が得られる．今これをR呈（x1）とする． x2 を消去する方法はFig．8の如く3・つ存在する。その
呑亨＼
、、
葱 1
・R警 ：x，）
別
・、一∴
虚警3
Fig．8
1つをy1としx2からy1へ到る径路を考える． y1 にはx2の項は含まれないので，そのすべての径路の 係数の和は0になる．いまd2 R｝およびd3 R杢， dl R｝，およびd3 Rき， d1 Rl，およびd2 Rきのように，
係数が同一もしくは符号のみが異なる2つの径路を考 えるとき，これらの各々を通る径路の係数の和は0に なる．したがって，例えばFig．9の太線部分のよう
2「2 わ
2
Rl
砂！
一b3 Fig．9
α」
b8 C8
．dI
な径路を考えるとき，R｝y1諜。2およびR養y1＝
＝b2と与えられることは明らかである． y2， y3につ いても同様のことを行なったとき，結局これらが同一 の点R呈（x1）となることがわかる． Fig．10はこう
して得られたx1に対する解法グラフである．
一b3 d3
Fig．10 G8（x1）
このグラフから実際にx1を求めてみよう．まず，
x1からRl（x1）へ到るすべての径路の係数の和D
を求める．
D＝c2（alb3−a3b1）一b2（alc3−a3c1）十a2（blc3 −b3 c1）
この値が未知数の係数行列式であることは容易に確か められる．次にd1， d2， d3を用いてR呈（x1）を求 める．Rl＝dlb3−dla3， Rl＝dlc3−d3a3， Rき＝d2 c3−d3b3
R釜（x・）＝・2Rl−b2 R易＋・2 R乙 （8）
R呈（x1）＝Dx1 （9）
（8）（9）よりRi（x1）を消去してx1が求められ
る．
最後の例として，4元連立方程式のx1に対する解 法グラフをFig．11に示す．「
一わ4 一α2
C4
一〇4
d4
一（刀4
d4 −b4
−C4 d4．
α3 −b，
」C3−d3「
3d3 （究明
一。ヲ
b
Fig．11 G言（x1）
3．解法ゲラフの基本的性質
本節において，連立方程式肺よびその解浩のグラフ 表現に関する形式化を行ない，いくつかの基本的な命 題を導く．
（定義1）Gn：n元連立方程式のグラフ表現．
（定義2）6叢（Xi）：k番目に構成された消去グラフ
（未知数Xiを消去することを表わす）．
（定義3）Rl・6裂に現われる点（ilま砿におけ るi番目の点であることを表わす）
Rド（Xj）はXjのみに関する関係式であることを表 1
わす．一般に，Rト（Xj）は未知数の集合Xjのみに 1
関する関係式で，X／Xj（／は集合の差を表わし， X は全未知数を表わす）の要素は含まないことを表わす．
R寧（Xj）は解法グラフの構成においては，未知数の 1
存在に関する情報を提示するのみである．
（定義4）G8（Xi）：Gn中のXiのみに関する部分 グラフ． これを用いてGnを表わせば次のようにな る． Gn＝G8（x1）UG3（x2）U……UG3（xn）
（定義5）Gn（Xi）：n元連立方程式のXiに対する解 法グラフ．
解法グラフはGnに消去グラフを結合させて得られ るが，グラフ結合を次のように表わす．
G8（Xi）［＞6呈（Xj1）
［〉 は消去法によるG8と耀のグラフ結合を表わす．
一般にG8［〉（雪［〉（輩［〉……［＞6匙1と表わされる・
未知数を消去する順序は任意であるから，Xiに対す る解法グラフは次のように与えられる．
〔命題1〕 Gn（xi）＝G3（xi）［＞6呈（xj 1）［〉……［＞
6且一1（Xjn一・）
ここに． （」1，j2，…， jn−1）．は（1，2，…， i−1，
i＋1，…，n）の任意の置換である．
すでに消去されたXiに対する消去グラフを構成す ることは無意味であるから次のことがいえる．
〔命題2〕（G8＞6呈〉……〉鰻（x・）〉……＞
6呈）＞6呈＋1（Xi）
ここに［〉は［〉の否定を表わす．
（定義5） 〈G＞：グラフGの径路の係数集合．
（定義6）〈G8（・・）〉一Kl
ただしK9の要素はすべて相異なるものとする．ま 1
たKl≒Kl（i≒j）とする・
次に消去グラフにおける演算系を定義する．Fig．
て多
α乙
免。
ムう
Fig．12
拒2
R
12におけるXiからRに到る2つの径路の係数の和が 0になるとき，次のようにk1， k2を定める．
ak・＋軌k野・⇔ oli＝墜叢：ll㎡
これを単にk1＝bi， k2＝aiと表わすことにする．
ai， bi∈K9とすれば， k1， k2∈K9となることが
1 1
わかる．上式の両辺にAlを掛けると次式を得る．
aiAjk1十biAjk2＝0
これを形式的にグラフ表現すればFig．13の如くな る．消去グラフにこのような径路が存在することは，
次のようにして証明される．
α
ん
C一
d多
AJ
κ 、 蓄L
Fig．13
R
、
、
、 し
諺・
勘、
香㍗αの 否財）
8r
y
A。
Aa
、
、
、
努
Fig．14 A3
耀
θ。
Fig．14においてG呈（xi）を考える． A1， A2，A3 に対してA1＝A2・＝A3＝kiとなることはグラフから 明らかである．また，このような径路に対して《輩 ノ（xj）を考えるとき， kjAIB1＋k｝A2B1＝0より（kj
ノ ノ
B、＋k｝B・）k・一・⇔B・一k・またk・A・B，＋
kl A3 B2＝0よりB2＝kjを得る．したがって上記
の例ではA2 B1＝A3 B2＝ki kjなる係数をもつ径路 が存在することが示される．またこのような径路にお いては図の破線部分のように，異なる2点から出発し た径路が他の径路と2点で一致するということは起こ らない．実際，このようなことが起こると仮定すれば，
k1＝＝bi＝・di， k2＝ai＝・ciとなり， aiキci， bi≒diと 矛盾する．
この性質から次の命題が導かれる．
〔命題3〕 GnにおいてR甕2の数はn個である．
〔命題4〕〈艦一1（・・）〉一Kl さらに次の命題が成立する．
〔命題5〕 解法グラフGn（Xi）において， Xiから Rn−1（Xj）に到るすべての径路の係数の和はi＝1，2
…，nに対して一定である．ただしiキjとする．
（証明） 2つの解法グラフGn（Xi）およびGn（Xj）
（i≒j）を同時に考える．この2つの解法グラフは次の ような消去グラフを共通の部分グラフとしてもつ．
6呈（xj・）＞6馨（…）〉……＞6言．2（・・n−2）
ここセこ， （j1， j2，……， jn＿2） をコ＝（1，2，……，i−1，
i＋1，……，j−1， j＋1，……， n）の任意の置換であ る．この消去グラフにおける径路の係数集合をSとす る．定義6および命題4により，Gn一（Xi）の径路の 係数は
＜G号（・・）＞S〈G藍．1（x・）〉一KI SKl
として与えられる．同様にしてGn（Xj）に対してKl SKIが得られる．命題3からG8（Xi）の径路の数と GR．1（X」）の径路の数はいずれもnであることがわか る・したがってKI SKIとKI SKIは同等となり・
各々の係数の総和は等しくなる． （QED）
4．解法ゲラフの情報およびシステム論的考察 連立方程式のグラフ表現から解法グラフが得られる
まで基本的な考えとなっていたのは，未知数に関する 情報の流れとそれを処理する消去グラフであった．解 法グラフの出発点はG号（Xi）であるが，これ自体は Gnの部分グラフではあっても関係式としての表現を
もたない意味のないものである．しかし，情報の流れ を考慮しながら各消去グラフを構成する場合には，重
要な役割りを果している．具体的な数式の展開による 解の求め方は，各段階において等式として意味のある 形での表現が要求される．一方，グラフによる解法で
は未知数そのものすら扱わず，それに関係した情報の 処理のみを考えればよい．その上，解法グラフを構成 するに当って，各消去グラフ中の点は情報の内容を示 すための媒体として用いられるだけで，具体的な計算 には一度も用いられていない．径路およびその係数の みが計算の対象となっている．しかしその反面，ある 未知数に関する情報をすべて取り出すため，操作が多
くなるという欠点もある．
解法グラフを形成するためにはGnにおける各未知 数を情報源と考えればよいが，解法グラフから実際に 解を求める場合，Gnにおける未知数Xiと定数ei の2つの情報源に対するネットワークを考えることに なる．この2つの情報の流れが同一の終端点に到ると き，未知数が既知数により表わされ解が得られる．解 法グラフGn（Xi）は， Xi以外の未知数に関する情報 はすべて消去してしまうシステムであるともいえる．
本稿で得られた結果は，本質的には消去という操作 をグラフ表現することに帰着される．このように，
problem solving のテーマを扱う場合には，解を求 めるための基本的なアルゴリズムにもとずく表現形式 を与えることが重要である．
5．あとがき
問題を解くということを情報とシステムの立場から 考察する例として，連立方程式の解法をグラフ表現す ることを試みた．問題を解くためのア〜レゴリズム（こ こでは消去法）そのものをグラフ表現することにより，
そして未知数という情報の流れを考察することにより，
解法グラフというシステムが得られた．
本稿で用いたシグナルフローグラフは変数の1次関 係を表わすには有効な方法であるが，その他の形式の 方程式や問題を考察する場合には，別の演算形式をも
ったグラフを考える必要があると思われる．
