logo

レギュラーグラフ 📂グラフ理論

レギュラーグラフ

定義 1

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

レギュラーグラフ

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

サイクル

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

20200211_141819.png

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

20200211_142214.png


  1. Wilson. (1970). Introduction to Graph Theory: p17. ↩︎