平成28年度 技術士第一次試験問題【専門科目】
【16】情報工学部門
V−6
グラフ理論に関する次の記述のうち、最も適切なものはどれか。
 @ 完全2部グラフは、すべての頂点同士が辺で繋がっている。
 A 距離を重みとする重み付きグラフでは、ある頂点から別の頂点への移動に
   要する重みは、どの順路でも常に同じである。
 B 頂点から出た辺が同じ頂点に戻るループのみである場合、その頂点は
   孤立点である。
 C 3つの頂点及び3つの辺で構成される単純閉路グラフならば、いずれの
   頂点でも次数は2である。
 D 無向完全グラフでは、頂点の数をnとしたとき、辺の数は2nとなる。



【正解】 C
@
2部グラフは、頂点の集合を2つの集合(部分集合)に分割し、各集合内の
 頂点同士には辺がないグラフのことで、
 完全2部グラフは、2部グラフのうち、全ての頂点がつながっているグラフのこと。
 例えば○3つ、 ●3つがあったとすると、
 ○同士には辺がなく、●同士にも辺がないが、
 全ての○と全てのの●がつながっているグラフのこと。
A3辺の長さが、3cm、4cm、5cmの三角形もグラフであるが、
 3cm,4cmの辺をたどって移動するのと、5cmの辺をたどって移動するのとでは
 移動した長さが異なる。
B孤立点は 辺がない点(次数が0の点)のことを言う。
C正しい。3つの頂点全てに2つの辺(次数=2)がある。
D無向完全グラフは全ての点同士が辺で結ばれているグラフであり、
 頂点の数が n であれば、辺の数は n(n-1)/2 本である。
 例えば四角形の場合、頂点は4つ、辺の数は6つである。

EXCELのマクロのご相談なら ファーストマクロ 



V−5 目次 V−7
ファーストマクロ TOPページ