本文へスキップ

技術士試験(情報工学部門)・情報技術者試験。ファーストマクロ。


Since 2016.4.19

令和元年度 技術士第一次試験問題(再)【専門科目】

V−7

グラフ理論に関する説明として、最も適切なものはどれか。

@ 3つの頂点及び3つの辺で構成される単純閉路グラフならば、いずれの頂点でも次数は2である。

A 完全2部グラフは、全ての頂点同士が辺で繋がっている。

B 距離を重みとする重み付きグラフでは、ある頂点から別の頂点への移動に要する重みは、どの順路でも常に同じである。

C 頂点から出た辺が同じ頂点に戻るループのみである場合、その頂点は孤立点である。

D 無向完全グラフでは、頂点の数をnとしたとき、辺の数は2nとなる。


類題

H28 V-6


正解

@


解説

@ 正しい。3つの頂点全てに2つの辺 (次数=2) がある。

A 2部グラフは、頂点の集合を2つの集合 (部分集合) に分割し、各集合内の頂点同士には辺がないグラフのことである。
完全2部グラフは、2部グラフのうち、全ての頂点がつながっているグラフのことである。
例えば○3つ、●3つがあったとすると、○同士には辺がなく、●同士にも辺がないが、全ての○と全てのの●が辺でつながっているグラフのことである。

B 3辺の長さが、3cm、4cm、5cmの三角形もグラフであるが、3cm, 4cmの辺をたどって移動するのと、5cmの辺をたどって移動するのとでは移動した長さが異なる。

C 孤立点は、辺がない点 (次数が0の点) のことを言う。

D 無向完全グラフは、全ての点同士が辺で結ばれているグラフである。頂点の数が n であれば、辺の数は n(n-1) / 2本である。例えば四角形の場合、頂点は4つ、辺の数は6つとなる。

V−6 目次 V−8