グラフ理論に関する次の記述のうち、最も適切なものはどれか。
① 完全2部グラフは、すべての頂点同士が辺で繋がっている。
② 距離を重みとする重み付きグラフでは、ある頂点から別の頂点への移動に要する重みは、どの順路でも常に同じである。
③ 頂点から出た辺が同じ頂点に戻るループのみである場合、その頂点は孤立点である。
④ 3つの頂点及び3つの辺で構成される単純閉路グラフならば、いずれの頂点でも次数は2である。
⑤ 無向完全グラフでは、頂点の数をnとしたとき、辺の数は2nとなる。
④
① 2部グラフは、頂点の集合を2つの集合 (部分集合) に分割し、各集合内の頂点同士には辺がないグラフのことである。
完全2部グラフは、2部グラフのうち、全ての頂点がつながっているグラフのことである。
例えば○3つ、●3つがあったとすると、○同士には辺がなく、●同士にも辺がないが、全ての○と全てのの●が辺でつながっているグラフのことである。
② 3辺の長さが、3cm、4cm、5cmの三角形もグラフであるが、3cm, 4cmの辺をたどって移動するのと、5cmの辺をたどって移動するのとでは移動した長さが異なる。
③ 孤立点は、辺がない点 (次数が0の点) のことを言う。
④ 正しい。3つの頂点全てに2つの辺 (次数＝2) がある。
⑤ 無向完全グラフは、全ての点同士が辺で結ばれているグラフである。頂点の数が n であれば、辺の数は n(n-1) / 2本である。例えば四角形の場合、頂点は4つ、辺の数は6つとなる。
| Ⅲ－５ | 目次 | Ⅲ－７ |