Matsushita's Blog

【グラフ理論とネットワーク理論】Graph #1

グラフとは何か

グラフは以下のコンポーネントで成り立つ。

  • 節点、頂点: 対象物(スイッチ、ルータ)
    Node, Vertex: Objectives(Switch, Router)

  • 枝、辺: 接点間の関係(伝送路)
    Branch, Edge: Relation among nodes(Transmission lines)

つまり、グラフとは節点と枝によって構成される。

グラフには既に名前が付けられているものがある。

・空グラフ Empty graph: ノードだけでエッジを持たない。
・完全グラフ Complete graph: 全てのノード間にエッジを持っている。
・補グラフ Complement graph: 元のグラフを補完するグラフ。元のグラフと補グラフを足すと完全グラフとなる。

グラフの性質

・同形 Isomorphic: あるグラフと同じグラフ。接点数、枝数、関係性も同じなグラフ。
・平面グラフ Plane graph: どの辺同士も交差しないグラフ。
・非平面グラフ Non-plane graph: どんな同形も枝同士の交差を生んでしまうグラフ。
・有向グラフ Directed graph: 辺に向きがあるグラフ。
・無向グラフ Undirected graph: 辺に向きが無いグラフ。

経路と連結性 Path and Connectivity

経路、連結は以下のように定義されている。

  • 経路、道: 始点Vsから終点Vtに至る枝の系列
    Route, Path: Series of branches from source Vs to sink Vt
  • 連結: VsからVtに経路がある
    Connected: There is a route from Vs to Vt
  • 強度に連結 Strongly connected: Vs→Vt、Vt→Vs

グラフ理論における経路、連結性に関する性質

・連結グラフ: すべての節点が他のどの節点とも連結しているグラフ
 Connected graph: Every node is connected to any other node.
オイラー線: グラフの全ての枝を通る一筆書きの閉路
 Euler line: Loop drawn with a single stroke of the brush.
オイラーグラフ: オイラー線が存在するグラフ
 Euler graph: Graph which has an Euler line.
・局所次数: 節点に付いている枝の数
 Local degree: The number of branches of a node

グラフ理論における定理(教養として)

グラフがオイラーグラフであるための必要十分条件は、すべての節点の局所次数が偶数であることである。

木とカットセット Tree and Cutset

木とは以下のようの定義されている。

  • 木: 閉路を持たない連結グラフ
    Tree: Connected graph without loops

木の性質

・木は枝数が最も少ない:
 今の状態から枝を足そうとすると閉路ができてしまい、木ではなくなる。
・覆う:
 元のグラフをGとし、Gからできる木をTとした時に、TはGを覆うと言う。
 通信網を作る時に始めはTの状態からスタートさせ、トラフィックが増えるにつれてGの状態にしていく。

カットセットとは

あるグラフGを2つに分けて見た時(それぞれをサブグラフV1、V2とすると)、V1とV2を繋ぐ辺のセットをカットセットと呼ぶ。例としては、島が2つあり、それぞれの島にはグラフ(ネットワークなど)が形成されてる状態を考える。この時、2つの島を繋ぐ辺の事をカットセットと呼ぶ。生命線のようなもの。

木とカットセットに関する定理

Gを覆うTは、Gのあらゆるカットセットと少なくとも1本の共通な枝を持っている。