1．完全グラフ Kn について次の設問に答えなさい（1）サイズを答えなさい

1．完全グラフ Kn について次の設問に答えなさい
（１）サイズを答えなさい
（２）全ての頂点の次数を加えた値を答えなさい
（３）奇数次数の頂点はいくつあるか答えなさい（n で場合分けせよ）
2．完全 2 部グラフ Kmn について次の設問に答えなさい。
（１）位数とサイズを答えなさい
（２）全ての頂点の次数を加えた値を答えなさい
（３）奇数次数の頂点の数はいくつあるか答えなさい
3．一直線状に頂点を並べて、隣の頂点と結んだグラフは、線グラフ(path graph)
と呼ばれている。頂点数が n の線グラフを Pn と書くとき次の設問に答えなさい。
（１）サイズを答えなさい
（２）全ての頂点の次数を加えた値を答えなさい
（３）奇数次数の頂点の数はいくつあるか答えなさい
4．頂点数 n の木グラフ Tn について次の設問に答えなさい。
（１）サイズを答えなさい
（２）全ての頂点の次数を加えた値を答えなさい
5．完全グラフ K8 を描きなさい
6．完全 2 部グラフ K2,6 を描きなさい。
7．スターグラフ K1,5 を描きなさい。
8．頂点数 5 の木グラフを全て挙げ（描き）なさい
9．8 個の頂点からなる 3-正則グラフを 2 つ描きなさい
0 1 0 1


1 0 0 1
10．隣接行列が、 
で与えられる単純グラフを描きなさい。
0 0 0 1


1 1 1 0
11．次の問に答えなさい。
（１）頂点の集合 V と辺の集合 E が次のように与えられる単純グラフ G=(V,E)
を描きなさい。
V={a,b,c,d,e},
E={{a,b},{a,c},{a,e},{b,d},{c,e}}
（２）設問（１）で求めたグラフ G の隣接行列と接続行列を答えなさい。
（３）設問（１）で求めたグラフ G について頂点 b を始点とし、頂点 a を終点と
する長さ3のパスの数を答えなさい。
12．単純グラフ G=(V,E)において、
 deg
G
(v ) = 2 | E |
v∈V
が成り立つことを証明しなさい。
（⇒次数の総和は、偶数になる）
13．単純グラフにおいて次数が奇数である点は、偶数個存在することを示しなさい。
2|E |
14．単純グラフ G=(V,E)において、次数の平均が、
であることを示しなさい。
|V |
15．n 頂点の k-正則グラフの辺数を答えなさい
b
16．右のグラフ G=(V,E)について、次の設問に答えなさい。
1
（１）頂点 b に隣接する頂点を全て答えなさい。
a
（２）頂点 e に接続する辺を全て答えなさい。
2
（３）頂点 f の次数 deg(f) を答えなさい。
d
（４）グラフ G で最も次数の小さな頂点を答えなさい。
（５）グラフ G の隣接行列(adjacency matrix)を求めなさい。
ただし、行列の成分は、a,b,…,f の順に並ぶものとする
f
5
6
3
e
4
7
c
G = ( V, E )
V = { a, b, c, d, e, f }, E = { 1, 2, 3, 4, 5, 6, 7 }
17．頂点の集合 V と辺の集合 E が次のように与えられる単純グラフ G=(V,E) に
ついて、次の設問に答えなさい。
V={a,b,c,d,e,f,g,h}, E={{a,b},{a,c},{a,d},{b,f},{e,f},{f,g},{g,e}}
（１）グラフ G を描き、位数とサイズを答えなさい。
（２）頂点 a と頂点 d は隣接しているか？
（３）頂点 b と隣接する頂点を全て答えなさい
（４）頂点 g に接続している辺を全て答えなさい。
18．単純グラフにおいて、位数 8、サイズ 6 のグラフは連結グラフか？
19．単純グラフにおいて、位数 8、サイズ 22 のグラフは連結グラフか？
20．次の次数列を持つ単純グラフは存在するか答えなさい。また、存在する場合は、
そのグラフを描きなさい。
（１）2, 2, 2, 1, 1
（２）3, 2, 2, 2, 1, 1
21．連結な平面グラフにおいて
頂点数 + 面数 = 辺数 + 2 （オイラーの公式）
が成り立つことを証明しなさい。
21．木グラフは 2 部グラフであることを示しなさい
22．G=(U,V,E) を|U|=|V|=n である完全 2 部グラフとする。G の補グラフ G の辺の数
を答えなさい。
23．n (≧2) 個の頂点を持つ木グラフには次数 1 の頂点が少なくとも 2 つ存在するこ
とを示しなさい。
24．頂点数 n が 3 以上の完全グラフ K3 は、ハミルトングラフであることを示せ。
25．ある頂点からの最短路木が、そのグラフの最小全域木とならない例を 1 つ示しな
さい。

Download Report