次数(グラフ)
概要
グラフ $G=(V, E)$ について、の頂点 $v$ の次数 (degree) とは、$v$ に接続する辺の個数のことをいう。
基本的な用語についてはグラフについても参照。
定義
グラフ $G = (V,E)$ について、頂点 $v$ の次数 (degree) $d(v)$とは $v$ に接続する辺の個数のことをいう。すべての頂点 $v\in V$ に関する次数の最大値を $\Delta(G) = \mathrm{max}_{v \in |G|}(d(v))$ を $G$ の最大次数といい、次数の最小値 $\delta(G) = \mathrm{min}_{v \in |G|}(d(v))$ を $G$ の最小次数という。空でない有限グラフ $G$ のすべての頂点 $v\in V$に関する次数の平均値 $d(G) = \frac{\sum_{v \in |G|} d(v)}{|G|}$ を $G$ の平均次数 という。
定義より明らかに、空でない有限グラフについて $$\delta(G) \leq d(G) \leq \Delta(G)$$ が成り立つ。
正則グラフ
有限グラフ $G = (V,E)$ が正則グラフ (regular graph)であるとは、任意の頂点 $v$ について $d(v)$ の値がすべて等しいことをいう。任意の頂点について $d(v) = k$ であるとき $G$ を $k$-正則グラフであるという。
性質
$$\sum_{v \in G} d(v) = 2|E|.$$
$$\sum_{v \in G} d(v) = \sum_{v\in G}\sum_{w: \{v, w\}\in E}1 = \sum_{(v, w)\in E^2: \{v, w\}\in E}1$$
となるが、各辺 $\{v, w\}\in E$ について $(v, w)$ および $(w, v)$ が対応するから、これは $2\abs{E}$ に等しい。
有限グラフについて、次数が奇数であるような頂点は偶数個存在する。
定理1 より $\sum_{v \in G} d(v) = 2|E|$ となるから、次数が奇数となるような頂点は偶数個存在する必要がある。
