あたらしいグラフ理論入門

概要

本

• あたらしいグラフ理論入門 | 小林 みどり

かかった時間

• 6.8 時間

読む前の状態

• やさしく学べる離散数学 を読んだあと、グラフ理論を補足するために読み始めた

  • グラフ理論については、基本の基本についてだけ学んだ状態

  • 重複している内容はこの後の読書メモではカットしている

感想

• 内容的には「やさしく学べる離散数学」ですでに学んでいる内容も多かったが、入門としてはこのくらいの範囲なんだなということがわかった

• どういう問題に対してグラフ理論が適用できるか具体的に示されているので、そこには新しい発見も多かった

読書メモ

1. グラフとは

• 様々な事象をグラフで表すことの目的・意義としては次のような点が挙げられる

  • グラフに表すことで、複雑な事象の全体が視覚的にとらえられ、分かりやすくなる

  • 全体の構造が把握しやすくなる

  • 各点の特徴がとらえやすくなる

  • グラフ化の基準を明確にしておけば誰でも同じ結果が得られるため、恣意性を排除できる

• ただし、得られたグラフを解釈する時には、いろいろな特性を切り捨てて単純化したことに注意する必要がある

2. 論理と証明

• 鳩の巣原理

  • 鳩の巣が n 個あり、鳩は n + 1 羽以上いる。どの鳩も巣に入っている時、鳩が 2 羽以上入っている巣がある(n は自然数)

  • この原理は「引出し論法」とも呼ばれる

3. グラフの定義と用語

• 「隣接」と「接続」は日本語では意味が似ていて紛らわしいが、これらはそれぞれ英語の adjacent と incident の訳である。adjacent は同種のものが結びついている時に使い、incident は異種のものが結びついている時に使われる

• グラフの内周と外周

  • グラフの内周とは、グラフの最小のサイクルの長さのこと

  • グラフの外周とは、グラフの最大のサイクルの長さのこと

• 距離と直径

  • グラフにおける 2 頂点 u, v との距離(distance)とは、u から v へ行くパスのうち、最短のパスの長さのこと

    • パスがない時、距離は無限大であるとする

  • 連結グラフにおいて、すべての 2 頂点間の距離の最大値をそのグラフの直径という

4. いろいろなグラフ

• 林・木

  • サイクルのないグラフを林(forest)という。サイクルのない連結グラフを木(tree)という

5. 多重グラフと有向グラフ

• 多重グラフ

  • 多重辺とループの存在を許す時、多重グラフという

• 単純グラフ

  • 多重辺やループのないグラフ

• 強連結・弱連結

  • 有向グラフにおいて、どの頂点からどの頂点へも有向辺に沿って行ける時、その有向グラフは強連結であるという

  • 有向辺の向きを無視した時にできるグラフが連結である時、その有向グラフは弱連結であるという

• ネットワーク

  • グラフの辺や有向辺に機能を付け加えたものをネットワークと呼ぶ

6. 二部グラフ

• 偶数サイクルと奇数サイクル

  • サイクル(閉路)について、長さが偶数の時は偶数サイクル、奇数の時は奇数サイクルという

• 二部グラフの性質(グラフ G に頂点は 2 個以上あるとする)

  • グラフ G が二部グラフの時、G のどのサイクルも偶数サイクルである

  • グラフ G にサイクルがない時、G は二部グラフである

  • グラフ G のどのサイクルも偶数サイクルのとき、G は二部グラフである

7. 木

• 木の性質

  • 木について、q = p - 1 が成り立つ

    • グラフの頂点の個数を p、辺の本数を q とする

  • 木のどの頂点からどの頂点へも、行く道(パス)は 1 通りしかない

  • 木や林は二部グラフである。ただし位数は 2 以上とする

  • 連結グラフ G において q = p - 1 が成り立つ時、G は木である

• 林の性質

  • 林については q = p - k が成り立つ

    • k は林の連結成分の個数である

• 木の中心

  • 離心数

    • 連結グラフ G において、頂点 v から最も遠い頂点までの距離を、頂点 v の離心数という

  • 中心点

    • 離心数が最小の頂点を、そのグラフの中心点と呼ぶ

  • 中心(センター)

    • すべての中心点の集合を、グラフの中心と呼ぶ

  • 木の中心は、1 点、または隣接する 2 点からなる

  • 単心的・双心的

    • 中心が 1 点からなる木を単心的、中心が 2 点からなる木を双心的という

• 二分木

  • 根付き木で、どの頂点も子が 2 個以下であり、かつ子について左の子か右の子か明示されているものを二分木(binary tree)という

• ポーランド記法

  • 二項演算の記号を 2 つの式の前に書く書き方をポーランド記法(または前置記法)という

