グラフについて（グラフ理論）

調査目的

  • グラフの用途を把握するため、概要を調査する
  • 厳密な数学的定義、種類などは記載しない

グラフとは

  • 点と二点間を結ぶ線のペア
    • 点：ノード（node, vertex）、線：エッジ（edge）
    • 以降、ノード（ノード数: $V$）とエッジ（エッジ数: $E$）と呼ぶ
  • ノードに何かのオブジェクト（とその属性）、エッジにそれらの関係性を表現させることが多い
  • 非線形構造
  • 複雑な問題・構造の可視化が可能で、最短経路の探索、BFS（幅優先探索）・DFS（深さ優先探索）の実装などに圧倒的に向く
https://ja.wikipedia.org/wiki/%E3%82%B0%E3%83%A9%E3%83%95%E7%90%86%E8%AB%96

計算機上での表現方法

  • Edge lists（エッジリスト）
    • 隣接するノード、（必要なら）エッジの重みを要素としてもつリスト（長さ2か3）のリスト（長さ$E$）
      [ [node1, node2], [node2, node3, edge2-3], ... ]
    • メリット
      • 簡単でメモリ空間が複雑にならない
      • ノードが大量にあり、エッジが少ない場合は便利
    • デメリット
      • エッジが存在するかどうかを探索するだけでもすべての要素をチェックしないといけない等、基本的に探索に時間がかかる
      • 同じノード間に複数種類のエッジが存在する場合、一つの行列では表現不可能
  • Adjacency matrices（隣接行列）
    • $V \times V$の行列を用意し、それぞれの要素にエッジの重みをもたせる
    • メリット
      • ノード間にエッジが存在するかどうかの探索が容易
      • グラフを行列として扱うことができる（固有値などを考察できる）
    • デメリット
      • ノードが非常に多い場合、莫大なメモリが必要になる
  • Adjacency lists（隣接リスト）
    • 隣接するノードと重みのリスト（長さ：1か2）のリスト（長さ: 隣接しているノードの数）をもつリスト（長さ$V$）
    • メリット
      • 隣接するノードの探索が容易
      • 比較的（隣接行列より）メモリが少なくて済む
    • デメリット
      • ノード間にエッジが存在するかどうかの探索に比較的（隣接行列より）時間がかかる

用途例

化学・生物学

  • 分子構造
    • 原子と分子間の結合関係の解析
    • 分子構造の比較
  • PPI (タンパク質 – タンパク質相互作用) ネットワーク解析
  • DNA
    • 遺伝子調節
    • 転写制御

Internet

  • 検索エンジン
  • データ転送のルーティング
  • ソーシャル メディア サイトで人々の間の関係・相互作用のモデル構築
  • エリアまたは建物内の人々の動きマッピングによる混雑緩和等
  • 最適な利用周波数帯割り当て予測

自然言語処理

  • 言語ツリーの構文解析と言語ツリーの文法解析
  • 特定の単語が関連する単語の分析

交通システム・地図

  • 最短経路探索
  • 渋滞予想
  • フライト スケジュール
  • 地域の成長に関する経済予測
  • 新しい道路や鉄道の設計

医療

  • 感染病の拡大予測
  • がん治療（がん細胞の成長・転移予測）

そのほか

  • 電子回路の配線
  • 家系図解析
  • 数独パズルの解析

参考

項目調査まとめグラフ理論

Posted by ttnt