次数 (グラフ理論)

次数（グラフ理論）

グラフ理論における次数（degree）は、グラフを構成する要素である「頂点」に、いくつの「辺」がつながっているかを示す基本的な数値です。ある頂点につながる辺の数をその頂点の次数と呼びます。特に、辺が同じ頂点に両端で接続している場合（これを「ループ」と呼びます）は、次数の計算において2本分の辺として数えます。特定の頂点 `v` の次数は `deg(v)` と表記されるのが一般的です。

グラフ全体について考える際には、いくつかの指標が用いられます。グラフ内のすべての頂点の中で最も次数が大きい値を最大次数と呼び、`Δ(G)` と表記されます。逆に、最も次数が小さい値を最小次数と呼び、`δ(G)` と表記されます。例えば、あるグラフで頂点に接続する辺の数がそれぞれ 3, 3, 3, 2, 2, 1, 0 であった場合、そのグラフの最大次数は 3、最小次数は 0 となります。全ての頂点が同じ次数を持つグラフは正則グラフと呼ばれ、その等しい次数をグラフの次数として言及することもあります。

グラフに辺の向きが定義されている場合、すなわち有向グラフにおいては、次数の概念はより細分化されます。頂点に入ってくる辺の数を入次数（indegree）、頂点から出ていく辺の数を出次数（outdegree）と呼び、区別します。

握手補題

無向グラフの次数に関する非常に重要な性質に、握手補題（handshaking lemma）があります。これは、「グラフの全ての頂点の次数を合計すると、辺の数のちょうど2倍になる」という法則です。数式で表すと、全ての頂点 `v` についてその次数 `deg(v)` を合計した値は、辺の総数 `|E|` の2倍、すなわち `Σ deg(v) = 2|E|` となります。この法則は、「ダブルカウンティング」と呼ばれる、同じ対象を二通りの方法で数え上げる証明手法の典型例として知られています。辺を数えるとき、辺の両端にある頂点を数えると、各辺は2つの頂点に接続しているため、辺の数の2倍が数えられます。一方、頂点の次数を合計するということは、各頂点に接続する辺を数えることになり、これも結局は全ての辺を両端の頂点から数え上げることと同じになるため、結果が一致します。

この握手補題が導く重要な帰結として、「次数が奇数である頂点の個数は、必ず偶数になる」というものがあります。なぜなら、全ての次数の総和は偶数（辺数の2倍）であり、この総和は偶数次数の頂点の総和（偶数）と奇数次数の頂点の総和に分けられるため、奇数次数の頂点の総和が偶数であるためには、奇数次数の頂点が偶数個なければならないからです。この補題の名前は、「ある集まりの中で、奇数人の人々と握手した人の数は常に偶数になる」という、握手を辺、人を頂点に見立てた数学の証明問題に由来しています。

次数列

次数列（degree sequence）とは、無向グラフに含まれる全ての頂点の次数を、通常は大きい順（非増加順）に並べた数列のことです。例えば、先ほどの例のグラフであれば、次数列は (3, 3, 3, 2, 2, 1, 0) となります。次数列はグラフのグラフ不変量の一つであり、互いに同型（構造が同じとみなせる）なグラフは必ず同じ次数列を持ちます。しかし、逆は必ずしも真ではなく、次数列が同じでも、グラフの構造が異なる（同型でない）場合があります。したがって、次数列だけではグラフを一意に特定することはできません。

与えられた整数の数列が、実際に何らかのグラフの次数列として存在するかどうかを判定したり、存在する場合にそのようなグラフを構成したりする問題は次数列問題と呼ばれます。特に、単一の辺のみで構成され、ループや多重辺を持たない単純グラフの次数列であるかどうかの判定は古典的な問題であり、Erdős-Gallaiの定理やHavel-Hakimiの定理といった判定基準が知られています。握手補題から、次数列の総和が奇数になる数列は、いかなるグラフの次数列にもなり得ないことが直ちに分かります。

特殊な次数

特定の次数を持つ頂点には特別な名称が付けられています。次数が0である頂点は、どの辺とも接続しておらず、グラフの他の部分から完全に孤立しているため、孤立頂点（isolated vertex）と呼ばれます。次数が1である頂点は、1本の辺のみに接続しており、葉頂点（leaf vertex）と呼ばれます。葉頂点と接続している辺は、ペンダント辺（pendant edge）と呼ばれることがあります。これらの概念は、特に木構造のような特定の種類のグラフを研究する際に頻繁に用いられます。

次数と包括的特性

次数は、グラフ全体の構造や他の様々な性質とも密接に関連しています。例えば、全ての頂点の次数が等しいk-正則グラフは、その次数 `k` によって特徴づけられます。また、グラフがオイラー路（グラフの全ての辺を一度ずつ通る道）を持つかどうかの判定において、奇数次数の頂点の数が重要な役割を果たします。具体的には、連結な無向グラフがオイラー路を持つのは、奇数次数の頂点が0個または2個の場合に限られます。

さらに、グラフの最大次数 `Δ` は、グラフ彩色数（頂点を隣り合う頂点と同じ色にならないように塗り分けるのに必要な最小の色数）や彩色指数（辺を隣り合う辺と同じ色にならないように塗り分けるのに必要な最小の色数）の上限を与える定理（Brooks' theorem や Vizing's theorem など）にも現れ、グラフの重要な特性を理解する上で基礎となります。

このように、次数はグラフ理論における最も基本的でありながら、グラフの多様な性質や構造を解き明かすための出発点となる非常に重要な概念です。

もう一度検索