次数(グラフ)
提供: Mathpedia
基本的な用語についてはグラフについても参照されたい。
定義
グラフ $G = (V,E)$ について、頂点 $v$ の次数とは $v$ に接続する辺の個数のことをいう。この値について、$d(v)$ と表記する。また、$G$ の最大次数とは $\Delta(G) = \mathrm{max}_{v \in |G|}(d(v))$ のことをいい、$G$ の最小次数とは $\delta(G) = \mathrm{min}_{v \in |G|}(d(v))$ のことをいう。空でない有限グラフ $G$ の平均次数とは $d(G) = \frac{\sum_{v \in |G|} d(v)}{|G|}$ のことをいう。
定義より明らかに、空でない有限グラフについて $$\delta(G) \leq d(G) \leq \Delta(G)$$ が成り立つ。
正則グラフ
有限グラフ $G = (V,E)$ が正則グラフであるとは、任意の頂点 $v$ について $d(v)$ の値がすべて等しいことをいう。$d(v) = k$ であるとき $G$ を $k$-正則グラフであるという。
性質
命題 1 (奇次数頂点の偶個数性)
有限グラフについて、次数が奇数であるような頂点は偶数個存在する。
証明
$\sum_{v \in G} d(v) = 2|E|$ より、次数が奇数となるような頂点は偶数個存在する必要がある。
□information
情報源
- R. Diestel. "Graph Theory". Springer (2000).
