2016年10月26日

平成28年度 技術士第一次試験問題 情報工学部門 V−6

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のマクロのご相談なら ファーストマクロ 



タグ:グラフ理論
posted by ファーストマクロ at 18:58| Comment(0) | H28技術士一次試験(情報工学)
この記事へのコメント
コメントを書く
お名前:

メールアドレス:

ホームページアドレス:

コメント:

認証コード: [必須入力]


※画像の中の文字を半角で入力してください。