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