• 逆ポーランド記法

  • 二項演算の記号を 2 つの式の後に書く書き方を逆ポーランド記法(または後置記法)という

  • 普通の書き方は中置記法という

8. サイクル分解とその応用

• オイラーグラフ

  • オイラー路

    • グラフ G のオイラー路とは、G のすべての辺を 1 回ずつ通る歩道のこと

  • オイラー閉路

    • オイラー路のうち、特に始点と終点が一致しているものをオイラー閉路という

  • オイラーグラフ

    • オイラー閉路を持つグラフをオイラーグラフという

• オイラーの一筆書き定理

  • グラフにオイラー路が存在するための必要十分条件は、グラフに奇点が高々 2 個しかないことである

  • 奇点が 2 個の時は、その 2 個の奇点がオイラー路の視点と終点である。奇点が 0 個の時は、オイラー閉路が存在する

• ハミルトングラフ

  • ハミルトンパス

    • グラフ G のハミルトンパスとは、G のすべての頂点を 1 回ずつ通るパスのこと

  • ハミルトンサイクル

    • グラフ G のハミルトンサイクルとは、G のすべての頂点を 1 回ずつ通る閉路のこと

  • ハミルトングラフ

    • ハミルトンサイクルを持つグラフをハミルトングラフと呼ぶ

• ハミルトンサイクル分解

  • 完全グラフのハミルトンサイクル分解

    • 完全グラフ Kn のすべての辺がいくつかのハミルトンサイクルに分解される時、これらのハミルトンサイクルの集合を、完全グラフ Kn のハミルトンサイクル分解という

  • 完全二部グラフのハミルトンサイクル分解

    • 完全二部グラフ Kn,n の n が偶数の時は、ハミルトンサイクル分解を作ることができる。n が奇数の時はハミルトンサイクル分解は存在しない

9. 点彩色とその応用

• 点彩色

  • グラフの点彩色とは、隣接する 2 頂点には異なる色を塗るというルールで、すべての頂点に色を塗ることを言う

• 彩色数

  • グラフ G を点彩色する時に最低限必要な色の数を、そのグラフの彩色数という

• グラフの彩色数と頂点の次数の関係

  • グラフ G の彩色数を χ(G) 、最大次数を ⊿(G) と書く時、次の式が成り立つ

    • χ(G) <= ⊿(G) + 1

• 辺彩色問題

  • 辺に色を塗る問題は辺彩色問題と呼ばれる

10. 平面的グラフ

• グラフの同相

  • 細分

    • グラフ G において、辺 e の間に 1 点を追加して新しいグラフを作る。そのグラフを G の基本細分という

    • G に基本細分を何回か繰り返してできるグラフを G の細分という

    • また G 自体も G の細分であるとする

  • 同相

    • グラフ H1 と H2 がどちらも、あるグラフの細分になっている時、H1 と H2 は同相であるという

• グラフの縮約

  • 縮約

    • グラフ G において、隣接する 2 点 u, v を 1 点とみなして新しいグラフを作る。そのグラフを G の基本縮約という

    • G に基本縮約を何回か繰り返してできるグラフを G の縮約という

• 平面的グラフの性質

  • 平面的グラフの部分グラフは平面的グラフである

  • K5 または K3,3 を含むグラフは平面的グラフではない

  • K5 または K3,3 の細分を含むグラフは平面的グラフではない

• クラフトスキーの定理

  • グラフが平面的グラフであるための必要十分条件は、K5 または K3,3 の細分を含まないことである

• ワグナーの定理

  • グラフが平面的グラフであるための必要十分条件は、K5 または K3,3 に縮約可能な部分グラフを含まないことである

11. オイラーの定理と平面的グラフの彩色問題

• オイラーの定理(p - q + r = 2)より示される平面的グラフの特徴

  • すべての頂点の次数が 6 以上のグラフは平面的グラフではない

    • 辺が全部で 6p / 2 以上であることから、q <= 3p - 6 と矛盾することを示せば証明できる

• 多重グラフの彩色問題

  • 平面的多重グラフでも 4 彩色可能

12.地図の塗り分け問題 - どんな地図でも 4 色で塗り分けられるか

• トーラス

  • ドーナツのような穴の空いた立体の表面をトーラスという

• トーラス上の地図の 7 色定理

  • トーラス上の地図を塗り分けるには 7 色必要であり、7 色あれば十分である

13. グラフの行列表示

• 有向グラフの接続行列(頂点と辺の行列)

  • n × m 行列であり、(i, j) 成分 (sij) は次のように決める

    • sij = 1 (頂点 vi が有向辺 ej の始点である時)

    • sij = -1 (頂点 vi が有向辺 ej の終点である時)

    • sij = 0 (いずれでもない時)

