[学習記録]グラフ理論１

参考資料

https://ocw.hokudai.ac.jp/wp-content/uploads/2016/01/GraphTheory-2007-Note-all.pdf

イントロダクション

グラフとは何か

グラフ　・・・　点（Vertex）および辺（Edge）からなる図形
次数　　・・・　ある点を端点とする辺の数

次数は点を指定することにより定義される量になる
 deg(P) = 3, deg(Q) = 4

点の数　＝　位数、点数、ｎ、｜G｜（グラフをGとしたとき）
辺の数　＝　辺陬、｜｜G｜｜（グラフをGとしたとき）

グラフに意味を持たせる
グラフをうまく現実の物事に当てはめることによって、有益な情報を得ることができる

グラフの同形成
グラフは点と辺の集合であり、距離的な性質とは無関係である
（数学的には、同形か否かは写像でのAとBの１対１対応があるかどうかで判定される

グラフは図形描画以外にも、隣接行列、接続行列等を用いても表現することができる

様々なグラフとその例

グラフの性質から、様々なグループに分類されている

１．多重辺、ループ、単純グラフ
多重辺・・・任意の点Ｐ、Ｑを２本以上の辺が結んでいる場合
　　（ＰＱは多重辺である、などという）
ループ・・・任意の点ＰからＰに戻る辺を持つ場合
単純グラフ・・・多重辺やループを持たない

２．有向グラフ（Directed Graph,、Digraph）
辺に向きが与えられたグラフのこと
歩道（walk）・・・連結した辺の数
道（path）　・・・どの点も高々一度しか現れない歩道
閉路（cycle）・・・その名の通り、サイクルになっているようなもの
　　　　　　　　　PQ, QS, SPのように道があったとき、閉路になる

３．連結、非連結グラフ
全ての点が道でつながっているか否かで判断（分断されているか否か）
非連結グラフの時、それを構成する連結グラフを成分(Component）とよぶ
A - B - C      D - E 　→　成分数：２になる

４．名前付きグラフ
考案者の名前が付いたグラフ。いろいろある。
オイラーグラフ　・・・　すべての辺をちょうど一回ずつ通って出発点に戻る歩道を含むグラフ
ハミルトングラフ・・・　すべての点をちょうど一回ずつ通って出発点に戻るグラフ

該当する条件を見つけることによっていずれかのグラフであるかを判定するのは容易でない。しかし、各グラフであるための十分条件があり、それぞれオイラーの定理、オーレの定理としてまとめられている

５．木
どの２点にも道が１本しかないグラフのこと

練習問題

1.1.1  C5H12の構造異性体について、対応するグラフをかけ
1.1.2   John は Joan が好きで, Jean は Jane が好きで, Joe は Jean と Joan が好き で, Jean と Joan は 互いに好きである. John, Joan, Jean, Jane 及び Joe の間の関係を説明する有向グラフを描け
1.1.3  a,b,c,d,e,f の 6 チームでホッケーの試合をすることになった. 各チームの行った試合数は
a b c d e f 
2 2 4 4 3 1
であったとき、考えうる組み合わせを全てかけ。ただし、同一カードは２試合以上行わないものとする

1.2.1  点の集合が V = {v1, v2, v3, v4, v5, v6} で与えられ, かつ, 辺の集合が E = {v1v3, v2v3, v3v4, v4v1, v4v3, v5v6} からなるグラフを描け.
1.2.2  ヘビはカエルを食べ, トリはクモを食べる. トリとクモはどちらも虫を食べる. カエルはカタ ツムリ, クモ, および, 虫を食べる. この捕食行動を表す有向グラフを描け

1.3.1  身の回りの事柄で, それが「木」のグラフで表現できるものを一つ挙げよ.
 　　→　樹形図
1.3.2  どの辺の 2 つの端点も異なる集合 (グループ) に属するように n 個の点を 2 分割するようなグ ラフを 2 部グラフと呼んでいる. このとき, n = 7 である 2 部グラフを描き, そのグラフが奇 数本の辺からなる閉路を含まないことを示せ. (※実はグラフに奇数本の辺からなる閉路が含まれないことが 2 部グラフであるための必要十 分条件となっているのであるが, この証明は後に詳しく見て行くことにする. ここでは, 具体 的に上記の事実を n = 7 の 2 部グラフに対して示すだけでよい.)

1.4.1　略
1.4.2  点集合 V と辺集合 E がそれぞれ, V = {v1, v2, v3, v4, v5} E = {v1v2, v2v3, v3v4, v4v5, v5v1, v1v3, v3v5, v5v2, v2v4, v4v1} で与えられるグラフの概形を描け. また, このグラフの持つ特徴を考察し, それらのうち 2 つ を挙げよ.

・全ての次数が同じであり、4となっている。
・オイラーグラフであり、ハミルトングラフでもある。