【グラフ理論とネットワーク理論】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を２つに分けて見た時(それぞれをサブグラフV1、V2とすると)、V1とV2を繋ぐ辺のセットをカットセットと呼ぶ。例としては、島が２つあり、それぞれの島にはグラフ(ネットワークなど)が形成されてる状態を考える。この時、２つの島を繋ぐ辺の事をカットセットと呼ぶ。生命線のようなもの。
木とカットセットに関する定理
Gを覆うTは、Gのあらゆるカットセットと少なくとも１本の共通な枝を持っている。