14. 支配グラフ

• 支配グラフ

  • どの 2 頂点間にも、どちらかの有向辺が 1 本ずつ引かれている有向グラフを支配グラフという

  • 支配グラフ G において、P → Q である時、P は Q を支配するという

• 支配点

  • 支配グラフ G において、自分以外のすべての頂点を 1 段階または 2 段階で支配する頂点がある時、その頂点を支配グラフ G の支配点と呼ぶ

  • 支配グラフにおいて、1 関係の数と 2 関係の数の和が最大の頂点を P とすると、P は支配点(の 1 つ)である

    • 支配グラフには支配点が 2 個以上存在することもある

  • 2 関係が何個あるかは A^2 を計算すればよい

• 支配点の存在定理

  • 支配グラフには支配点が存在する

15. 有向グラフの強連結分解

• 頂点 vi から vj への行き方

  • 有向グラフ G の隣接行列を A とする。A^k の (i, j) 成分は、頂点 vi から vj へ k ステップで行く行き方が何通りあるかを表している(k は自然数)

  • 1 <= k <= n - 1 であるすべての k について A^k の (i, j) 成分が 0 である時、頂点 vi から vj へは何ステップでも到達できない

• 到達可能行列

  • 一般に有向グラフ G の位数を n として、Dn-1 を Dn-1 = Dn-2 + A^n-1 = E + A + A^2 + ... + A^n-1

  • Dn-1 について「1 以上の数は 1 に置き換え、0 の時はそのままにしておく」ようにして得られる行列 D'n-1 を有向グラフ G の到達可能行列と呼ぶ

• 強連結分解

  • 極大

    • 強連結性を保ちつつ、それ以上大きくはできないという意味

  • 強連結成分

    • 極大の強連結な部分グラフのこと

    • 有向グラフの頂点集合は、いくつかの強連結成分に分けられる

  • 強連結分解

    • 有向グラフ G の強連結成分を G1, G2, ... , Gs とする。これらの強連結成分を頂点として、新しい有向グラフ G* を次のように作る

    • 強連結成分 Gi から Gj へ向かう G の有向辺が 1 本でもある時、新しい有向グラフ G* において、頂点 Gi から頂点 Gj へ有向辺を引く

    • このようにして得られる G* を、有向グラフ G の強連結分解という

• 強連結分解の手順

  • 各頂点 i について、次の集合を定義する

    • 先行点集合 A(i) = {j | rji = 1}

    • 到達点集合 B(i) = {j | rij = 1}

  • ここで A(i) ∩ B(i) は強連結成分を表す

  • A(i) ∩ B(i) = A(i) となるものからランク上位とし、ランク分けされた点は表から削除して、また A(i) ∩ B(i) = A(i) となるものを探す

  • 最後に有向辺を書き入れると強連結分解が完成する

16. スモールワールドネットワーク

• 格子グラフ

  • どの人も両隣の人、および 1 人おきの人と知り合いであるような規則的なグラフ

• ランダムグラフ

  • 知り合いがランダムに決められているグラフ

• リワイアリング

  • 辺をつなぎ替えることをリワイアリング(またはつなぎ替え)という

• 固有パス長

  • すべての 2 頂点間の距離の平均。L と書く

• クラスタ度

  • 頂点 v と隣接している頂点が d 個あるとする。その d 個の頂点の間に辺がある割合をクラスタ度という

  • つまり、最大では d(d - 1) / 2 本なので、実際に k 本あったとすると、クラスタ度 Cv は k / (d(d - 1) / 2) となる

• クラスタ係数

  • すべての頂点についてクラスタ度を計算し、その平均 C を、そのグラフのクラスタ係数と呼ぶ

• スモールワールドネットワーク (SWN)

  • つなぎ替えの確率 p = 0 の時、格子グラフとなり、クラスター性は強く、2 頂点間の平均距離は大きい

  • つなぎ替えの確率 p = 1 の時、ランダムグラフとなり、クラスター性は弱く、2 頂点間の平均距離は小さい

  • SWN は p が 0.001 ~ 0.1 くらいの時、2 頂点間の平均距離は小さくなるが、クラスター性は強いままの状態であるグラフのこと

    • 「なぜ世間はこんなに狭いのか」という疑問をよく説明するモデルとして、広く知られるようになった

    • リワイアリングの辺を持つ人の重要性が論じられている

• クリーク

  • 一般にグラフ G に完全グラフ Kl が含まれていて、それがそれ以上大きな完全グラフに含まれていない時、Kl はグラフ G のクリークと呼ばれる(l は 3 以上の整数)