次数（グラフ理論）

グラフ理論において、グラフの頂点の次数（または価数）は、その頂点に接続する辺の数です。多重グラフでは、ループは辺の両端に対して頂点の次数に2を加算します。^{[ 1 ]}頂点の次数${\displaystyle v}$と表記される${\displaystyle \deg(v)}$または${\displaystyle \deg v}$グラフの最大次数${\displaystyle G}$は、$\displaystyle \Delta (G)$、そして、の最大値です。${\displaystyle G}$の頂点の次数。グラフの最小次数は で表されます。${\displaystyle \delta (G)}$、そしては最小値です${\displaystyle G}$の頂点の次数。右に示す多重グラフでは、最大次数は 5、最小次数は 0 です。

正則グラフでは、すべての頂点の次数が同じなので、グラフの次数について話すことができます。完全グラフ（と表記）${\displaystyle K_{n}}$、 どこ${\displaystyle n}$はグラフの頂点の数です。 は、すべての頂点が可能な最大の次数を持つ特別な種類の正則グラフです。${\displaystyle n-1}$。

符号付きグラフでは、頂点に接続されている正のエッジの数を正の次数と呼び、接続されている負のエッジの数を 負の次数と呼びます。^{[ 2 ]}

次数和の公式は、グラフが与えられた場合、${\displaystyle G=(V,E)}$、

${\displaystyle \sum _{v\in V}\deg(v)=2|E|\,}$。

この式は、任意の無向グラフにおいて、次数が奇数の頂点の数は偶数であることを意味している。この命題（および次数和の公式）は、握手補題として知られている。後者の名前は、任意の人々の集団において、その集団内の奇数人の人と握手をした人の数は偶数であることを証明する、有名な数学の問題に由来する。^{[ 3 ]}

無向グラフの次数列は、その頂点の次数が非増加列である。^{[ 4 ]}上記のグラフの場合、次数列は (5, 3, 3, 2, 2, 1, 0) である。次数列はグラフ不変量であるため、同型グラフは同じ次数列を持つ。ただし、次数列は一般にグラフを一意に識別するものではなく、場合によっては同型でないグラフが同じ次数列を持つこともある。次数列によって同型を除いて識別されるグラフはユニグラフと呼ばれ、対応する次数列はユニグラフィックと呼ばれる。

次数列問題 とは、次数列が与えられた非増加正整数列となるようなグラフの一部または全部を見つける問題である。（末尾のゼロは、グラフに適切な数の孤立頂点を追加することで容易に実現できるため、無視してもよい。）次数列問題に解が存在するような単純グラフの次数列である列は、グラフ列またはグラフ列と呼ばれる。次数和公式の結果として、(3,  3,  1) のように奇数和を持つ列は、グラフの次数列として実現することはできない。逆もまた真である。つまり、列の次数が偶数であれば、それは多重グラフの次数列である。このようなグラフの構築は簡単である。奇数次数を持つ頂点をペアで接続し（マッチングを形成する）、残りの偶数次数を自己ループで埋める。与えられた次数列が単純グラフで実現できるかどうかという問題は、より難しい。この問題はグラフ実現問題とも呼ばれ、エルデシュ・ガライの定理またはハベル・ハキミのアルゴリズムのいずれかで解くことができます。与えられた次数列を持つグラフの数を見つける、または推定する問題は、グラフ列挙の分野の問題です。

より一般的には、ハイパーグラフの次数列は、その頂点の次数の増加しない列です。${\displaystyle k}$-単純な次数列である場合は、グラフで表すと${\displaystyle k}$-一様ハイパーグラフ。特に、${\displaystyle 2}$-グラフィックシーケンスはグラフィックです。与えられたシーケンスが${\displaystyle k}$-グラフィックは多項式時間で実行可能です${\displaystyle k=2}$エルデシュ・ガライの定理により、すべての に対してNP 完全である。${\displaystyle k\geq 3}$[ ^{5 ]​}

• 次数が0の頂点は孤立頂点と呼ばれます。
• 次数が 1 の頂点は、葉頂点、末端頂点、または垂下頂点と呼ばれ、その頂点に接続する辺は垂下辺と呼ばれます。右のグラフでは、{3,5} は垂下辺です。この用語は、グラフ理論における木構造の研究、特にデータ構造としての木構造の研究でよく用いられます。
• n個の頂点を持つグラフにおいて、次数がn − 1 の頂点を支配頂点と呼ぶ。  

• グラフの各頂点の次数がkである場合、そのグラフはk正則グラフと呼ばれ、グラフ自体の次数はkであると言われます。同様に、二部グラフにおいて、二部分割の同じ側にあるすべての頂点の次数が等しい場合、そのグラフは二部正則グラフと呼ばれます。  
• 無向連結グラフは、次数が奇数の頂点が0個または2個ある場合に限り、オイラー路を持つ。次数が奇数の頂点が0個の場合、オイラー路はオイラー閉路となる。
• 有向グラフは、すべての頂点の出次数が最大でも1である場合に限り、有向擬似森林である。関数グラフは、すべての頂点の出次数がちょうど1である擬似森林の特殊なケースである。  
• ブルックスの定理によれば、クリークまたは奇数サイクル以外のグラフGの彩色数は最大で Δ( G ) であり、ヴィジングの定理によれば、任意のグラフの彩色指数は最大で Δ( G )  +  1 である。
• k-退化グラフとは、各部分グラフの頂点の次数が最大でkであるグラフのことである。

• 有向グラフの入次数、出次数
• 学位分布
• 二部グラフの次数列

• エルデシュ、P. ;ガライ、T. (1960)。「Gráfok előírt fokszámú pontokkal」(PDF)。マテマティカイ・ラポック（ハンガリー語）。11 : 264–274 .。
• ハベル、ヴァーツラフ(1955)。「有限グラフの存在についてのコメント」。Časopis Pro Pěstování Matematiky (チェコ語)。80 (4): 477–480。土井: 10.21136/CPM.1955.108220。
• Hakimi, SL (1962). 「線形グラフの頂点の次数としての整数の集合の実現可能性について。I」。Journal of the Society for Industrial and Applied Mathematics . 10 (3): 496–506 . doi : 10.1137/0110037 . MR 0148049 . 。
• シールクスマ、ジェラルド。ハン・ホーヘフェーン (1991)。「整数列がグラフィックであるための 7 つの基準」。グラフ理論ジャーナル。15 (2): 223–231。土井: 10.1002/jgt.3190150209。MR 1106533。 。