📂グラフ理論

グラフのオリエンテーション

Build-up

Let’s assume a directed graph $D$ is given.

1. A finite sequence of arcs is called a Directed Walk and is represented as follows: $$v_{0} v_{1} , v_{1} v_{2} , \cdots , v_{m-1} v_{m} \\ v_{0} \rightarrow v_{1} \rightarrow v_{2} \rightarrow \cdots \rightarrow v_{m-1} \rightarrow v_{m}$$ In this case, $v_{0}$ is called the Initial Vertex, $v_{m}$ is called the Final Vertex, and $m$ is referred to as the Length.
2. A directed walk with all distinct arcs is called a Directed Trail.
3. A directed walk with all distinct vertices is called a Directed Path.
4. If the start and end points of a directed walk are the same, it is said to be Closed.
5. A closed path is called a Directed Cycle.

An Arc refers to an edge with direction in a directed graph. The definitions above essentially redefine the definitions of walks, trails, paths, and cycles for directed graphs.

Before introducing the definition of orientation, let’s review the connectivity of general graphs.

Set Representation of Graphs: For two graphs $G_{1}$ and $G_{2}$, assume $V(G_{1}) \cap V(G_{2}) = \emptyset$. Then, the Union $G = G_{1} \cup G_{2}$ of the two graphs has the vertex set $V(G_{1}) \cup V(G_{2})$ and the edge set $E (G_{1}) \cup E ( G_{2} )$. If graph $H$ cannot be represented as the union of graphs, $H$ is said to be Connected.

Now, let’s define the orientation of graphs.

Definition

6. For any two vertices $v,w \in V(D)$ in the directed graph $D$, if there exists a directed path with the initial vertex $v$ and the final vertex $w$, then $D$ is said to be Strongly Connected.
7. If by assigning directions to the edges of graph $G$, it can be made into a strongly connected directed graph, then $G$ is said to be Orientable, and such a strongly connected directed graph is called the Orientation of $G$.

Explanation ¹

Unlike clean definitions of connectivity through the set representation of graphs, strong connectivity is defined through the existence of paths. It is not mathematically elegant but can be understood more intuitively. In hindsight, the connectivity of general graphs could also be defined through the existence of paths, but using set representation is similar to the way connectivity is defined in topology.

In simple terms, an Orientable Graph is a general graph $G$ that maintains connectivity even when changed to a directed graph. Obviously, if there is no connectivity, it cannot have strong connectivity. For example, the following graph shows that it becomes an orientable graph by having strong connectivity when directions are assigned.

Regarding orientable graphs, the following theorem related to cycles is known.

Theorem

Let $G$ be a connected graph. That $G$ is orientable and all its edges are included in at least one cycle are equivalent.

Proof

Strategy: If there exists an end vertex $v_{0}$ that does not belong to a cycle in the graph, regardless of how the directions are assigned, entering or leaving $v_{0}$ is inevitable, so it cannot be an orientable graph. From this fact, all vertices and edges of an orientable graph must belong to a cycle.

---

$(\Rightarrow)$

Let’s fix cycle $C$ of $G$. If all edges are part of $C$, there is nothing to prove, but suppose there is an edge $e \in E(G)$ adjacent to but not part of $C$. However, since $G$ is orientable, it must belong to another cycle $c '$. $c '$ can be seen as a newly formed cycle that includes the directions already given in $C$. Since $G$ is a connected graph, the same way, new cycles can be assigned to each edge not part of $C$ or $c '$. Therefore, all edges of $G$ belong to at least one cycle.

---

$(\Leftarrow)$

It is trivial. Since all edges belong to at least one cycle, it’s possible to reach any final vertex $w$ from any starting point $v \in V(G)$ by passing through various cycles.

■

ビルドアップ

有向グラフ$D$が与えられているとしよう。

