担当：Defolos
日付：2006-10-28
行列(matrix)：数字を行と列に、長方形状に並べたもの
行列Aに対し、a11などを行列の成分あるいは要素という
横方向に並んだ要素を行(row)と呼び、縦方向に並んだ要素を列(column)と呼ぶ
行列のi行目、j列目の要素を特に行列の(i, j)要素と呼ぶ
行列における加減算は、各行列の(i, j)要素を加減算する
この場合、行列Aの(i, j)要素と行列Bの(i, j)要素を加減算すればよい
ここでは加算の場合の例のみを挙げるが、減算も同様に計算できる
行列の積算はAの横要素とBの縦要素を掛けたものを足し合わせる
行列A,Bを掛けた行列Cは次のようになる
行列の積算は次の公式を覚えておくとよい
cij = ai1*b1j+ai2*b2j+ai3*b3j...ain*bnj
[A]{m*n}, [B]{n*r}, [C]{m*r} = [A]*[B]
空グラフ(null graph)：辺集合が空であるグラフ
点のみからなるグラフ、辺のないグラフとも言える
n個の点からなる空グラフはNnと表現される
完全グラフ(complete graph)：異なる2つの点が全て隣接している単純グラフ
∀v,v' ∈ V(G)に対し、v,v'を両端とする辺が唯一1個存在するグラフ
n個の点からなる完全グラフはKnと表現される
Knの辺の総数はグラフKの中の2点のペアの数全てと等しいため、nC2 = n(n-1)/2と表すことができる
r-正則グラフ(regular graph)：どの点の次数も全て共通にrであるグラフ
∀v ∈ V(G)に対し、dev(v) = rであるグラフ
3-正則グラフは特に、3価グラフ(trivalent graph)と呼ぶことがある
プラトングラフ：プラトン立体の頂点と辺からなるグラフ
プラトン立体はユークリッド空間に表現できる正多面体のことである
幾何学的定義は「その表面を囲む全ての面が同じ形の正多角形で、各頂点への辺と面のつながり方も全く同じになっている３次元図形」
プラトン立体は5つだけしかなく正4面体、正6面体、正8面体、正12面体、正20面体がプラトン立体である
閉路グラフ(cycle graph)：次数が2の正則連結グラフ
n点からなる閉路グラフはCnと表現される
道グラフ(path graph)：閉路グラフCnからひとつの辺を削除して得られるグラフ
n点からなる道グラフはPnと表現される
車輪(wheel)：Cn-1に新しく点vを追加し、追加した点vと他の点を辺で結んでできるグラフ
真ん中に配置された点vから伸びる辺はスポークと呼ばれる
n点からなる車輪はWnと表現される
ピータースン・グラフ(petersen graph)：図のような形状を持つグラフのことである
今後の演習課題や問題などで現れることがある
3正則グラフの代表例である
二部グラフ(bipartite graph)：グラフGの点集合を、二つの素な集合AとBに分け、Gの全ての辺はAの点とBの点を結ぶようなグラフ
完全二部グラフ(complete bipartite graph)：二部グラフにおいてAの各点とBの各点とがちょうど1本の辺で結ばれているグラフ
Aの点r個、Bの点s個からなる完全二部グラフはKr,sと表現される
K1,nであるグラフは特に星グラフ(star graph)と呼ばれる
Kr,sには、r+s個の点とr*s本の辺がある
k-立方体(k-cube)：グラフのそれぞれの点をベクトルに対応させたグラフ
ベクトル(a1, a2, a3, .... ak)は1か0かの2進数である
ベクトルに対応させた点同士を辺で結ぶが、そのときベクトル成分が1つだけ異なる点同士しか結んではならない
このような正則二部グラフをk-立方体と呼ぶ
k個のベクトル要素からなるk-立方体はQkと表現される
k-立方体は次元を考えながらうまく点を配置すると、k次元の立体になる
Qkには2^k個の点があり、k*2^(k-1)本の辺がある
単純グラフの補グラフ(complement)：点集合V(G)を持ち、Gの補グラフの2点が接するのはGにおけるその2点が隣接していない場合のみに限るような単純グラフ
元のグラフと補グラフとの和は完全グラフである
Gの上に線を引いた記号で表現するが、フォントがないのでここではG￣のように表現する
下図のような8つの円の中にA,B,C,D,E,F,G,Hの8つの文字を入れることを考える
ただし、アルファベット順で隣に来る文字はお互いに隣接しないように置く
着眼点
上記の着眼点を考慮しながら配置する
#1,#2は次数が6であるため、AかH以外は配置することができない
次に#1が隣接しない唯一の点である#8にBを配置する
同様に#7にGを配置する
後は残りの文字を隣接しあわないように残った円に配置すれば回答が求められる
下図の展開図から立方体を作り、それらを積み重ねて四角柱をつくり、四角柱の4つの側面にそれぞれ4つの色が現れるような積み上げ方をみつけたい
以下の問い1～3に答え、このような配置を求めよ
それぞれのキューブを立体に組み立てた場合に平行しあう面を辺で結ぶ
これを全てのキューブについて行う
求めたグラフを全て重ね合わせる（グラフ同士の和を求める）と次のようになる
ここから次の条件に合致する部分グラフH1,H2を見つけ出す
H1は前後の色の組を表しており、H2は左右の色の組を表している
H1において辺1が結んでいる点はGとRであるため、cube1の前面はG、後面はRである
H2において辺1が結んでいる点はRとBであるため、cube1の左面はR、右面はBである
下図のグラフGに関して以下の問いに答えよ
接続行列の定義通りに書き出すと、次のようになる
接続行列は点iと辺jがつながってるときには1を、つながっていないときには0を行列のij成分に書く
接続行列の各列の要素の和は常に2であり、辺一本に対する点の数を表している
握手補題から辺一本の両端には点がそれぞれひとつづつある→点の数は2
接続行列の各行の要素の和は各点における次数を表している
点iに接続している辺の数＝点iにおける次数
次数は接続行列のすべての成分の和
辺の数は接続行列の列の数であり、接続行列の各列の和は必ず2であるため次の式が成り立つ
∑{v∈V(G)}deg(v) = 2e(G)
下図の完全グラフK5について以下の問いに答えよ
点の数は5であるため5*5の行列である
単純グラフにはループがないため、対角成分は0
完全グラフは他の点と一本ずつ線で結ばれているため、他の成分は1
点1と点3を結ぶ長さ2の歩道は次の3つである
接続行列を計算すると次のようになる
A^2の第(1,3)要素は3であり、点1と点3を結ぶ長さ2の歩道の数と等しいことが確認できた
点1と点3を結ぶ長さ3の歩道は次の13通りである
接続行列を計算すると次のようになる
A^3の第(1,3)要素は13であり、点1と点3を結ぶ長さ3の歩道の数と等しいことが確認できた
隣接行列のij成分は点iから点jへの道がある場合1、そうでない場合0が入る（単純グラフの場合）
上記のAに対してA^2を行うと次のようになる
a12*a21は点1から点2へ、点2から点1へ行く道が存在するなら1になる
片方でも道がない場合は0*1となるため、0になる
また、Aの2乗なので二つの成分をかけることになる
これをグラフで表すと次のようになる
A^2の(2,1)成分をグラフにしている
(2,1)成分はaij*ajkのように添え字の内側同士は同じ値である
これはiからkへの道を表しており、iからjへの道、jからkへの道がある場合はiとkはつながってると言える
掛け算するので、iからjへの道とjからkへの道の両方があってはじめて1になるため、道の数を表すことになる
点2から点1への道と点1から点1への道（ループ）があるので、点2から点1への道数は1
点2から点2への道（ループ）と点2から点1への道があるので、点2から点1への道数は2
点2から点3への道と点3から点1への道があるので、点2から点1への道数は3
同じようにA^3を行うと次のようになる
これを展開する
Aを3乗しているのでそれぞれの掛け算の部分は3つの成分をかけることになる
この掛け算の部分は全て aij*ajk*aklのようになっている
点iから点jへの道があり、点jから点kへの道があり、点kから点lへの道がある場合に限ってこの部分が1になる
これは点jから点lへの道があるかどうかということである
3つの辺が関係する点iから点lへの道の組み合わせ全てを試しており、道が存在する場合には1カウントアップしている
このことから、点iから点lへの道の個数になる
完全三部グラフKr,s,tはそれぞれに属する点の個数がr,s,tである3つの点集合からなり、異なる集合に属する点は全て辺で結ばれているグラフである。このとき、以下の問いに答えよ。
K2,2,2は2つの点を持つ集合が3つあるグラフである
K3,3,2も同様にして描くことができる
Kr,s,tの辺の本数はrs+rt+st本
rをグループA、sをグループB、tをグループCとする
グループA,Bのみで考えると、Aの点ひとつから出る辺数はBの点の数だけあり、Aの全ての点において考えるとr*sとなる
グループCも考える場合には、A,Bに加え、A,C,とB,Cも同様に考えるため、rs+rt+st本の辺が存在すると言える
次数5の正則二部グラフはK5,5がある
二部グラフであるプラトングラフは次のようなものがある
ここでは正6面体を例に挙げているが、これ以外のプラトングラフではひとつの面を構成する点の数が奇数となり、二部グラフとはならない
4つの点からなる完全グラフは車輪である完全グラフと言える
11個の点を持つ3次グラフは存在しない
拍手補題より次数3、点数nのグラフの辺数mは m = 3n / 2
辺数は必ず整数でなければならいため、nは偶数以外とることができない
よってn=11の場合、グラフを書くことはできない
次数4の正則グラフでK5,K4,4,Q4以外のグラフとしては次のような正八面体が挙げられる
自己補対のグラフは点の数によって描ける、描けないがある
あるグラフとその補グラフとの和は完全グラフであり、点数nの完全グラフの辺数mは m = n(n-1) / 2である
自己補対のグラフの辺数は完全グラフの辺数の半分 n(n-1) / 4である
点数nは「n(n-1) / 4」の式に当てはめたときに整数になるn = 4kまたはn = 4k + 1である（kは整数）
このことから与えられた点数nが4k個、または4k + 1個の場合は自己補対のグラフを描くことができる
点数が4の場合を考えると、4k(k=1)個の点があることになるので自己補対グラフを描くことができる
各点の次数は、独立点が生じたり次数が3になったりしてはいけないため、1か2に限られる
次数1の点の数をL、次数2の点の数をMとすると、次の等式を満たさねばならない
この式を解くとL=2、M=2となる
ここから次数1の点が2個、次数2の点が2個あることがわかり、次数列は(1,1,2,2)である
同様に5個の点からなるグラフも、4k + 1個の点があるので自己補対グラフを描くことができる
次数1の点の数をL、次数2の点の数をM、次数3の点の数をNとすると次の等式を満たす必要がある
この式を解くとL=1、M=3、N=1あるいはL=2、M=1、N=2となる
ここから次数列は(1,2,2,2,3)あるいは(1,1,2,3,3)であるが、前者では自己補対のグラフは描けない
これまでL,M,Nは1以上の数として解を求めてきたが、これらは0も取りうる
L=0、M=5、N=0も解として存在し、このとき次数列は(2,2,2,2,2)である
k=2とすると4k=8であり8個の点を持つ自己補対グラフは描くことができる
8個の点を時計回りに配置する
8個の点の奇数番目の点(1,3,5,7)に関して完全グラフを作る
奇数番目の点と、その点+1番目の偶数の点とを結ぶ
偶数番目の点と、その点+3番目の点とを結ぶ
上記を行ったグラフと、奇数と偶数を入れ替えて同じ動作を行ったグラフとは自己補対の関係になる
次のような展開図を持つ4つの立方体の問題には解がないことを示せ
各キューブのグラフは次の通り
各キューブのグラフを重ね合わせたグラフGは次の通り
ここから次の条件を満たす部分グラフH1,H2を作ることは不可能である
それゆえに解は存在しない