📂グラフ理論

レギュラーグラフ

定義 ¹

1. 全ての頂点の次数が同じであるグラフをレギュラーグラフ^{regular Graph}と言う。特に、全ての頂点の次数が$r$の場合、$r$-レギュラーグラフと言う。言い換えると、次を満たすグラフ$G$を$r$-レギュラーグラフと言う。 $$ \deg (v) = r \qquad , \forall v \in V(G) $$
2. $2$-レギュラーな連結グラフをサイクルと言う。

例

レギュラーグラフ

• ペーターセングラフ
• プラトニックグラフ：正多面体をグラフで表したもの。ペーターセングラフと同様に$3$-レギュラーグラフであり、以下の五つだけが存在する。
  
• 完全グラフ：グラフの頂点数が$n$であれば、$(n-1)$-レギュラーグラフは完全グラフとなる。

サイクル

サイクルは、最も単純な形のグラフであり、純粋なグラフ理論では大きな関心を集めている。もちろん、サイクルグラフ自体のことではなく、グラフ内でサイクルの形をした部分についての話である。[ NOTE: サイクルからたった一つのエッジを取り除いたグラフもパスと呼ばれる。] サイクルの形を直接見れば、なぜ$2$-レギュラーがサイクルと呼ばれるのかすぐに理解できる。

一方、なぜサイクルが連結である必要があるのかについての例は次の通り。二つのコンポーネントで構成された次のグラフ$G = A \cup B$は確かに$2$-レギュラーだが、二つのサイクルのユニオンとして表されるため、真のサイクルと呼ぶにはふさわしくないことがわかる。もちろん、$A$と$B$はそれぞれがサイクルである。