1. アークの有限のシーケンスを有向ウォークと呼び、次のように表される。 $$v_{0} v_{1} , v_{1} v_{2} , \cdots , v_{m-1} v_{m} \\ v_{0} \rightarrow v_{1} \rightarrow v_{2} \rightarrow \cdots \rightarrow v_{m-1} \rightarrow v_{m}$$ このとき、$v_{0}$ を始点、$v_{m}$ を終点、$m$ を長さという。
2. 有向ウォークのアークが全て異なる場合、有向トレイルという。
3. 有向ウォークの頂点が全て異なる場合、有向パスという。
4. 有向ウォークの始点と終点が同じ場合、閉じているという。
5. 閉じたパスをサイクルという。

アークは、有向グラフにおいて方向を持つエッジを指す。上記の定義は、本質的には有向グラフにおけるウォークとトレイル、パス、サイクルの定義を再定義したものである。

オリエンテーションの定義を紹介する前に、一般的なグラフの接続性について見直そう。

グラフの集合表現: 二つのグラフ$G_{1}$と$G_{2}$に対して$V(G_{1}) \cap V(G_{2}) = \emptyset$とする。すると、二つのグラフのユニオン$G = G_{1} \cup G_{2}$は頂点セット$V(G_{1}) \cup V(G_{2})$とエッジセット$E (G_{1}) \cup E ( G_{2} )$を持つグラフである。グラフ$H$がグラフのユニオンとして表現できない場合、$H$は接続されているという。

では、グラフのオリエンテーションを定義してみよう。

定義

6. 有向グラフ$D$において、任意の二つの頂点$v,w \in V(D)$に対して、始点が$v$で終点が$w$の有向パスが存在する場合、$D$は強く接続されているという。
7. グラフ$G$のエッジに方向を付けて強く接続された有向グラフを作ることができれば、$G$はオリエンタブルであるといい、その強く接続された有向グラフを$G$のオリエンテーションという。

説明 ¹

グラフの集合表現を通じてきれいに定義された接続性とは異なり、強い接続性はパスの存在によって定義される。数学的にエレガントではないが、より直感的に理解できるだろう。振り返ってみると、一般的なグラフの接続性もパスの存在によって定義しても問題ないが、集合表現を使用するのは位相数学での接続性を定義する方法に似ているためである。

簡単に言えば、オリエンタブルなグラフは一般的なグラフ$G$を有向グラフに変更した場合でも接続性が維持されるグラフである。当然、接続性がなければ強い接続性も持つことはできない。例として、次のグラフでは、方向を与えたときに強く接続性を持つことにより、オリエンタブルなグラフであることが確認できる。

一方、オリエンタブルなグラフに関して、サイクルに関連した次の定理が知られている。

定理

$G$を接続グラフとする。$G$がオリエンタブルであり、その全てのエッジが少なくとも一つのサイクルに含まれることは同値である。

証明

戦略: グラフにサイクルに属さない頂点エンドヴァーテックス$v_{0}$が存在する場合、どのように方向を付けても、$v_{0}$には入るか出るしかないため、オリエンタブルなグラフになることはできない。この事実から、オリエンタブルなグラフの全ての頂点とエッジは必ずサイクルに属していなければならない。

---

$(\Rightarrow)$

$G$のサイクル$C$を固定しよう。もし全てのエッジが$C$に属するなら、証明することは何もないが、$C$に隣接しているが$C$には属していないエッジ$e \in E(G)$があるとしよう。しかし、$G$がオリエンタブルであれば、別のサイクル$c '$には属しているはずである。$c '$は、$C$にて既に与えられた方向を含む、新しく作成されたサイクルとみなすことができる。$G$は接続グラフであるため、同様の方法で、$C$や$c '$に属さない各エッジに対して新しいサイクルを割り当てることができる。したがって、$G$の全てのエッジは少なくとも一つのサイクルに属することになる。

---

$(\Leftarrow)$

自明である。全てのエッジが少なくとも一つのサイクルに属しているので、どのような始点$v \in V(G)$から出発しても、様々なサイクルを経由して任意の終点$w$に到達することができる。

■