平成29年度 秋期 午前 問6

✓ これが正解イ0 1 0 0 1 1 0 1 1 0 0 1 0 0 0 0 1 0 0 0 1 0 0 0 0

解説

五つのノードの木は、エッジがちょうど四本です。

設問は、五つのノードをもつグラフの隣接行列のうち、木になるものを選ばせています。木とは、閉路がなく全体がひとつながりになっているグラフのことで、これはノードの数から一を引いた本数のエッジで全体がつながっている状態と同じです。ノードが五つですから、エッジは四本でなければなりません。向きのないグラフの隣接行列は対角線をはさんで対称になるので、行列に並ぶ一の個数はエッジの本数の二倍、つまり八個になります。そこで、図を描き起こす前にまず一の個数を数えると、八個のものはひとつだけに絞られます。あとはそこからエッジを書き出し、五つのノードすべてに行き着けること、対角成分がすべて零であることを確かめれば決まります。

ほかの選択肢はなぜ違うのか

• ア0 1 0 0 1 1 0 1 0 0 …：並んでいる一の個数は十で、エッジは五本になります。書き出すと五つの点が順に手をつないで輪をひとつ作っており、閉じた道があるので木とは呼べません。
• ウ0 1 0 1 0 1 0 1 0 0 …：こちらも一の個数は十で、エッジは五本です。四つの点が四角い閉じた道を作り、残るひとつがそこにぶら下がる形になっているため、条件から外れます。
• エ0 1 1 0 0 1 0 1 0 0 …：一の個数は十二で、エッジは六本と四つの中でいちばん多くなっています。三つの点から成る閉じた道が二か所に含まれており、本数の時点で木にはなり得ません。