グラフ理論に関する次の記述のうち、最も適切なものはどれか。
@ 完全2部グラフは、すべての頂点同士が辺で繋がっている。
A 距離を重みとする重み付きグラフでは、ある頂点から別の頂点への移動に
要する重みは、どの順路でも常に同じである。
B 頂点から出た辺が同じ頂点に戻るループのみである場合、その頂点は
孤立点である。
C 3つの頂点及び3つの辺で構成される単純閉路グラフならば、いずれの
頂点でも次数は2である。
D 無向完全グラフでは、頂点の数をnとしたとき、辺の数は2nとなる。
@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のマクロのご相談なら ファーストマクロ へ
タグ:グラフ理論