「グラフ」は、点(節点)と、点同士を結ぶ線(枝)で、ものの関係を表したものです。例えば、駅を節点、駅同士をつなぐ線路を枝と見れば、路線図もグラフの一種です。
グラフを図ではなく数で表す方法の一つが「隣接行列」です。節点がn個のとき、n行n列の表を作り、節点ViとVjが枝で結ばれていれば第i行第j列に1、結ばれていなければ0を書きます。問題の定義では、枝に向きがないので、第i行第j列と第j行第i列は必ず同じ値になります。
行列を読むときは、行ごとに「その節点がどの節点と結ばれているか」を調べます。
枝は、V1-V2、V1-V3、V2-V4、V3-V4の4本で、4つの節点がちょうど四角形の形につながるグラフです。また、各行の1の個数は、その節点につながる枝の本数を表します。この行列ではすべての行が2個なので、どの節点にも枝が2本ずつ出ています。選択肢の図でも、枝の本数を数えると見分けやすくなります。
解説
「グラフ」は、点(節点)と、点同士を結ぶ線(枝)で、ものの関係を表したものです。例えば、駅を節点、駅同士をつなぐ線路を枝と見れば、路線図もグラフの一種です。
グラフを図ではなく数で表す方法の一つが「隣接行列」です。節点がn個のとき、n行n列の表を作り、節点ViとVjが枝で結ばれていれば第i行第j列に1、結ばれていなければ0を書きます。問題の定義では、枝に向きがないので、第i行第j列と第j行第i列は必ず同じ値になります。
行列を読むときは、行ごとに「その節点がどの節点と結ばれているか」を調べます。
枝は、V1-V2、V1-V3、V2-V4、V3-V4の4本で、4つの節点がちょうど四角形の形につながるグラフです。また、各行の1の個数は、その節点につながる枝の本数を表します。この行列ではすべての行が2個なので、どの節点にも枝が2本ずつ出ています。選択肢の図でも、枝の本数を数えると見分けやすくなります。